[시간복잡도/Set] Jewels and Stones

Jeenie·2025년 5월 7일

코딩테스트 문제풀이

목록 보기

11/16

원리

문제의 핵심 : 자료구조를 통해 시간복잡도를 줄일 수 있는가?

초기 제출

풀이 소요시간 : 3m

시간복잡도 등은 전혀 고려하지 않고 무지성 반복문

var numJewelsInStones = function (jewels, stones) {
    let count = 0
    for (const el of stones) {
        if (jewels.includes(el)) {
            count++
        }
    }
    return count
};

chatGPT의 피드백

✅ 긍정적인 점

문제 해결력: 문제 요구사항을 명확히 이해하고, 정답을 올바르게 도출했습니다.

간결한 구조: 코드가 짧고 직관적이며, 누구나 쉽게 읽을 수 있습니다.

ES6 문법 활용: for...of, includes 등을 적절히 활용해 가독성이 좋습니다.

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

1. 시간 복잡도: includes는 내부적으로 순차 탐색을 하므로 O(n), 이를 stones.length 만큼 반복하면 전체 시간 복잡도는 O(n * m)가 됩니다 (n: stones, m: jewels).

2. 입력 크기가 클 경우 비효율적입니다. 최악의 경우, jewels에 50개 문자가 있고 stones에 10^4개가 있다면 상당한 반복이 발생합니다.

자료구조 최적화 필요: Set을 사용하면 O(1) 시간에 포함 여부를 체크할 수 있어 성능이 향상됩니다.

⏱ 시간복잡도 비교

방법	시간복잡도	설명
`includes()`	`O(n * m)`	`jewels.includes(stone)`는 매번 O(m)
`Set.has()`	`O(n + m)`	`jewels → Set 변환 O(m)`, 이후 `O(n)`

💡 더 나은 코드:

var numJewelsInStones = function (jewels, stones) {
    const jewelSet = new Set(jewels);
    let count = 0;

    for (const stone of stones) {
        if (jewelSet.has(stone)) {
            count++;
        }
    }

    return count;
};

시간 복잡도: O(n + m) (Set 생성 O(m), stones 순회 O(n))
공간 복잡도는 O(m) 정도 사용하지만 시간 효율이 훨씬 우수합니다.

✅ 면접관 한 마디 (총평)

깔끔한 풀이로 문제를 정확히 해결한 점은 인상적입니다. 다만, 입력 규모가 커질 경우 시간 복잡도를 고려한 자료구조 선택이 중요합니다. 코딩 테스트나 실무에서는 항상 성능을 염두에 둔 선택이 평가 요소 중 하나이므로, 상황에 따라 Set, Map 등의 자료구조를 적극 활용하는 습관을 들이는 것이 좋겠습니다.

개선

var numJewelsInStones = function (jewels, stones) {
    const set = new Set(jewels)
    let count = 0
    for(const el of stones) {
        if(set.has(el)){
            count++
        }
    }
    return count
};