[ProblemSolving] 백준 - 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을 출력한다.

예제 입력1

1 2 2
1 2 1
2 1 3
3 3 3

예제 출력1

0

예제 입력2

1 2 4
1 2 1
2 1 3
3 3 3

예제 출력2

52

나의 풀이

구현 문제

반복문을 쓰지 않고 2차원 리스트를 뒤집는 방법을 알게 되었다.

참고했습니다.

2차원 리스트 뒤집기 - zip

l = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
new_l = [[],[],[]]
for i in range(len(l)):
    for j in range(len(l)):
        new_l[i].append(l[j][i])

파이썬의 zip과 언패킹을 이용

l = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
new_l = list(map(list, zip(*l)))

zip

mylist = [1, 2, 3]
new_list = [40, 50, 60]
for i in zip(mylist, new_list):
    print (i)

#(1, 40)
#(2, 50)
#(3, 60)

풀이 순서

세로 길이 = length, 가로 길이 = width , 연산횟수 = cnt

1. while cnt <= 100 인 경우에 아래를 진행하고, cnt ==101이되면 cnt는 -1을 출력한다.
2. k값에 도달하면 break, 이때 length > c, width > r인 조건도 만족해야함
3. length >= width이면 r연산, 그렇지 않은 경우 c연산을 한다.
   이 때, c연산은 zip과 언패킹을 이용해 새 배열을 만들고, r연산 후, 그 배열을 다시 zip과 언패킹을 이용하여 정렬해준다.
4. r또는 c연산을 했으면 연산 횟수를 1초 증가시킨다.

r 연산 순서

sort(arr) : 배열을 파라미터로 받아서 r 연산된(r 정렬한) 새 배열을 리턴해주는 역할을 한다.

1. r연산된 배열을 저장할 temp 리스트를 초기화, 배열의 행 중 가장 큰 행의 사이즈를 저장할 idx 변수 초기화
2. arr 배열에서 한 행씩 꺼내서 다음과 같은 작업을 한다.
   • 그 행의 0이 아닌 원소와 그 원소의 등장 횟수를 딕셔너리에 저장한다.
   • 딕셔너리에는 key로 원소가, value에는 원소가 그 행에 등장한 횟수(갯수)가 저장된다.
   • 원소의 등장 횟수를 기준으로 오름차순으로 정렬한 결과를 a라는 새 리스트에 저장해준다.
   • tmp라는 새 리스트를 생성
   • a에서 각 한 쌍(key, value)씩 꺼내서, key와 value 순서대로 tmp에 추가하고, tmp의 사이즈의 최댓값을 idx에 저장한다.
   • tmp에 a의 모든 쌍을 저장했다면, temp에 tmp를 추가한다.
3. r연산된 결과가 temp에 옮겨지고,각 행의 길이가 idx보다 짧다면 0 패딩해준다.

알게 된 점

• 통과된 조건문

if width > c-1 and length > r-1 and arr[r-1][c-1] ==k:
        break

• 불통과된 조건문

if arr[r-1][c-1] ==k and width > c-1 and length > r-1 :
        break

코드 다시 짜보다가, 무지성으로 조건문 역순으로 짰더니 런타임 에러가 떴다. 그 이유는 k값과 같은 값이 있지만, width와 length가 조건을 만족하지 못하는 경우에 대한 예외처리가 조건문을 만족하지 못하기 때문이다.

테스트 케이스 6 참고

if문에도 순서가 있다는 걸 깜빡했다.

코드

r, c, k = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(3)]
cnt = 0

def sort(arr):
    temp = []
    idx = 0
    for width in arr:
        dic = dict()
        for i in width:
            if i>0:
                if i in dic:
                    dic[i] += 1
                else:
                    dic[i] = 1
        # 개수를 오름차순
        a = sorted(list(zip(dic.keys(), dic.values())), key = lambda x:(x[1], x[0]))
        a = a[0:100]
        tmp = []
        for i in a:
            tmp.append(i[0])
            tmp.append(i[1])
        idx = max(idx, len(tmp))
        temp.append(tmp)
    # 0 패딩
    for j in range(len(temp)):
        while len(temp[j]) != idx:
            temp[j].append(0)
    return temp

while cnt < 101:
    width = len(arr[0]) # 가로 길이
    length = len(arr) # 세로 길이
    
    if width > c-1 and length > r-1 and arr[r-1][c-1] ==k:
        break
    
    # r연산
    if length >= width:
        arr = sort(arr)
    # c 연산 
    else:
        arr = list(map(list, zip(*arr)))
        arr = sort(arr)
        arr = list(map(list, zip(*arr)))
    cnt += 1
    
if cnt == 101:
    cnt = -1
print(cnt)