A. 문제설명
https://www.acmicpc.net/problem/17140
자세한 설명은 위 링크에서
1. 3 * 3 배열이 존재
2. 배열에 매 초마다 연산을 적용
2-1. R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용
2-2. C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용
3. 여기서 정렬의 의미는 각 행 또는 열 내 숫자들을 계수, 숫자들이 발생한 횟수를 조건에 맞추어 정렬한다는 것
* [1, 1, 2, 3, 3] 의 배열이 존재한다고 가정. 1이 2개, 2가 1개, 3이 2개이므로 [1, 2, 2, 1, 3, 2]의 새로운 배열을 만듦
4. 새로 만든 배열은 아래와 같이 정렬됨
4-1. 등장횟수를 우선으로 숫자와 등장횟수 쌍을 오름차순 정렬
4-2. 등장횟수가 같은 수끼리는 그 크기를 기준으로 오름차순 정렬
* [1, 1, 2, 3, 3]을 계수하면 [1, 2, 2, 1, 3, 2]가 되고, 이를 정렬하면 최종적으로 [2, 1, 1, 2, 3, 2]가 됨
5. 배열을 정렬해서 각 행 또는 열에 넣고 길이가 100이 넘기는 것은 버리고, 100이 안되면 빈 곳을 0으로 채움
6. A[r][c]에 k가 나올때까지 반복. 100초가 넘으면 -1 반환
이 문제에서는 R/C 연산과 문제의 정렬방법에 대해서 이해하고 접근법을 생각하면 된다. 두가지 다 특정 조건들을 주어진대로 충실하게 구현할 수 있도록 하자.
B. 접근법
배열에 연산을 적용하고 100번 반복하는 시뮬레이션 문제. 여기서 a) R/C 연산의 선택을 위한 행/열 갯수 계산 b) 문제에서 주어진 배열 정렬법, a), b) 두가지를 염두하여 구현하자.
C. 풀이
1. 100번의 턴을 수행하는 반복문
2. 행/열의 크기에 따라 R/C 연산을 수행
3. 각 R/C 연산에서 해당 행/열의 크기만큼 각 배열을 뽑아내어 계수하고 정렬한다.
4. 배열 내 숫자의 등장 횟수를 계수(C++ Map 자료구조 사용)
5. 맵을 배열로 옮겨서 정렬
5-1. 숫자의 등장 횟수를 우선으로 오름차순정렬
5-2. 숫자 등장횟수가 같으면, 숫자의 크기를 기준으로 오름차순정렬
6. 정렬된 배열을 모두 채워줌
6-1. 빈 자리는 모두 0으로 채움
6-2. 배열이 넘치면 100번째 인덱스까지만 사용
7. 매 턴이 수행될 때마다 행/열의 크기를 업데이트
8. 100초내 K 값을 찾으면 종료
D. 내 코드
