[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)