문제 이해
문제
크기가 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을 출력한다.
아래의 예시를 보면 아마 완벽히 이해가 될 것이다.
문제 접근
나는 우선 문제를 보고 3가지 단계로 나누었다.
- (숫자, 개수) 쌍으로 나타낼 방법 찾기
- 이를 정렬하기
- R과 C일 때 어떻게 할것인가?
문제 풀이
(숫자, 개수) 쌍으로 나타낼 방법 찾기
dic = dict()나는 파이썬의 dictionary 자료형을 사용해서 숫자와 개수 쌍으로 나타내었다.
dic에 현재까지 들어가 있지 않은 수라면 초기화를 통해 dic[숫자] = 1로 만들어주고, 만약 있다면 +1을통해 개수를 셌다.
이렇게 센 개수를 숫자와 개수를 쌍으로 묶어 B라는 리스트에 넣었다.
for i in range(len(matrix)):
B = []
dic = dict()
for j in range(len(matrix[i])):
if matrix[i][j]!=0:
if matrix[i][j] not in dic:
dic[matrix[i][j]] = 1
else: dic[matrix[i][j]] += 1
for key,value in dic.items():
B.append([key,value])이를 정렬하기
이를 정렬하는 것은 쉽다. 바로 파이썬의 lambda를 사용하면 된다. 아래 코드를 보자.
sort를 통해 개수를 1순위, 그 다음 숫자를 2순위로 하여 정렬해주었다.
이렇게 정렬한 2차원 배열을 1차원으로 변환하고 그 최대 길이를 max_count에 저장하여 추후에 다른 행들을 변환 해줄 때 기준으로 삼는다.
이제 sorted_matrix에 순서대로 C를 append하면 정렬한 값들이 알맞게 들어간다.
B.sort(key=lambda x: [x[1],x[0]])
C = sum(B,[])
max_count = max(max_count,len(C))
sorted_matrix.append(C)R과 C일 때 어떻게 할것인가?
근데 사실 지금까지 내가 말한 방식은 R방식이다. C는 조금 더 복잡하다.
나는 R부터 구현한 뒤에 어떻게 하면 C를 구현할 수 있을까? 에 대해서 생각을 오래했던 것 같다.
그러다 파이썬의 zip()내장함수를 알게 되었다.
zip(*matrix)를 하면 matrix의 열을 행으로 바꾸어주는 내장함수이다.
만약 [[0,0,0], [1,1,1], [2,2,2]]를 zip하면 [(0,1,2),(0,1,2),(0,1,2)]로 바뀌게된다.
나는 이 방식을 사용했다.
sort_new라는 함수를 선언할 때 아래와 같이 선언하고
def sort_new(matrix, RC):main함수에서 sort_new의 파라미터에 정렬할 matrix와 R또는 C를 넣어주었다.
if len(A)>=len(A[0]):
#R연산
A = sort_new(A,"R")
else :
# C연산
A = sort_new(list(zip(*A)),"C")sort_new에서 최종적으로 0을 추가하고 만약 그 길이가 100을 넘는다면 슬라이싱해주었다.
matrix를 전부 정렬 완료하고 이를 return할 때 만약 처음에 파라미터에 C로 들어왔다면 A = sort_new(list(zip(A)),"C")에 의해 호출되었기 때문에 A를 다시 zip하여 원래대로 되돌려야 한다. 따라서 return list(zip(sorted_matrix))해준다.
for i in sorted_matrix:
i+=[0]*(max_count-len(i)) # 가장 긴 길이에 맞춰서 0 추가
if len(i)>100:
i = i[:100]
return sorted_matrix if RC=="R" else list(zip(*sorted_matrix))제출 코드
import sys
r,c,k = map(int, sys.stdin.readline().split())
A = [list(map(int, sys.stdin.readline().split())) for _ in range(3)]
def sort_new(matrix, RC):
sorted_matrix = []
max_count = 0
for i in range(len(matrix)):
B = []
dic = dict()
for j in range(len(matrix[i])):
if matrix[i][j]!=0:
if matrix[i][j] not in dic:
dic[matrix[i][j]] = 1
else: dic[matrix[i][j]] += 1
for key,value in dic.items():
B.append([key,value])
B.sort(key=lambda x: [x[1],x[0]])
C = sum(B,[])
max_count = max(max_count,len(C))
sorted_matrix.append(C)
for i in sorted_matrix:
i+=[0]*(max_count-len(i)) # 가장 긴 길이에 맞춰서 0 추가
if len(i)>100:
i = i[:100]
return sorted_matrix if RC=="R" else list(zip(*sorted_matrix))
result = 0
while True:
count = 0
if result >=101:
result = -1
break
if r-1<len(A) and c-1<len(A[0]):
if A[r-1][c-1] == k:
break
if len(A)>=len(A[0]):
#R연산
A = sort_new(A,"R")
else :
# C연산
A = sort_new(list(zip(*A)),"C")
result += 1
print(result)