백준 17140 이차원 배열과 연산 (Python)

문제

출처: https://www.acmicpc.net/problem/17140

 

 

나의 접근법

먼저 행과 열의 최대길이를 구분하여 계산합니다.

 

R 연산 

checkList 배열에 [숫자, 개수]를 함께 묶어 저장하여 not in으로 중복을 해결했습니다.

정렬은 sort함수의 lambda를 사용했습니다.

행이나 열의 최대 길이는 maxLen을 통해 값을 저장하여 maxLen 보다 작은 행 또는 열의 길이를 가진 경우 차이만큼 0을 추가해줍니다.

 

C 연산

반복문으로 열을 바로 계산하면 R x C 만큼 더 늘어나야 하므로 

for i in range(clen):
    checkList = []
    col = list(zip(*arr))[i]

열 마다 zip 함수를 이용하여 편하게 행으로 바꿔 작업하였습니다.

행 연산 보다 추가로 고려해야 될 것은 행은 바로 붙일 수 있지만 열은 공간이 미리 있어야 가능해서 제 코드에서는 0을 채울 수 있는 공간 미리 확보해야만 했습니다. 그래서 appendList라는 deque를 만들어 행으로 바꿔 계산한 열을 저장하고 이를 각 열의 maxLen 차이 만큼 0을 추가했습니다.

 

첫번째 제출 코드 (오답)

from collections import deque
r, c, k = map(int, input().split())
arr = []
r, c= r-1, c-1
ans = 0
for i in range(3):
    arr.append(list(map(int, input().split())))
while True:
    if arr[r][c] == k:
       print(ans)
       break
    if ans > 100:
        print(-1)
        break
    ans += 1

#R 연산
    if rlen >= clen:
        maxLen = -1
        for i in range(rlen):
            checkList = []
            for j in range(clen):
                num = arr[i][j]
                if num > 0:
                    if [num, arr[i].count(num)] not in checkList:
                        checkList.append([num, arr[i].count(num)])

            checkList.sort(key=lambda x: (x[1], x[0]))
            arr[i] = sum(checkList, [])
            maxLen = max(maxLen, len(arr[i]))

        # 0으로 채우기
        for i in range(rlen):
            if len(arr[i]) < maxLen:
                arr[i] = arr[i] + [0] * (maxLen - len(arr[i]))
        clen = maxLen

#c 연산
    else:
        maxLen = -1
        appendList = deque([])
        for i in range(clen):
            checkList = []
            col = list(zip(*arr))[i]
            for j in range(rlen):
                num = col[j]
                if num > 0:
                    if [num, col.count(num)] not in checkList:
                        checkList.append([num, col.count(num)])
            checkList.sort(key=lambda x: (x[1], x[0]))
            col = sum(checkList, [])
            maxLen = max(maxLen, len(col))

            #for j in range(len(col))
            appendList.append(col)

        # maxLen과 같게 행 추가
        if rlen < maxLen:
           arr = arr + [[0] * clen for _ in range(maxLen - rlen)]

        idx = 0
        for i in range(len(appendList)):
            col = appendList[i]

            #0으로 채우기
            #if len(col) < maxLen:
                #col = col + [0] * (maxLen - len(col))
            for j in range(len(col)):
                arr[j][i] = col[j]

    # 0으로 채우기
        for i in range(clen):
            if len(appendList[i]) < maxLen:
                for j in range(len(appendList[i]), maxLen):
                    arr[j][i] = 0

        rlen = maxLen

제 첫번째 코드입니다. 위 코드는 행은 제대로 연산을 하지만 열에서 에러가 발생하고 계속 제 코드를 수정하려고 했지만 그럴수록 다음 예제에서 계속 걸려 넘어졌습니다. 그래서 결국 검색의 도움을 받기로 했습니다.

 

정답 코드

from collections import deque
def compute():
    rlen = len(arr)
    clen = len(arr[0])
    maxLen = -1
    for i in range(rlen):
        checkList = []
        for j in range(clen):
            num = arr[i][j]
            if num > 0:
                if [num, arr[i].count(num)] not in checkList:
                    checkList.append([num, arr[i].count(num)])

        checkList.sort(key=lambda x: (x[1], x[0]))
        arr[i] = sum(checkList, [])
        maxLen = max(maxLen, len(arr[i]))

    # 0으로 채우기
    for i in range(rlen):
        if len(arr[i]) < maxLen:
            # for j in range()
            # arr[i].append()
            arr[i] = arr[i] + [0] * (maxLen - len(arr[i]))
    return

r, c, k = map(int, input().split())
#arr = [[0]*(3) for _ in range(3)]
arr = []
r, c= r-1, c-1
ans = 0
#rlen, clen = 3, 3
for i in range(3):
    arr.append(list(map(int, input().split())))
while True:
    try:
        if arr[r][c] == k:
            print(ans)
            break
    except:pass

    if ans > 100:
        print(-1)
        break
    ans += 1

#R 연산
    if len(arr) >= len(arr[0]):
        compute()
    # c 연산
    else:
        arr = list(zip(*arr))
        compute()
        arr = list(zip(*arr))

검색을 하고 제 코드와의 차이점을 단번에 알아챌 수 있었습니다. 최대한 불필요한 반복은 버리고 zip함수를 이용하여 바로 열까지 커버를 쳤습니다.

 

후기

이번 문제를 통해 새롭게 알게 된 것이 너무 많아서 개인적으로 완벽하게 풀지는 않았지만 몇 시간 내내 고민하고 괴로워 했던 고통들이 다 날아갔습니다.

1. 일단 zip으로 2차원 배열 전체의 행과 열을 바꿀 수 있다는 것을 깨달았습니다. 저는 numpy 모듈을 불러와야지만 가능한 줄 알았는데 zip 함수 하나로 해결할 수 있었습니다.
2. 이건 제가 아직 많이 부족하다는 증거이기도 한데 저는 행의 길이와 열의 길이를 2차원에서는 찾지 못했습니다. 정사각 배열에서 len(arr[0])은 열의 길이를 나타내고 len(arr)은 행의 길이를 나타내는 것을 새롭게 알았습니다.
3. 배열이 처음에는 3x3이라 3초 뒤의 A[3][3]의 값을 접근할 경우 에러가 발생하는데 이를 try except 문으로 바로 커버하는 것을 보고 예전에 배웠던 try except 을 활용하는 방법까지 배웠습니다. 

파이썬에서 가장 큰 장점 중 하나인 내장 함수의 강력함에 다시 한 번 놀랐습니다. 특히 zip은 정말 유용하고 편리한 함수인 것 같습니다.