문제 링크
문제 설명
3*3 크기의 배열 A가 주어진다. 1초간 다음의 두 연산중 하나가 진행된다.
- R 연산 : A의 모든 행 정렬 (행개수 >= 열개수 인 경우)
- C 연산 : A의 모든 열 정렬 (행개수 < 열개수 인 경우)
이때 정렬 연산은 다음과 같다.
각각의 수가 각 행/열에 몇번 존재하는지 세고, 등장 횟수가 커지는 순으로 정렬한다. 수가 같으면 숫자가 커지는 순으로 정렬한다. 정렬된 결과는 수와 등장 횟수를 모두 포함한다.
예를들어 [3,1,1]은 3이 1번, 1이 2번 나오고, 등장 횟수가 커지는 순으로 정렬하면 [3,1,1,2]가 된다.
정렬 뒤 행렬의 크기가 달라지면, 크기는 가장 크기가 큰 행/열을 기준으로 하고, 빈 곳은 0으로 채운다. 이때 0은 정렬할때 세지 않는다. 행렬의 크기가 100이 넘어가면 처음 100를 제외한 나머지는 버린다. r,c,k와 행렬 A의 초기값이 주어질때, A[r][c]가 k가 될때까지 걸리는 시간의 최소값은?
문제 풀이
이 문제의 핵심 로직은 이차원 리스트에서 열을 읽어오는 list(zip(*A))이다. 역쉬 파이썬 매직~~~
입력을 받고, 함수를 부르는 main은 다음과 같다.
r,c,k = map(int, input().split())
A = []
for _ in range(3):
A.append(list(map(int, input().split())))
time = 0
while time <= 100:
# A[r][c] == k면
if len(A) >= r and len(A[0]) >= c and A[r-1][c-1] == k:
break
# R 연산할지 C 연산할지?
if len(A) >= len(list(zip(*A))):
A = operationR(A)
else:
A = operationC(A)
time += 1
if time > 100:
print(-1)
else:
print(time)R연산은 다음과 같이 구현하였다.
1.각 행마다 숫자의 등장 횟수 세기
이는 count dictionary를 선언해서 셌다.
for i in range(len(board)):
for j in range(len(board[i])):
if board[i][j] != 0:
if board[i][j] in count[i].keys():
count[i][board[i][j]] += 1
else:
count[i][board[i][j]] = 1- dictionary를 value기준 오름차순, key 기준 오름차순 정렬하기
maxlen = 0
for i in range(len(count)):
sort = sorted(count[i].items(), key= lambda x:[x[1], x[0]])
board[i] = []
for s in sort:
board[i] += list(s)
if len(board[i]) > 100:
board[i] = board[i][:100]
maxlen = max(maxlen, len(board[i]))- 2에서 찾은 행 길이의 최대값 기준으로 0 append 해주기
if len(board) > 100:
board = board[:100]
for b in board:
if len(b) < maxlen:
for i in range(maxlen-len(b)):
b.append(0)C연산의 로직은 R연산과 동일하다. parameter로 받은 board를 list(*zip(board))로 행-열을 바꿔서 계산하고, 이를 다시 행-열 바꿔서 리턴해주면 된다.
전체 코드
전체 코드는 다음과 같다.
import sys
input = sys.stdin.readline
r,c,k = map(int, input().split())
A = []
for _ in range(3):
A.append(list(map(int, input().split())))
time = 0
def operationR(board):
# board의 모든 행 정렬하기
count = [{} for _ in range(len(board))] # board의 각 행 숫자 등장 횟수 count
# 1. 등장 횟수 count
for i in range(len(board)):
for j in range(len(board[i])):
if board[i][j] != 0:
if board[i][j] in count[i].keys():
count[i][board[i][j]] += 1
else:
count[i][board[i][j]] = 1
# 2. dic을 value 기준 오름차순, key 기준 오름차순 정렬하기
maxlen = 0
for i in range(len(count)):
sort = sorted(count[i].items(), key= lambda x:[x[1], x[0]])
board[i] = []
for s in sort:
board[i] += list(s)
if len(board[i]) > 100:
board[i] = board[i][:100]
maxlen = max(maxlen, len(board[i]))
# 3. 최대값 기준으로 0 append 해주기 -> 길이 맞추려고 & 100개 넘어가면 버리기
if len(board) > 100:
board = board[:100]
for b in board:
if len(b) < maxlen:
for i in range(maxlen-len(b)):
b.append(0)
return board
def operationC(board):
# board의 모든 열 정렬하기
new_board = []
for b in list(zip(*board)):
new_board.append(list(b))
count = [{} for _ in range(len(new_board))] # board의 각 행 숫자 등장 횟수 count
# 1. 등장 횟수 count
for i in range(len(new_board)):
for j in range(len(new_board[i])):
if new_board[i][j] != 0:
if new_board[i][j] in count[i].keys():
count[i][new_board[i][j]] += 1
else:
count[i][new_board[i][j]] = 1
# 2. dic을 value 기준 오름차순, key 기준 오름차순 정렬하기
maxlen = 0
for i in range(len(count)):
sort = sorted(count[i].items(), key= lambda x:[x[1], x[0]])
new_board[i] = []
for s in sort:
new_board[i] += list(s)
if len(new_board[i]) > 100:
new_board[i] = new_board[i][:100]
maxlen = max(maxlen, len(new_board[i]))
# 3. 최대값 기준으로 0 append 해주기 -> 길이 맞추려고
if len(new_board) > 100:
new_board = new_board[:100]
for b in new_board:
if len(b) < maxlen:
for i in range(maxlen-len(b)):
b.append(0)
# 4. 얘를 다시 행렬 바꿔서 리턴
board = []
for b in list(zip(*new_board)):
board.append(list(b))
return board
while time <= 100:
# A[r][c] == k면
if len(A) >= r and len(A[0]) >= c and A[r-1][c-1] == k:
break
# R 연산할지 C 연산할지?
if len(A) >= len(list(zip(*A))):
A = operationR(A)
else:
A = operationC(A)
time += 1
if time > 100:
print(-1)
else:
print(time)
100이 넘어가면 -1일인데 조건을 time<100으로 줘서 계속 틀렸습니다가 났다,, 문제 꼼꼼히 읽기
소요 시간
1시간 10분
Hongik CE