[python] BOJ 백준 17140: 이차원배열과연산

1. 문제  

크기가 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가 되기 위한 최소 시간을 구해보자.

2. 입력   

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

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

3. 출력   

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

4. 해결방법   

이 문제는 구현, 시뮬레이션 문제이다. R연산과 C연산을 각각 만들어준다기보다는 zip함수를 이용해서 행과열을 전환하고 계산후 다시 전환해주는 것이 좋다. 각각의 수가 몇번나왔는지 알기위해서는 파이썬의 counter 모듈을 사용하면 편하고, 0일때는 무시하므로 0이 아닐 때만 임시배열에 저장해주면된다. 연산함수를 100초동안 반복하면서 해당 조건을 만족하는지 검사해주면되는데, 이때 주의할점은 100초까지이므로 for문을 101번 돌려서 100번의 연산에 대한 검사를 해주어야한다. 

1) cal 함수: 연산후 최대길이를 저장하고 있어야 모자란 길이 만큼을 0으로 채울수 있다. 또한 문제에서 100개까지만 반영한다고 하였으므로 인덱싱해주어야한다. 파이썬의 counter라이브러리와 sort함수를 이용한다면 문제에서 원하는 연산을 할 수 있다.  

5) 구현코드   

from collections import Counter
r,c,k=map(int,input().split())
board=[list(map(int,input().split()))for _ in range(3)] #이차원배열 

#연산 함수 
def cal(board):
  temp=[[] for _ in range(len(board))] #임시배열 
  max_len=0 #연산 후 최대길이 
  for i in range(len(board)):
    c=Counter(board[i]).most_common() #숫자등장횟수 
    c.sort(key=lambda x:(x[1],x[0])) #등장횟수대로 정렬
    for a,b in c:
      if a!=0: #0이아닐경우에는 
        temp[i].append(a) #차례대로 입력 
        temp[i].append(b)
    max_len=max(max_len,len(temp[i])) #최대길이 업데이트 
  for i in range(len(board)):
    if len(temp[i])!=max_len: #최대길이모자라면 
      cnt=max_len-len(temp[i])
      for _ in range(cnt):
        temp[i].append(0) #0으로채우기 
    temp[i]=temp[i][:100] #100개까지만 반영 
  return temp

#100초까지 탐색 
for i in range(101):
  try:
    #조건 만족하면 
    if board[r-1][c-1]==k:
      print(i) #시간 출력 
      break
  except: pass
  #C연산 
  if len(board)<len(board[0]):
    board = list(zip(*board))
    board=cal(board)
    board = list(zip(*board))
  else:#R연산 
    board=cal(board)
else: #100초지나도 조건이 안만족할경우
  print(-1)

 

⭐️난이도:  골드 4 ⭐️

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

17140번: 이차원 배열과 연산