인프런 커뮤니티 질문&답변

안녕하세요 진살님 ㅎㅎ

일단 주석을 달아서 1 ~ 3은 답변 드렸구요.

#include<bits/stdc++.h>
using namespace std;
int n, m;
string s[1000004], t; 

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m;
	// Q1. 첫번째 for문의 Big-O 표기법은 O(n)이 맞나요? 
    for (int i = 0; i < n; i++)
    {
        cin >> s[i];
    }
	// Q2. 두번째 for문의 Big-O 표기법은 O(m*n)이 맞나요? 넵. 
    for (int i = 0; i < m; i++)
    {
        cin >> t;
        if(atoi(t.c_str())){
            cout << s[stoi(t)+1] << "\n";
        }
        else{
            for (int i = 0; i < n; i++)
            {
                if(t == s[i]) cout << i << "\n";
            }
            
        }
    }
    // Q3. 포켓몬 이름의 최대 길이는 20이고, 포켓몬의 최대 갯수는 100,000입니다. 
	// 그렇다면 단순히 string 타입의 배열로 담았을 때 필요한 메모리의 크기는 
	// 20 * 100,000 < 256MB 라고 계산하는게 맞나요? 넵 맞습니다. 다만, 알파벳은 1바이트인데 한글은 
	// 3바이트에요. 이부분은 교안에 설명되어있으니 참고 부탁드려요.
	// 이 문제는 알파벳만 나오니 그렇게 계산하는게 맞습니다.  
    return 0;
}

그리고..

Q4. 문제의 메모리 제한은 계산으로 역추적이 가능한데, 시간 제한은 어떻게 Big-O 표기법과 연관지어서 생각할 수 있는지 잘 모르겠습니다.. 문제에서 주어지는 시간 제한을 계산하는 방법이 궁금합니다!

>> 음.. 이거 혹시 제 시간복잡도 강의 보셨나요? 제가 6강의에 걸쳐서 설명을 하는데 일단 안보셨으면 참고 부탁드리구요.

이 4 - 1과 함께 설명을 드리자면

이 문제는 O(N *M)으로 풀수가 있습니다. 다만 그렇게 해서 제출하면 시간초과가 나죠.

자, 그러면 이 문제는 그것보다 더 작게 해야 한다는 것을 알 수 있습니다.

이겁니다!! (넹?!)

다시 말씀드리면, 진살님의 접근방법은 좋아요. 시간복잡도 계산도 잘하셨구요.

이렇게 해서 제출을 해봅시다.

어?

시간초과가 나네?

그러면 생각해보는겁니다. 어디서 시간초과를 해결할 수 있을까.

좀 높게 되는 부분은 바로 이부분입니다. O(N *M) 부분이니까요.

            for (int i = 0; i < n; i++)
            {
                if(t == s[i]) cout << i << "\n";
            }

진살님은 string 배열 이라는 하나의 자료구조에만 key, value를 담았고

그걸 기반으로 이런식으로 key에 해당하는 것은 바로 출력이 가능한 걸 볼 수 있습니다.

        if(atoi(t.c_str())){
            cout << s[stoi(t)+1] << "\n";
        }

근데 value를 기반으로 하려다 보니 앞서 설명한 코드처럼 O(N * M)이 나는 것이죠.

그렇다면..?

value : key 형태로 하나의 자료구조를 더 만들어서 하면 되지 않을까?

하는 발상이 필요한 것이죠.

진살님의 접근법, 시간복잡도 계산은 좋았습니다. 이걸 기반으로 어떻게 하면 개선할 수 있을까? 발상 및 구현만 좀 더 다듬으시면 될 것 같아요.

또 질문 있으시면 언제든지 질문 부탁드립니다.

감사합니다.

강사 큰돌 올림.