백준 33511 (C++) 쉐이드 커튼 위 먼지는 쌓이는 중

최초 업로드: 2025-10-07 10:52:25

최근 수정 시간: 2025-10-07 10:52:25

게시자: rlatjwls3333

카테고리: 백준

# [Gold III] 쉐이드 커튼 위 먼지는 쌓이는 중

[문제 링크](https://www.acmicpc.net/problem/33511)

## 문제 설명

즈티는 심심하다. 그래서 즈티는 $N$명의 친구들에게 자신의 최애 수열 $A$를 선물하려고 한다. 하지만 즈티는 친구들에게 수열을 그냥 주지 않는다. 수열의 한 원소를 골라 그 원소를 값이 다른 수로 바꾼 뒤 선물한다. 즈티가 친구들에게 선물한 $N$개의 수열이 주어질 때, 즈티의 최애 수열 $A$를 구해보자.

## 입력

첫째 줄에 친구의 수 $N$과 수열 $A$의 길이 $M$이 공백으로 구분되어 주어진다. $(1 \le N, M \le 2\,000)$

다음 $N$개의 줄에 각 친구가 선물 받은 수열의 원소 $M$개가 공백으로 구분되어 순서대로 주어진다. 각 원소는 $1$ 이상 $2\,000$ 이하의 정수이다.

조건을 만족하는 수열 $A$가 존재하는 입력만 주어진다.

## 출력

즈티의 최애 수열 $A$의 $M$개의 원소를 공백으로 구분하여 한 줄에 출력한다. 각 원소는 $0$ 이상 $2\,000$ 이하의 정수여야 한다.

조건을 만족하는 출력이 여러 가지인 경우 그중 아무거나 출력한다.

## 풀이
중복된 수열을 제외하면 한 열에서 중복된 숫자가 나오는 것은 고정된다. 중복되지 않은 수열이 2개 이상 존재하면, 최대 2개의 빈칸이 나오고 나머지는 다 채워진다. 이제 빈칸이 M개인 경우 (중복되지 않은 수열이 1개인 경우), 빈칸이 0개인 경우, 빈칸이 2개인 경우로 나누어 case-work 하면 된다.

``` c++
#include<bits/stdc++.h>
using namespace std;

int n, m, res[2000], exist[2001];
vector<vector<int>> arr;

bool isAlreadyDiff(int i) {
 for(int j=0;j<m;j++) {
 if(res[j] && arr[i][j]!=res[j]) return true;
 }
 return false;
}

bool notCorrect() {
 for(int i=0;i<arr.size();i++) {
 int cnt=0;
 for(int j=0;j<m;j++) {
 if(res[j]!=arr[i][j]) cnt++;
 }
 if(cnt>=2) return true;
 }
 return false;
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 cin >> n >> m;
 for(int i=0;i<n;i++) {
 arr.push_back({});
 for(int j=0;j<m;j++) {
 int val; cin >> val;
 arr.back().push_back(val);
 }
 }
 sort(arr.begin(), arr.end());
 arr.erase(unique(arr.begin(), arr.end()), arr.end());

int blank=m;
 for(int j=0;j<m;j++) {
 memset(exist, 0, sizeof exist);
 for(int i=0;i<arr.size();i++) {
 if(++exist[arr[i][j]]==2) {
 res[j] = arr[i][j];
 blank--;
 break;
 }
 }
 }

for(int i=0;i<arr.size();i++) {
 if(isAlreadyDiff(i)) {
 for(int j=0;j<m;j++) {
 if(!res[j]) {
 res[j]=arr[i][j];
 blank--;
 }
 }
 }
 }

if(arr.size()==1) {
 for(int j=1;j<m;j++) res[j] = arr[0][j];
 } else if(blank==2) {
 int blankIdx1=-1, blankIdx2;
 for(int i=0;i<m;i++) {
 if(!res[i]) {
 if(blankIdx1==-1) blankIdx1=i;
 else blankIdx2=i;
 }
 }
 res[blankIdx1] = arr[0][blankIdx1];
 if(notCorrect()) res[blankIdx2] = arr[1][blankIdx2];
 if(notCorrect()) res[blankIdx1] = 0;
 }
 for(int j=0;j<m;j++) cout << res[j] << ' ';
}
```