[ 내배캠 TIL 260325 ] C++ 로또 문제 (완전탐색 → 해시 최적화)

1. 기존 접근 (완전탐색)

처음에는 lottos와 win_nums를 이중 반복문으로 비교하여 맞춘 개수를 계산했다.

for(int i = 0 ; i < lottos.size() ; ++i)
{
    if(lottos[i] == 0)
    {
        blind++;
        continue;
    }
    
    for(int j = 0 ; j < win_nums.size() ; ++j)
    {
        if(lottos[i] == win_nums[j])
        {
            hit++;
            break;
        }
    }
}

• 시간복잡도: O(n²)
• 단순하지만 비효율적

---

2. 개선 포인트

이 문제의 핵심은
"각 숫자가 당첨 번호에 포함되어 있는지 여부를 판단하는 것"이다

→ 값의 존재 여부만 확인하면 되므로
해시 기반 자료구조를 사용하는 것이 적절하다

---

3. 개선된 접근 (unordered_set)

unordered_set<int> s(win_nums.begin(), win_nums.end());

for(int i = 0 ; i < lottos.size() ; ++i)
{
    if(lottos[i] == 0)
    {
        blind++;
    }
    else if(s.count(lottos[i]))
    {
        hit++;
    }
}

• 시간복잡도: O(n)
• count()를 사용해 O(1)로 존재 여부 확인

---

4. 등수 처리 개선

기존에는 등수를 수식으로 계산했지만,
가독성이 떨어지고 예외 처리가 필요했다.

→ 배열을 이용해 명확하게 매핑

vector<int> rank = {6,6,5,4,3,2,1};

answer.push_back(rank[hit + blind]);
answer.push_back(rank[hit]);

---

5. 핵심 배운 점

• 단순 비교 문제라도 "존재 여부"가 핵심이면 해시를 떠올려야 한다
• unordered_set을 사용하면 이중 반복문을 제거할 수 있다
• 문제의 규칙은 수식보다 "명시적인 매핑"이 더 읽기 쉽다

---

6. 한줄 정리

완전탐색으로 해결 가능한 문제라도,
"탐색 방식"을 바꾸면 시간복잡도를 크게 줄일 수 있다