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

안녕하세요 준영님 ㅎㅎ

처음 문제를 봤을 때, 저도 조합을 떠올려서 이중 for문을 사용하여 문제를 풀어볼까 했었는데, 그러면 코드의 시간 복잡도가 O(n^2)이니까, n = 15000일 경우 연산 횟수가 대략 15,000 * 15,000번 이기 때문에 시간 초과가 날 거라고 생각해서 다른 방법을 계속 생각했는데요...

>> 이렇게 생각하시는게 맞습니다. 처음에는 당연히 아이거 너무 큰데.. 하면서 들어가시는게 맞습니다. 그렇게 꼭 앞으로도 생각하셔야 합니다. 잘하셨어요 ㅎㅎ

참고로 이 문제는 사실 이렇게 효율적으로도 풀 수 있습니다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    map<int, int> mp;
    vector<int> keys;
    int ret = 0;

    for (int i = 0; i < n; i++) {
        int temp;
        cin >> temp;
        mp[temp]++;
        keys.push_back(temp);
    }

    for (int key : keys) {
        if (mp.find(key) != mp.end() && mp.find(m - key) != mp.end()) {
            if (key != m - key || mp[key] > 1) {
                ret++;
                mp.erase(key);
                mp.erase(m - key);
            }
        }
    }

    cout << ret;
    return 0;
}

그러나 제가 이 문제를 낸 이유 중 하나는 코테를 풀 때 무식하게 푸는 것을 가장 먼저 생각해야하기 때문에 그렇습니다. 무식하게 -> 효율적으로? -> 어 안되네? -> 무식하게 시도 이런식의 과정이 빠르게 일어나야 합니다.

결국 못 풀어서 문제 해설을 보니 처음 생각했던 그 방법이여서 조금 당황스러웠습니다. O(n^2)정도 시간복잡도를 가진 알고리즘이 떠올랐을 땐, 그냥 시간 초과 신경 안 쓰고 문제 풀이를 이어나가도 되는건가요?

>> 아뇨 좀 크다 싶으시면... 효율적인 방법 생각한 이후에 안되겠다 싶으면 시도 -> 시간초과 -> 다른 방법 다시 생각.

이런 플로우가 이어져야 합니다.

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

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.