문제 개요
n개의 요소를 가진 배열 A와 숫자 k가 주어진다고 가정해 봅시다. 한 학급에 n명의 학생이 있고, i번째 학생의 평점은 A[i]입니다. 우리는 k명의 학생으로 팀을 구성해야 하며, 팀원 모두의 평점이 서로 달라야 합니다.
만약 이러한 조건을 만족하는 팀을 구성하는 것이 불가능하다면 "Impossible"을 반환하고, 가능하다면 해당 학생들의 인덱스 시퀀스를 반환하면 됩니다.
예시
입력이 A = [15, 13, 15, 15, 12], k = 3이라면, 출력은 [1, 2, 5]가 됩니다. 즉, 1번(평점 15), 2번(평점 13), 5번(평점 12) 학생을 선택하면 세 명의 평점이 모두 서로 다르므로 조건을 충족합니다.
해결 접근 방식
이 문제는 그리디(Greedy) 방식으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 배열을 처음부터 끝까지 순회하면서 처음 등장하는 평점만 선택합니다.
- 이미 등장한 적이 있는 평점은 건너뛰고, 새로운 평점일 때만 그 인덱스를 결과 배열에 저장합니다.
- 순회가 끝난 후 서로 다른 평점의 개수(cnt)가 k 이상이면, 저장된 인덱스 중 앞에서 k개를 출력합니다.
- k 미만이라면 중복 없이 k명을 뽑을 수 없으므로 "Impossible"을 출력합니다.
알고리즘 단계
- 방문 여부를 기록하는 배열 app과 결과를 저장하는 배열 ans를 선언하고 0으로 초기화한 뒤, 카운터 cnt를 0으로 설정합니다.
- i를 1부터 n까지 반복하면서 각 학생의 평점 a = A[i-1]을 확인합니다.
- app[a]가 0이라면(아직 등장하지 않은 평점이라면) app[a]를 1로 만들고, cnt를 증가시킨 후 ans[cnt]에 현재 인덱스 i를 저장합니다.
- 반복 종료 후 cnt >= k라면 ans[1]부터 ans[k]까지 출력하고, 그렇지 않으면 "Impossible"을 출력합니다.
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
void solve(vector<int> A, int k) {
int app[101] = { 0 }, ans[101] = { 0 }, cnt = 0;
int n = A.size();
for (int i = 1; i <= n; i++) {
int a = A[i - 1];
if (!app[a]) {
app[a]++;
ans[++cnt] = i;
}
}
if (cnt >= k) {
for (int i = 1; i <= k; i++)
cout << ans[i] << ", ";
}
else
cout << "Impossible";
}
int main() {
vector<int> A = { 15, 13, 15, 15, 12 };
int k = 3;
solve(A, k);
}실행 결과
입력
{ 15, 13, 15, 15, 12 }, 3출력
1, 2, 5,
복잡도 분석
- 시간 복잡도: O(n) — 배열을 한 번만 순회하면 되므로 매우 효율적입니다.
- 공간 복잡도: O(V) — V는 가능한 평점 값의 범위입니다. 위 코드에서는 평점이 1~100 사이라고 가정하여 크기 101의 배열을 사용했습니다.
마무리
이 문제는 중복 제거와 인덱스 추적을 결합한 전형적인 해시(방문 배열) 활용 문제입니다. 평점 범위가 크다면 app 배열 대신 unordered_set이나 map을 사용하면 메모리를 더 유연하게 관리할 수 있습니다. 또한 입력 배열에 음수나 큰 값이 포함될 수 있다면 해시 기반 자료구조를 쓰는 것이 안전합니다.