문제
크기가 3×3인 배열 A가 있다. 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을 출력한다.
접근
해당 문제는 조건대로 정렬 후에 2차원 리스트를 어떻게 갱신할지 생각해야했다.
먼저 행과 열의 개수에 따라 정렬을 수행해야하는 위치가 달라진다. 먼저 행을 기준으로 보자.
각각의 수가 몇 번 나왔는지 알 수 있어야하고 이를 기준으로 정렬을 해야한다.
또한 행에서 최대길이가 6이 되었을 때 다른 행에 4개의 수만 넣는다면 뒤에 0을 두개 넣어줘야한다.
이를 위해 counter 리스트를 선언하여 각 숫자가 몇 번 나왔는지 체크한다. 이후 counter를 탐색하여 0이 아닌 수가 들어있을 때 해당 수와 횟수를 해당 행에 대한 리스트에 넣어준다.
이후 이 리스트를 sort한다.
모든 행에 대해 위와 같은 과정을 거친 후에 수와 횟수가 들어있는 것을 해당 행에 꺼내어 2차원 리스트를 갱신한다.
이때 최대 길이보다 작을 때는 뒤에 남은 수만큼 0을 넣어주도락 한다.
이 과정이 끝나면 열의 개수가 변경되기 때문에 최대 길이를 열의 값으로 갱신한다.
구현
- 매 초마다 연산을 진행하고 100초가 넘어갔을 때 반복문을 종료한다.
- 또한 입력받은 R, C 위치에 K라면 종료한다.
time = 0
while time <= 100:
if board[R][C] == K:
break
solve()
time += 1- solve함수에서 rows와 cols의 개수에 따라 나눠서 진행한다. 행을 기준으로 보자.
- max_len은 이후에 0을 뒤에 넣어야하는지와 열의 값을 업데이트하는데 사용된다.
- temp는 각 행에 들어가야할 수를 넣어준다.
- 이제 각 행에서 수를 탐색하면서 counter 리스트에 해당 수가 몇 번나왔는지 넣어준다.
- 이후 1부터 max_number까지 temp에 해당 수와 횟수를 넣어준다.
- 위 과정이 모두 끝났다면 이차원 리스트의 값을 갱신해야한다.
- 행을 순서대로 temp의 값을 꺼내어 원본 리스트인 board에 넣어준다.
- 만약 다 넣었는데 idx가 max_len 미만이라면 뒤에 차이만큼 0을 넣어준다.
- 열도 위의 과정을 거친다.
def solve():
global rows, cols
if rows >= cols:
max_len = 0
temp = [[] for _ in range(101)]
for i in range(1, rows+1):
max_number = 0
counter = [0 for _ in range(101)]
for j in range(1, cols+1):
max_number = max(max_number, board[i][j])
counter[board[i][j]] += 1
count = 0
for k in range(1, max_number+1):
if counter[k]:
temp[i].append((k, counter[k]))
count += 2
max_len = max(max_len, count)
temp[i] = sorted(temp[i], key= lambda x: (x[1], x[0]))
cols = max_len
for i in range(1, rows+1):
idx = 1
for a, b in temp[i]:
board[i][idx], board[i][idx+1] = a, b
idx += 2
if max_len - idx > 0:
for j in range(idx, max_len+1):
board[i][j] = 0
else:
max_len = 0
temp = [[] for _ in range(101)]
for i in range(1, cols + 1):
max_number = 0
counter = [0 for _ in range(101)]
for j in range(1, rows + 1):
max_number = max(max_number, board[j][i])
counter[board[j][i]] += 1
count = 0
for k in range(1, max_number + 1):
if counter[k]:
temp[i].append((k, counter[k]))
count += 2
max_len = max(max_len, count)
temp[i] = sorted(temp[i], key=lambda x: (x[1], x[0]))
rows = max_len
for i in range(1, cols + 1):
idx = 1
for a, b in temp[i]:
board[idx][i], board[idx+1][i] = a, b
idx += 2
if max_len - idx > 0:
for j in range(idx, max_len + 1):
board[j][i] = 0전체 코드
import sys
input = sys.stdin.readline
def solve():
global rows, cols
if rows >= cols:
max_len = 0
temp = [[] for _ in range(101)]
for i in range(1, rows+1):
max_number = 0
counter = [0 for _ in range(101)]
for j in range(1, cols+1):
max_number = max(max_number, board[i][j])
counter[board[i][j]] += 1
count = 0
for k in range(1, max_number+1):
if counter[k]:
temp[i].append((k, counter[k]))
count += 2
max_len = max(max_len, count)
temp[i] = sorted(temp[i], key= lambda x: (x[1], x[0]))
cols = max_len
for i in range(1, rows+1):
idx = 1
for a, b in temp[i]:
board[i][idx], board[i][idx+1] = a, b
idx += 2
if max_len - idx > 0:
for j in range(idx, max_len+1):
board[i][j] = 0
else:
max_len = 0
temp = [[] for _ in range(101)]
for i in range(1, cols + 1):
max_number = 0
counter = [0 for _ in range(101)]
for j in range(1, rows + 1):
max_number = max(max_number, board[j][i])
counter[board[j][i]] += 1
count = 0
for k in range(1, max_number + 1):
if counter[k]:
temp[i].append((k, counter[k]))
count += 2
max_len = max(max_len, count)
temp[i] = sorted(temp[i], key=lambda x: (x[1], x[0]))
rows = max_len
for i in range(1, cols + 1):
idx = 1
for a, b in temp[i]:
board[idx][i], board[idx+1][i] = a, b
idx += 2
if max_len - idx > 0:
for j in range(idx, max_len + 1):
board[j][i] = 0
R, C, K = map(int, input().split())
rows = cols = 3
board = [[ 0 for _ in range(101)] for _ in range(101)]
for i in range(1, 4):
board[i][1], board[i][2], board[i][3] = map(int, input().split())
time = 0
while time <= 100:
if board[R][C] == K:
break
solve()
time += 1
if time > 100:
time = -1
print(time)'알고리즘 풀이 > 백준' 카테고리의 다른 글
| [백준 10025] 게으른 백곰 (0) | 2021.07.18 |
|---|---|
| [백준 19238] 스타트 택시 (0) | 2021.07.18 |
| [백준 14503] 로봇 청소기 (0) | 2021.07.16 |
| [백준 17837] 새로운 게임2 (0) | 2021.07.16 |
| [백준 3190] 뱀 (0) | 2021.07.14 |