백준 1436번 영화감독 숌(C++)

문제 해결 전략 :  1부터 1000000차례대로 666이 들어있는지 조사해서 N번째 666을 찾으면 출력하고 루프문을 벗어나서 프로그램 종료하게 만들었음

 

문제 해결 소감 : 메모리 초과 이슈가 처음 발생함, 메모리도 신경써야겠다는 생각이 들었음, 메모리 이슈 해결이 생각이 안나서 gpt의 도움을 받았다. 모든 수 스트링을 vector에 저장해놓지 않고 반복이 한번 끝나면 같은 메모리에 다른 값을 할당시키는 것으로 메모리 사용을 줄였다.

 

#include <iostream>
#include <vector>
#include <string>
using std::string;
using std::vector;
/*
x666 9
666x 10
xx666 90
x666x 90 199개
이 4가지 경우밖에 없네 별로 없으니가 brute force
*/
int N = 0;
int n = 0;
vector<string> v;
int main(void)
{
    std::cin >> N;
    for (int i = 0; i < 10000000; i++) // 666xxxx
    {
        v.push_back(std::to_string(i + 1)); // 1부터 9999까지 채우기
    }
    // 666이 들어가 있으면 카운트
    for (auto i : v)
    {

        if (i.find("666") != string::npos)
        {
            n++;
        }
        if (n == N)
        {
            std::cout << i;
            break;
        }
    }
    return 0;
}

 

에러 난 이유 :  메모리 초과, 벡터를 선언하고 각 베터마다 string을 일일이 저장해놓는 방힉이라 메모리를 많이 잡아 먹었음

#include <iostream>
#include <string>
using std::string;

int main()
{
    int N, n = 0;
    std::cin >> N;

    for (int i = 0;; ++i)
    { // 숫자를 하나씩 처리
        string num = std::to_string(i);
        if (num.find("666") != string::npos)
        {
            n++;
        }
        if (n == N)
        {
            std::cout << num << std::endl;
            break;
        }
    }

    return 0;
}

 

에러 해결 방법: vector에 모든 수 string을 할당하지 않고 매 루프마다 메모리를 재활용함