[BOJ] 17140 이차원 배열과 연산

https://www.acmicpc.net/problem/17140

17140번: 이차원 배열과 연산

문제

크기가 3×3인 배열 A가 있다. 배열의 인덱스는 1부터 시작한다. 1초가 지날때마다 배열에 연산이 적용된다.

• R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
• C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.

한 행 또는 열에 있는 수를 정렬하려면, 각각의 수가 몇 번 나왔는지 알아야 한다. 그 다음, 수의 등장 횟수가 커지는 순으로, 그러한 것이 여러가지면 수가 커지는 순으로 정렬한다. 그 다음에는 배열 A에 정렬된 결과를 다시 넣어야 한다. 정렬된 결과를 배열에 넣을 때는, 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저이다.

예를 들어, [3, 1, 1]에는 3이 1번, 1가 2번 등장한다. 따라서, 정렬된 결과는 [3, 1, 1, 2]가 된다. 다시 이 배열에는 3이 1번, 1이 2번, 2가 1번 등장한다. 다시 정렬하면 [2, 1, 3, 1, 1, 2]가 된다.

정렬된 결과를 배열에 다시 넣으면 행 또는 열의 크기가 달라질 수 있다. R 연산이 적용된 경우에는 가장 큰 행을 기준으로 모든 행의 크기가 변하고, C 연산이 적용된 경우에는 가장 큰 열을 기준으로 모든 열의 크기가 변한다. 행 또는 열의 크기가 커진 곳에는 0이 채워진다. 수를 정렬할 때 0은 무시해야 한다. 예를 들어, [3, 2, 0, 0]을 정렬한 결과는 [3, 2]를 정렬한 결과와 같다.

행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다.

배열 A에 들어있는 수와 r, c, k가 주어졌을 때, A[r][c]에 들어있는 값이 k가 되기 위한 최소 시간을 구해보자.

입력

첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100)

둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.

출력

A[r][c]에 들어있는 값이 k가 되기 위한 연산의 최소 시간을 출력한다. 100초가 지나도 A[r][c] = k가 되지 않으면 -1을 출력한다.

풀이

행과 열의 길이에 따라 열을 늘리거나 행을 늘려야하기 때문에, 연산에 편의성을 위하여 먼저 열을 늘려주는 함수를 만들었다(R). 이제 만약 열의 길이가 행보다 길면 행을 늘려줘야하는데 일반적인 배열의 형태에서 순차적으로 행을 늘리기란 굉장히 번거로운 작업이기 때문에 만약 행을 늘려줘야한다면 배열의 가로와 세로를 뒤집어주고(T(arr)) R함수를 실행한 후 다시 뒤집어주면 되는 것이었다. 구현하는게 조금 복잡하기는 했지만 비교적 쉽게 풀 수 있었던 것 같다. 여기서 반례를 보다가 깨닫은 점이 만약 처음 주어진 r, c가 3보다 크면 모든 경우에 대하여 A[r][c]를 찾아줄 경우 당연히 인덱스 에러가 난다는 것이었다. try문으로 배열의 크기가 r, c보다 크거나 같을 때만 확인해줘야 한다. 또한 r과 c는 1부터 시작이다(0부터 시작하지 않으니 하나씩 빼줘야한다).

import sys
from collections import Counter
input = lambda: sys.stdin.readline().rstrip()
r, c, k = map(int, input().split())
arr = [list(map(int, input().split()))for _ in range(3)]
def R(arr):
  tmp = [[]for _ in range(len(arr))]
  for i in range(len(arr)):
    counter = Counter(arr[i])
    counter = sorted(counter.items(), key = lambda x: (x[1], x[0]))
    for k in counter:
      if k[0] == 0:
        continue
      if len(tmp[i]) == 100:
        break
      tmp[i].append(k[0])
      tmp[i].append(k[1])
  row_length = max(len(tmp[i])for i in range(len(tmp)))
  for i in range(len(tmp)):
    if len(tmp[i]) < row_length:
      while len(tmp[i]) < row_length:
        tmp[i].append(0)
  return tmp
def C(arr):
  tmp = [[arr[j][i] for j in range(len(arr))]for i in range(len(arr[0]))]
  tmp = R(tmp)
  tmp = [[tmp[j][i] for j in range(len(tmp))]for i in range(len(tmp[0]))]
  return tmp
cnt = 0
while cnt <= 100:
  try:
    if arr[r-1][c-1] == k:
      print(cnt)
      break
  except IndexError:
    pass
  if len(arr) >= len(arr[0]):
    arr = R(arr)
  else:
    arr = C(arr)
  cnt += 1
else:
  print(-1)

배운 점;

딕셔너리를 정렬할 때에는 key, value, item을 정해서 key = lambda로 정렬해주면 된다.