배열에서 첫 번째 반복 요소 (C++)

Source: Dev.to

왜 처음 접근 방식이 틀렸는가 — 그리고 어떻게 고쳤는가

문제 명확화 (매우 중요)

작업은 모든 반복 요소 중에서 첫 번째 등장 인덱스가 가장 작은 요소를 찾는 것입니다. 이는 다음이 아닙니다:

• 가장 작은 값
• 단순히 중복된 어떤 요소든

순서가 중요합니다.

초기 완전 탐색 접근법 (잘못된 논리)

vector v = {1, 2, 3, 4, 1, 2};
int t = INT_MAX;

for (int i = 0; i = j) {
    t = v[j];   // ❌ wrong comparison & assignment
}

cout = j는 값과 인덱스를 혼합하여 잘못된 결과를 초래합니다.

수정된 완전 탐색 솔루션 (인덱스 기반 사고)

문제를 다시 생각해 보면, 목표는 반복 요소의 가장 작은 인덱스를 추적하는 것이며, 값 자체가 아닙니다.

vector v = {1, 2, 3, 4, 1, 2};
int t = INT_MAX;

for (int i = 0; i  i) {
    t = i;   // ✅ store first occurrence index
}

vector v = {4, 5, 6, 7, 5, 4, 7};
vector freq(100, 0);
int t = INT_MAX;

for (int x : v) {
    if (freq[x] > 0) {
        t = x;
        break;
    }
    freq[x]++;
}

cout << t;

복잡도

• 시간: O(n)
• 공간: O(k) 여기서 k는 가능한 값의 범위(여기서는 100)입니다.

직접 해보기 (unordered_map 사용)

어떤 솔루션을 보기 전에, std::unordered_map을 사용해 첫 번째 발생을 추적하여 문제를 해결해 보세요.

핵심 학습 (가장 중요)

실수는 구문 오류가 아니라 문제 진술을 오해한 것이었습니다.

• 작업의 맥락에서 “첫 번째”가 무엇을 의미하는지 항상 명확히 하세요.
• 순서를 포함하는 문제에서는 인덱스 기반 사고가 필수적입니다.

최종 정리

초기 솔루션은 비록 틀렸지만, 요구 사항을 올바르게 해석하는 것이 얼마나 중요한지 강조하는 데 도움이 되었습니다. 자신의 논리를 고치는 것은 문제 해결 능력을 향상시키는 가장 강력한 방법 중 하나입니다.