[C++][난이도 Easy] Two Sum

코딩 테스트 대비를 위해 leetcode를 사용하는 이유

 

보통 IT 기업으로 취업이나 이직을 준비할 때, 면접 과정 중 빠질 수 없는 요소가 바로 코딩 테스트입니다. 저는 가끔 leetcode라고 불리는 코딩 테스트를 위한 사이트에서 문제를 풀어보는데요, 제가 leetcode를 쓰는 이유로 2가지가 있습니다. 

 

1. leetcode는 해외 IT 대기업 (구글, 애플, 아마존, 메타 등)에서 코딩 테스트 문제로 많이 출제되는 사이트입니다. 일종의 문제 은행처럼, leetcode에 있는 문제들을 반복해서 풀어볼 수 있고, 돈을 지불하면 각 기업별 코딩 테스트 문제와 유사한 유형의 문제들도 풀어볼 수 있습니다. 저는 아직 해외로 이직하기에는 실력이 많이 부족하기 때문에, 여가 시간에 심심풀이로 문제를 풀어보고 Notion에 정리해두고 있습니다. 언젠가 이직을 준비할 때 큰 도움이 될 것으로 생각됩니다. 

 

2. leetcode는 문제마다 "Discussion"이라는 페이지를 제공합니다. 여기서는 다른 사람이 올린 코드와 설명을 볼 수 있는데요, 전세계의 사람들이 각자 이 문제를 어떻게 해결했는지를 알 수 있습니다. 개인적인 생각이지만, 다른 사람이 제시한 해결 방법을 분석해보는 것도 스스로 성장할 수 있는 기회라고 생각됩니다. 왜냐하면, 우물 안 개구리처럼 저만의 편협한 사고에서 벗어날 수 있고, 무엇보다도, 보통 면접을 들어갈 때 recurssive로 짠 코드를 iterative하게 코드를 짜보라던가, stack으로 짠 코드를 queue로 짜보라던지, 이런 라이브 코딩도 많이 질문 받습니다. 이런 경우를 대비해서 다른 사람이 짠 코드도 찾아 보고 분석하는 노력도 필요하겠지요? 

 

 

Two Sum 문제 분석

 

[사진 1] Leetcode Two Sum 문제

 

오늘의 첫번째 문제는 leetcode의 난이도 easy 첫번째 문제인 Two Sum 입니다. 전체 문제에 대한 설명은 아래 [그림 1]과 같습니다. nums라는 int형 vector, target이라는 int형 자료를 함수 twoSum에서 입력받았을 때, nums 안에 있는 2개의 수를 더해서 target을 만들어낼 수 있다면, 이 두 수의 index를 또 다른 int형 vector에 넣어서 반환해주면 해결되는 문제입니다. 문제의 가정은 딱 1개의 답만 존재하고, 동일한 인덱스에 대응되는 수를 2번 반복해서 사용할 수 없다고 되어 있네요. 예제를 살펴볼까요?

 

우선 첫번째 예제는 target이 9이기 때문에, nums 안의 2와 7을 선택하면 되겠군요. 그리고 2와 7은 nums의 0번째, 1번째 인덱스에 대응되기 때문에, 최종 결과는 0과 1이 됩니다. 두번째 예제는 target이 6이므로, nums 안의 2와 4를 더하면 되고, 이 2와 4는 nums의 1번째, 2번째 인덱스에 대응됩니다. 따라서 최종 결과는 1과 2가 됩니다. 마지막 예제에서 target은 6이고 nums의 두 수가 모두 3이라서, 반환되는 인덱스는 0과 1입니다. 이 때, nums 안에 3이 2번 반복해서 들어갔어도, 서로 다른 인덱스로 맵핑된 수이기 때문에, 위에서 말한 2번째 가정에 위배되지 않습니다.

 

또 하나 leetcode의 장점이라고 볼 수 있는게, 가끔 문제 밑에 follow-up이 있습니다. 여기서는 O(n^2) 보다 더 작은 시간 복잡도로 문제를 풀어볼 수 있는지 제안하고 있습니다. 사실 O(n^2)으로 코드를 제출해도 괜찮지만, 연산 시간이 너무 오래 걸려서 timeout으로 테스트를 통과하지 못할 수도 있습니다. 따라서, follow-up에서 제안하는 내용을 적용해보기 위해 고민해보는 것도 실력 향상에 도움이 될 것 같습니다.

 

 

Two Sum 문제 해결을 위한 C++ 코드

 

#include <algorithm> 
#include <map>

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        map<int, vector<int>> select_nums;

        for (int i = 0; i < nums.size(); i++)
        {
            select_nums[nums[i]].push_back(i);
        }
        
        for (int i = 0; i < nums.size(); i++)
        {
            int first = nums[i];
            auto item1 = select_nums.find(first);
            
            int second = target - nums[i];
            
            auto item2 = select_nums.find(second);
            if (item2 != select_nums.end())
            {   
                if ((first == second) && (item2->second.size() > 1))
                {
                    result.push_back(item1->second[0]);
                    result.push_back(item2->second[1]);
                    sort(result.begin(), result.end());
                    break;
                }
                else if (first != second)
                {
                    result.push_back(item1->second[0]);
                    result.push_back(item2->second[0]);
                    sort(result.begin(), result.end());
                    break;
                }
            }
        }
        
        return result;
           
    }
};

 

부끄럽지만, 제가 C++로 이 문제를 해결한 코드를 올려보겠습니다. 저는 C++에서 제공하는 map이라는 STL을 써서 해결해보았습니다. 첫번째 for loop에서 nums에 저장된 숫자들이 select_nums라는 map의 key, nums에 저장된 숫자들에 대응되는 인덱스를 value로 저장하였습니다. 이 때, select_nums의 value를 vector로 선언한 이유가, 예제처럼 nums 안에 숫자가 동일한데 인덱스가 다른 경우를 처리하기 위함이었습니다. 

 

두번째 for loop에서는 nums의 인덱스 0부터 차례대로 접근하면서, 각 인덱스에 대응되는 수들을 select_nums에서 검색하고, 그 결과를 item1에 저장하였습니다. 이후, target을 지금 접근한 nums 안의 숫자만큼 뺀 값을 second라는 변수에 저장하고, 이 값을 다시 select_nums에서 검색 후 item2에 저장하였습니다. 이후 조건문에서, 현재 nums에서 선택한 숫자 first와 (target - first) 값 (코드에서 second)이 동일한지 다른지를 비교하고, 만약 다르다면 first와 second의 인덱스를 vector 변수인 result에 넣고 이를 반환합니다. 만약 동일하다면, nums에 지금 first와 동일한 숫자를 보였던 인덱스가 2개 이상 있었는지 검사해서, 만약 이에 해당되면, result에 검색된 index 정보를 저장하고 반환합니다. 그리고 정답은 항상 1개만 존재하기 때문에, loop을 다 실행할 필요도 없이, break 문을 통해 loop을 빠져나왔습니다.

 

 

Two Sum 문제의 솔루션 코드 중 제일 많은 추천을 받은 코드

 

[사진 2] Leetcode Two Sum 문제 솔루션 코드 중 제일 많은 추천 받은 코드

 

이제 다른 사람이 이 문제를 해결할 때 사용한 코드도 살펴볼까요? 아래 [그림 3]과 같이, 제가 짰던 코드보다 훨씬 간단한 것을 알 수 있습니다 (솔직히 다른 사람이 짠 코드를 보면 자괴감 + 존경의 마음을 갖게 됩니다). 우선 hashmap이라는 map 타입을 가지고, 전체 nums에 대해 loop을 반복하면서 (target - (현재 접근한 숫자))인 secondele를 계산합니다. 이후 if 문에서 secondele가 hashmap에 이미 존재하고 있고, 현재 가리키고 있는 인덱스 i와 다르다면 (즉, 동일한 숫자라도 인덱스가 다른 경우를 의미), vector 타입 out에 현재 접근한 인덱스 i와 secondele의 인덱스를 저장해서 반환합니다. 만약 아니라면, hashmap에 지금 접근한 nums의 값과 인덱스를 pair로 묶어서 저장해주고, 다시 loop을 진행합니다. 이렇게 구현하면, 저처럼 nums 내 동일한 숫자를 처리하기 위해, map의 value가 vector가 될 필요가 없었던거죠. 역시 갈 길이 멀군요.

 

 

지금까지 Two Sum 문제에서 다뤄봤습니다. 위 출처 링크의 Discussion 페이지를 보면 또 다른 해결 방법들도 나와있으니까, 찾아보시는 것도 좋을 것 같습니다.