BAEKJOON #17140 이차원 배열과 연산 (sorting) - python
이차원 배열과 연산
출처 : 백준 #17140
시간 제한 | 메모리 제한 |
---|---|
0.5초(추가 시간 없음) | 512MB |
문제
크기가 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을 출력한다.
입출력 예시
예제 입력 1
1 2 2
1 2 1
2 1 3
3 3 3
예제 출력 1
0
예제 입력 2
1 2 1
1 2 1
2 1 3
3 3 3
예제 출력 2
1
예제 입력 3
1 2 3
1 2 1
2 1 3
3 3 3
예제 출력 3
2
예제 입력 4
1 2 4
1 2 1
2 1 3
3 3 3
예제 출력 4
52
예제 입력 5
1 2 5
1 2 1
2 1 3
3 3 3
예제 출력 5
-1
예제 입력 6
3 3 3
1 1 1
1 1 1
1 1 1
예제 출력 6
2
풀이
생각 및 풀이 설명
- 2중 for문 중 두 번째 for문을 돌면서 임시 딕셔너리에 있으면 +1을 해주고, 없으면 1로 초기값을 만들어준다.
- 두 번째 for문을 다 돌면 딕셔너리의 value, key 순으로 내림차순으로 정렬한다.
- 정렬된 리스트를 돌면서 임시 리스트에 넣어준 뒤 matrix(원래 이차원 배열)에 넣어준다.
- 이 때 임시 리스트의 길이를 재면서 최대 길이를 뽑아낸다 (
max_len
) - 그 뒤
max_len
보다 길이가 짧은 임시 리스트에는 0을 그 차이만큼 추가한다. - while문 탈출 한 뒤 sec 이 100초를 넘기면 -1을 출력하고, 아니라면 sec을 출력한다.
python code (처음 풀이 - 메모리 초과)
# 백준 17140번 이차원 배열과 연산
from sys import stdin
input = stdin.readline
r, c, k = map(int, input().split())
matrix = []
for _ in range(3):
matrix.append(list(map(int, input().split())))
sec = 0
r -= 1
c -= 1
while (sec <= 100):
if len(matrix) - 1 >= r and len(matrix[0]) -1 >= c:
if matrix[r][c] == k:
break
sec += 1
# col_len, row_len
col_len = len(matrix)
row_len = len(matrix[0])
flag = ""
max_len = 0
if col_len >= row_len: # R 연산
flag = "R"
for i in range(col_len):
temp_dict = {}
for j in range(row_len):
temp = matrix[i][j]
if temp != 0:
if temp_dict.get(temp):
temp_dict[temp] += 1
else:
temp_dict[temp] = 1
temp = list(sorted(temp_dict.items(), key=lambda x:(x[1], x[0]))) # value가 작은 순, 그 다음으로 key가 작은 순
temp_arr = []
for key, value in temp:
temp_arr.append(key)
temp_arr.append(value)
matrix[i] = temp_arr
max_len = max(max_len, len(temp_arr))
else: # C 연산
flag = "C"
temp_matrix = []
for i in range(row_len):
temp_dict = {}
for j in range(col_len):
temp = matrix[j][i]
if temp != 0:
if temp_dict.get(temp):
temp_dict[temp] += 1
else:
temp_dict[temp] = 1
temp = list(sorted(temp_dict.items(), key=lambda x:(x[1], x[0]))) # value가 작은 순, 그 다음으로 key가 작은 순
temp_arr = []
for key, value in temp:
temp_arr.append(key)
temp_arr.append(value)
temp_matrix.append(temp_arr)
max_len = max(max_len, len(temp_arr))
matrix = temp_matrix
col_len = len(matrix)
row_len = max_len
for i in range(col_len):
for j in range(row_len):
temp_len = len(matrix[i])
if temp_len < max_len:
sub = max_len - temp_len
for s in range(sub):
matrix[i].append(0)
if flag == "C": # "C" (row, col change)
temp_matrix = [[0 for _ in range(col_len)] for _ in range(row_len)]
for i in range(col_len):
for j in range(row_len):
temp_matrix[j][i] = matrix[i][j]
matrix = temp_matrix
if sec > 100:
print(-1)
else:
print(sec)
Author And Source
이 문제에 관하여(BAEKJOON #17140 이차원 배열과 연산 (sorting) - python), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@nathan29849/BAEKJOON-17140-이차원-배열과-연산-sorting-python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)