C++에서 K번째 큰 원소

Source: Dev.to

🧩 문제 설명

배열과 정수 k 가 주어졌을 때, k번째로 큰 원소를 찾으세요.

예시

• 입력: [3, 2, 1, 5, 6, 4], k = 2
• 출력: 5

🧠 첫 번째 생각: 한 번 순회 + 탐욕적 업데이트

많은 배열 문제는 다음과 같이 해결할 수 있습니다.

• 한 번의 루프
• 상수 공간
• 탐욕적 업데이트

스스로에게 물었습니다: “한 번 순회하면서 k번째 큰 원소를 추적할 수 있을까?”

시도한 아이디어 (탐욕적 사고)

• 가장 큰 값들을 계속 업데이트한다.
• k번째 큰 값을 동적으로 유지하려고 한다.

❌ 왜 실패하는가

k번째 큰 값을 찾으려면 현재 값보다 큰 원소가 몇 개인지 알아야 합니다. 한 번의 순회에서는

• 미래의 원소를 알 수 없다.
• 정확한 순위를 결정할 수 없다.
• 탐욕적 결정이 신뢰할 수 없게 된다.

📌 핵심 인사이트

탐욕은 지역적인 결정이 전역적인 정확성을 보장할 때만 작동합니다.

탐욕이 깨지는 예시

배열: {7, 4, 6, 3, 9, 1}, k = 2

순회하면서 7이 큰 것처럼 보일 수 있지만, 나중에 9가 등장하면 순위가 바뀝니다. 이전의 탐욕적 결정은 무효가 됩니다. 순위 문제는 전체 컨텍스트가 필요하고, 부분적인 순회만으로는 해결되지 않습니다.

🧠 중요한 학습

✅ 올바른 접근법: STL sort() 사용

#include 
#include 
#include 
using namespace std;

int main() {
    vector arr = {3, 2, 1, 5, 6, 4};
    int k = 2;

    sort(arr.begin(), arr.end(), greater());

    cout << "Kth largest element: " << arr[k - 1];
}

⏱ 시간 및 공간 복잡도

• 정렬: O(n log n)
• 공간: 제자리 정렬 O(1) (재귀 스택 제외)

대부분의 인터뷰 문제에서는 제약이 크지 않은 한 충분히 괜찮습니다.

⚠️ 하지만 정렬이 항상 최선인가?

• 데이터가 매우 클 경우:
  • priority_queue → O(n log k)
  • nth_element → 평균 O(n)

학습 및 인터뷰에서는 sort()가

• 가독성이 좋고
• 신뢰성이 높으며
• 설명하기 쉬워

선호됩니다.

🧠 인터뷰 사고법 교훈 (가장 중요)

문제를 풀 때 스스로에게 물어보세요:

1. 문제에 전역 정렬이 필요한가?
2. 지역 탐욕적 결정이 정확성을 보장할 수 있는가?

답이 아니오라면 기억하세요: “최적화는 정확성 뒤에 온다.”

🚀 최종 정리

• 탐욕을 시도했지만 한계를 이해함.
• STL sort()를 사용해 정확하고 깔끔한 해결책을 얻음.
• 언제 최적화하지 말아야 하는지를 배움.

이것이 진정한 성장입니다.

📝 연습 제안

다음 체크리스트를 활용해 문제를 분류하세요:

• ✅ 탐욕 단일 패스가 가능한가?
• ✅ 정렬이 필요한가?
• ✅ 힙이 필요한가?

이 습관을 기르면 인터뷰 사고 속도가 향상됩니다.