[Python] 백준 17140번: 이차원 배열과 연산

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

17140번: 이차원 배열과 연산

 

 > 풀이

list가 주어졌을 때 이것의 정렬 함수를 먼저 구현해야한다. 이것은 딕셔너리로 0을 제외한 숫자들을 카운트해준 뒤 정렬을 2번 해주면 된다.

이제 도전과제는 C연산이다. 아래와 같은 리스트를 가정해보자.

C연산을 해줬을 때 결과는 다음과 같다.

[1,2] -> [1,1,2,2]

[2,1] -> [1,1,2,2]

[3,3] -> [3,2,0,0]

이 때 문제점은 두 가지다. 첫번째는 [1,2,3]처럼 묶여있는 것을 세로로 다시 묶어야 한다는 점이며, 두번째는 [1,1,2,2]와 같은 결과를 얻었을 때 이것을 다시 세로로 돌려서 저장해야 한다는 점이다.

첫번째 문제는 zip을 이용해서 쉽게 해결할 수 있다. [[1,2,3],[2,1,3]]에서 [1,2]을 구하려면 list(zip(*matrix))[0]을 해주면 된다. *matrix를 통해 리스트를 풀어준 뒤, zip을 이용해서 1 - 2, 2 - 1, 3 - 3을 묶어주었으며 마지막으로 리스트화한 뒤 인덱스로 접근하여 값을 얻어낸 것이다.

다음으로 두번째 문제에 대해 설명한다. 위 예시에서 정렬 과정을 거쳐서 [[1,1,2,2],[1,1,2,2],[3,2,0,0]]을 얻었다고 해보자. 그럼 이것을 다음과 같이 돌려주어야 한다.

이것 또한 zip을 이용한 rotation으로 쉽게 해결할 수 있다. list(zip(*matrix)) 한 줄로 바로 회전이 되며, 그 원리는 위에서 설명한 바와 완전히 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
input = sys.stdin.readline

def get_sorted_list(nums):
  num_to_count = defaultdict(int)
  for num in nums:
    if num == 0: continue
    num_to_count[num] += 1
                                            
  num_to_count = list(num_to_count.items())   
  num_to_count.sort(key = lambda x:x[0])
  num_to_count.sort(key = lambda x:x[1])   
                                          
  return [num_to_count[i][j] for i in range(len(num_to_count)) for j in range(2)]
                             

if __name__ == '__main__':
  r, c, k = map(int, input().split())
  r -= 1
  c -= 1
  matrix = [list(map(int, input().split())) for _ in range(3)]
               
  for i in range(101):    
    width = len(matrix[0])
    height = len(matrix)    
    if r <= height-1 and c <= width-1 and matrix[r][c] == k:
      break

    # 한 줄씩 정렬해서 lines에 담음
    lines = []             
    next_width = 0
    next_height = 0
    if height >= width:
      next_height = height

      for i in range(height):
        lines.append(get_sorted_list(matrix[i]))
        next_width = max(next_width, len(lines[-1]))
    else:                          
      next_height = width

      for j in range(width):             
        lines.append(get_sorted_list(list(zip(*matrix))[j]))    
        next_width = max(next_width, len(lines[-1]))   

    # lines를 matrix에 적용
    matrix = [[0]*next_width for _ in range(next_height)]
    for i in range(next_height):
      for j in range(len(lines[i])):
        matrix[i][j] = lines[i][j]
                   
    # r < c일 경우 돌리기 
    if height < width:       
      matrix = list(zip(*matrix))    
      
    # 크기가 100을 넘길 경우 버리기  
    if next_width > 100:
      for i in range(next_height):
        matrix[i] = matrix[i][:100]
    if next_height > 100:
      matrix = matrix[:100]
  else:
    i = -1
      
  print(i)