666영화제목 - 시간복잡도 질문

창신동 장첸

작성한 질문수 115

0

안녕하세요. 원진님. ㅎㅎ

총 연산이 1억이 되지 않으려면 for내부에서는 100번 이하 규모로 연산이 이뤄져야만 한다고 판단했습니다.

#include<bits/stdc++.h>
using namespace std; 
int n; 
int main() {
    cin >> n; 
    int i = 666; 
    for(;; i++){
        // 이 연산은 O(i의 자릿수)짜리입니다. 
        if(to_string(i).find("666") != string::npos)n--; 
        if(n == 0)break;
    }
    cout << i << "\n"; 
}

주석을 달았는데요. 100번이하라는 게 좀 애매한데요. 시간복잡도를 기준으로 보시는게 좋습니다.

저 i가 만약에 엄청나게 큰 자릿수라면 문제가 되지만 저 i자체가 그렇게 커지지 않기 때문에 해당 find연산은 O(1)이라고 봐도 무방합니다.

예를 들어 10000이라고 하면

2666799

가 나오게 되는데 이는 7자릿수밖에 안되거든요. 따라서 해당 연산은 O(1)이라고 봐도 무방했기 때문에 해당 연산에 대한 고려는 안해도 무방하다 생각했고 for반복문의 횟수만을 생각했습니다.

감사합니다.