문제 개요
N개의 요소를 가진 배열 A가 있다고 가정해 봅시다. N마리의 고양이가 있으며, 각각 1부터 N까지 번호가 매겨져 있습니다. 모든 고양이는 모자를 하나씩 쓰고 있는데, i번째 고양이는 "나를 제외한 나머지 N-1마리 고양이의 모자 중에서 서로 다른 색상은 정확히 A[i]가지다"라고 말합니다.
우리가 확인해야 할 것은, 고양이들의 발언과 모순되지 않는 모자 색상 배치가 실제로 존재하는지 여부입니다.
예를 들어 입력이 A = [1, 2, 2]라면 출력은 True입니다. 1번 고양이는 빨간색 모자를, 2번과 3번 고양이는 파란색 모자를 쓴다고 하면 각 고양이의 발언과 일치하기 때문입니다.
해결 접근 방식
이 문제는 다음 단계를 통해 해결할 수 있습니다.
먼저 배열 A의 최솟값(mn), 최댓값(mx)을 구하고, 최솟값과 같은 값을 가진 원소의 개수(cnt)를 셉니다. 그다음 경우를 나누어 판단합니다.
- 최댓값과 최솟값이 같은 경우(mx == mn): 모든 고양이가 같은 값을 말한다는 의미입니다. 이때 mn이 n-1과 같거나, 2 * mn <= n을 만족하면 참(true)을 반환하고, 그렇지 않으면 거짓(false)을 반환합니다.
- 최댓값이 최솟값 + 1인 경우(mx == mn + 1): mn >= cnt 그리고 n - cnt >= 2 * (mx - cnt) 조건을 만족하면 참을 반환하고, 아니면 거짓을 반환합니다.
- 그 외의 경우: 두 값의 차이가 1보다 크면 성립할 수 없으므로 거짓을 반환합니다.
C++ 구현 예제
아래 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
bool solve(vector<int> A) {
int mn = 99999, mx = 0, cnt = 0;
int n = A.size();
vector<int> a(n + 1);
for (int i = 1; i <= n; ++i) {
a[i] = A[i - 1];
mn = min(mn, a[i]), mx = max(mx, a[i]);
}
for (int i = 1; i <= n; ++i)
if (a[i] == mn)
++cnt;
if (mx == mn) {
if (mn == n - 1 || 2 * mn <= n)
return true;
else
return false;
}
else if (mx == mn + 1) {
if (mn >= cnt && n - cnt >= 2 * (mx - cnt))
return true;
else
return false;
}
else
return false;
}
int main() {
vector<int> A = { 1, 2, 2 };
cout << solve(A) << endl;
}입력
{ 1, 2, 2 }출력
1
출력값 1은 true, 즉 고양이들의 발언과 일치하는 모자 색상 배치가 존재함을 의미합니다.