[알고리즘] BOJ 17140 이차원 배열과 연산 #Python

김상현·2023년 6월 12일
0

알고리즘

목록 보기
301/301
post-thumbnail
post-custom-banner

[BOJ] 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을 출력한다.


📍 풀이

✏️ 문제해결 과정 중 학습한 내용

  • chain 메소드는 인자인 *args에 붙일 리스트들을 입력하여 붙여진 리스트를 얻을 수 있다.
from itertools import chain

data = [(1,3), (2,2), (4,1), (3,5)]
newData = list(chain(*data))
newData = [1, 3, 2, 2, 4, 1, 3, 5]
  • list(map(list, zip(*result))) 코드는 2차원 배열의 원소를 대각선 기준으로 대칭 이동시켜준다.
data = [[1,1,1,1],
		[2,2,2,2],
        [3,3,3,3]]
        
newData = list(map(list, zip(*data)))

newData = [[1,2,3],
		   [1,2,3],
           [1,2,3],
           [1,2,3]]

✍ 전체 코드

# BOJ 17140 이차원 배열과 연산
# https://www.acmicpc.net/problem/17140

from sys import stdin
from collections import defaultdict
from itertools import chain

def solution(r, c, k, A):
    
    def operationR(column, row):
        result = []
        maxLength = 0
        for y in range(row):
            weight = defaultdict(int)
            for x in range(column):
                if A[y][x]!=0: weight[A[y][x]] += 1
            result.append(list(chain(*sorted(weight.items(), key=lambda x : (x[1], x[0]))))[:100])
            maxLength = max(maxLength, len(weight)*2)
        for y in range(row):
            for _ in range(maxLength-len(result[y])):
                result[y].append(0)
        return result
            
    def operationC(column, row):
        result = []
        maxLength = 0
        for x in range(column):
            weight = defaultdict(int)
            for y in range(row):
                if A[y][x]!=0: weight[A[y][x]] += 1
            result.append(list(chain(*sorted(weight.items(), key=lambda x : (x[1], x[0]))))[:100])
            maxLength = max(maxLength, len(weight)*2)
        for x in range(column):
            for _ in range(maxLength-len(result[x])):
                result[x].append(0)
        return list(map(list, zip(*result)))

    for i in range(101):
        try:
            if A[r-1][c-1] == k: return i
        except:
            pass
        column, row = len(A[0]), len(A)
        A = operationR(column, row) if column <= row else operationC(column, row)
    return -1

r, c, k = map(int,stdin.readline().split())
A = list(list(map(int,stdin.readline().split())) for _ in range(3))

res = solution(r, c, k, A)
print(res)
profile
목적 있는 글쓰기
post-custom-banner

0개의 댓글