원리

초기제출 (time limit exceed)

풀이시간 24m
⚠️ time limit exceed 시간초과

배열을 떠올렸다가, Set를 떠올렸다가, Map을 떠올렸다가
다 잘 안되어서 그냥 제일 쉬운 stack과 count로 풀었다.

그랬더니 히든 테스트케이스가 있었나보다!
제출하니까 nums가 10만개인 테스트가 있었고.... 역시 통과하지 못했다.

    const stack = []
    let count = 0
    for (const num of nums) {
        if (stack.includes(num)) {
            count += 1
        }
        stack.push(num)
    }
    return count !== 0

chatGPT의 피드백

좋은 시도예요! 이 문제는 매우 자주 출제되는 기초 해시셋 문제입니다.
면접관 입장에서 아래처럼 피드백할 수 있습니다.

---

🔍 긍정적인 부분:

• 다양한 접근을 고민한 흔적이 좋아요: Set, Map, stack 등
• 메모를 통해 스스로 질문하며 문제 해결하는 방식은 학습에 매우 효과적입니다

⚠️ 개선 포인트:
1. ❌ stack.includes(num)는 비효율적
includes는 내부적으로 O(n) 이므로, 전체 루프와 함께 **O(n²)**가 됩니다
이 문제는 더 빠르게 **O(n)**에 해결 가능해요
2. ❌ count를 셀 필요 없음
요구는 "중복 존재 여부"이지, 횟수 세기가 아닙니다
조건이 충족되면 바로 return true하는 게 효율적
3. ❌ Stack은 의미상 맞지 않음
중복 체크엔 Stack보다 Set이나 Map이 더 자연스럽고 명확해요
Stack은 LIFO(후입선출) 구조지만, 이 문제에선 그런 특성이 필요 없습니다

✅ 면접에선 이런 코드가 더 좋습니다:

var containsDuplicate = function(nums) {
    const seen = new Set();
    for (const num of nums) {
        if (seen.has(num)) return true;
        seen.add(num);
    }
    return false;
};

🔍 설명:

• Set은 내부적으로 해시 기반이라 has와 add 모두 O(1)
• 중복 발견 즉시 return → 빠른 탈출

---

💡 면접관이 좋아할 말:

“중복 체크는 순서를 고려하지 않으므로 Set이 적합하고, 해시 기반이기 때문에 빠르게 조회할 수 있습니다. includes는 선형 탐색이라 비효율적이기 때문에 피했습니다.”

개선

런타임 16ms

var containsDuplicate = function (nums) {
    const checked = new Set()
    // set는 비어있는 상태로 시작해야한다. 중복인 숫자가 나오면 그때 추가되도록
    for (const num of nums) {
        if (checked.has(num)) { return true };
        checked.add(num)
    }
    return false
};

const set = new Set(nums)
처음엔 이렇게 생성하고 시작해서 계속 false를 받았다. (Set는 중복 제거된 set를 만든다)

느낀점

"선형 탐색인 includes는 시간복잡도 측면에서 비효율적이니까 Set 구조를 써야겠는데?"

라는 생각을 떠올렸는데 잠깐 해보고 안되니까 바로 포기한게 아쉽다!
(초기에 빈 set로 시작하지 않아서 오류가 났던 것)

그래도 실전에서는 비효율적으로 풀고 나서 -> 시간 남으면 효율적으로 푸는 순서가 맞으니까. 잘했다

✅ 해당 자료구조의 특성이 문제에 요구되는지 먼저 생각하자

❌ 무조건 Stack으로 시작하지 말기