[시간복잡도/Map] Two Sum

Jeenie·2025년 5월 7일

코딩테스트 문제풀이

목록 보기

12/16

원리

문제의 핵심 : 중복 반복문이 필요할 때 시간복잡도를 고려할 수 있는가?

첫 시도 (실패)

풀이 시간 : 20m

"찾는다"에 꽂혀서 그럼 시간복잡도 0(n)인 Set!
"더했을 때"에 꽂혀서 그럼 stack에 넣고 비교!
"인덱스"에 꽂혀서 그럼 for문!

로 시도했는데 도저히 풀리지 않았다.
처음부터 전혀 잘못접근한 것...

초기 제출

두가지 인덱스가 필요하기 때문에 이중 반복문으로 풀었다.

런타임 40ms

var twoSum = function (nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            // 문제 제한사항 : 현재 인덱스와 동일한 요소는 나오지 않아야한다
            if (nums[i] + nums[j] === target) {
                return [i, j]
            }
        }
    }
};

동작은 잘 하지만 이중 for문이라는 점이 치명적이다.
현재 이중 for문은 O(n²)의 시간복잡도를 가진다.
만약 nums의 길이가 길어진다면 시간복잡도가 엄청나게 증가할 것

시간복잡도를 개선해보자...

chatGPT의 피드백

✅ 긍정적인 점

문제 의도를 정확히 이해하고, 필요한 조건(서로 다른 두 인덱스의 합이 target인 경우)을 충족하도록 잘 구현했습니다.

중복 계산을 피하기 위해 j = i + 1부터 순회한 부분은 브루트포스 방식에서도 꼭 필요한 최적화 포인트입니다.

가독성 좋은 코드로 누구나 쉽게 이해할 수 있는 구조입니다. 초보 단계에서 이 정도 구현은 기본기를 잘 다지고 있다는 신호입니다.

🛠 개선 포인트 (면접자 기준 피드백)

시간 복잡도 O(n²): 이중 for문은 입력값이 커질수록 성능이 급격히 저하됩니다. LeetCode에서는 nums.length가 10⁴까지 될 수 있으므로 최적화된 풀이가 필요합니다.

실제 업무에서는 성능 이슈가 될 수 있으므로, 효율적인 방법(Map 활용 등)을 고려하는 사고력도 중요합니다.

코너 케이스가 없음: 예외 상황이나 문제 제약에 대한 방어 코드(ex. nums 길이가 2 미만인 경우 등)는 없지만, 문제 조건 상 항상 해가 있다고 명시되어 있으므로 이 점은 감안 가능합니다.

💡 더 나은 코드 (시간복잡도 O(n), 해시맵 사용):

var twoSum = function(nums, target) {
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (map.has(complement)) {
            return [map.get(complement), i];
        }
        map.set(nums[i], i);
    }
};

각 원소를 순회하며 필요한 값(target - nums[i])이 이미 저장된 값인지 즉시 확인합니다.
이를 통해 한 번의 반복만으로 해답을 찾을 수 있으며, 시간복잡도는 O(n) 입니다.

✅ 면접관 한 마디 (총평)
좋은 시작입니다. 문제를 정확히 이해하고, 조건에 맞게 정직하게 브루트포스로 구현한 점은 긍정적입니다. 하지만 코딩테스트나 실무에선 효율적인 자료구조 활용 능력이 중요하므로, 해시맵과 같은 도구를 빠르게 떠올리고 적용하는 사고력도 함께 키워야 합니다. 기본기 위에 성능 최적화를 더해가면 다음 단계로 성장할 수 있습니다.

개선

런타임 2ms
20배가 줄었다 와.....

var twoSum = function (nums, target) {
    const map = new Map()
    for (let i = 0; i < nums.length; i++) {
        // 나(nums[i])랑 더해서 target이 되려면 pair가 필요하다.
        const pair = target - nums[i]
        // 내가 지금 2인데 9를 만들기 위해서는 7이 필요해.
        if (map.has(pair)) {
            // 짝꿍인 7이 있다면 그 인덱스와 나의 인덱스를 리턴
            return [map.get(pair),i]
        }
        map.set(nums[i], i)
        // 순회없이 값으로 해당 인덱스를 한번에 찾기 위해서, 값과 인덱스를 페어로 저장한다.
    }
};