[ BOJ / Python ] 17140번 이차원 배열과 연산


이번 문제는 그때 그때의 행과 열의 길이를 계산하여 R 연산과 C 연산을 주어진대로 구현하는 문제였다. 우선 defaultdict를 이용하여 행이나 열의 수들의 등장을 카운팅하고, defaultdict를 순회하며 key와 value를 튜플로 임시 리스트에 저장하고, 이 임시 리스트를 lambda를 이용하여 x[1], x[0]의 우선순위로 오름차순 정렬하였다. 그리고 임시 리스트를 순회하며 결과 리스트에 튜플의 언팩킹한 값을 넣어 한 줄의 정렬된 행이나 열을 만들어낸다. 이 과정을 전체 리스트를 돌아가며 진행하였다. 이때 최대 길이를 구하여 최대길이보다 작은 수만큼의 0을 리스트에 채워주었고, 0을 채운 후, 길이가 100 이상일 경우 100까지로 잘라주었다.

인덱스 에러가 계속 발생하였는데, 이는 a[r][c]를 검사하는 과정에서 행, 열의 길이가 r, c보다 작을 때 발생하는 것이었다. 이를 찾는 데에 시간이 꽤 소모되었다. 이 부분은 검사를 하기 전에 행과 열의 길이가 r, c보다 클 경우에만 a[r][c]를 검사하도록 하여 해결하였다.

  • r, c, k를 입력받는다.
  • a 리스트를 입력받는다.
  • r, c를 1씩 감소시킨다.
  • 결과를 저장할 변수 answer를 0으로 선언한다.
  • cul_r 함수를 선언한다.
    -> lst를 리스트로 선언한다.
    -> a의 길이만큼 반복하는 i에 대한 for문을 돌린다.
    --> d를 defaultdict(int)로 선언한다.
    --> a[0]의 길이만큼 반복하는 j에 대한 for문을 돌린다.
    ---> 만약 a[i][j]가 0일 경우, continue한다.
    ---> d[a[i][j]]를 1 증가시킨다.
    --> result를 리스트로 선언한다.
    --> d를 순회하는 key, value에 대한 for문을 돌린다.
    ---> result에 (key, value)를 넣는다.
    --> result를 key=lambda x: (x[1], x[0])를 이용하여 정렬한다.
    --> 임시 리스트 tmp를 선언한다.
    --> result를 순회하는 x, y에 대한 for문을 돌린다.
    ---> tmp에 [x, y]를 붙인다.
    --> lst에 tmp를 넣는다.
    -> 최대 길이를 저장할 변수 mx_l를 0으로 선언한다.
    -> lst의 길이만큼 반복하는 i에 대한 for문을 돌린다.
    --> mx_l을 mx_l과 len(lst[i]) 중 더 큰 값으로 갱신한다.
    -> lst의 길이만큼 반복하는 i에 대한 for문을 돌린다.
    --> lst[i]mx_l-len(lst[i])개의 [0]을 붙인다.
    --> 만약 len(lst[i])가 100보다 클 경우,
    ---> lst[i]lst[i][:100]으로 갱신한다.
    -> lst를 반환한다.
  • cul_c 함수를 선언한다.
    -> lst를 리스트로 선언한다.
    -> a의 길이만큼 반복하는 i에 대한 for문을 돌린다.
    --> d를 defaultdict(int)로 선언한다.
    --> a[0]의 길이만큼 반복하는 j에 대한 for문을 돌린다.
    ---> 만약 a[i][j]가 0일 경우, continue한다.
    ---> d[a[i][j]]를 1 증가시킨다.
    --> result를 리스트로 선언한다.
    --> d를 순회하는 key, value에 대한 for문을 돌린다.
    ---> result에 (key, value)를 넣는다.
    --> result를 key=lambda x: (x[1], x[0])를 이용하여 정렬한다.
    --> 임시 리스트 tmp를 선언한다.
    --> result를 순회하는 x, y에 대한 for문을 돌린다.
    ---> tmp에 [x, y]를 붙인다.
    --> lst에 tmp를 넣는다.
    -> 최대 길이를 저장할 변수 mx_l를 0으로 선언한다.
    -> lst의 길이만큼 반복하는 i에 대한 for문을 돌린다.
    --> mx_l을 mx_l과 len(lst[i]) 중 더 큰 값으로 갱신한다.
    -> lst의 길이만큼 반복하는 i에 대한 for문을 돌린다.
    --> lst[i]mx_l-len(lst[i])개의 [0]을 붙인다.
    --> 만약 len(lst[i])가 100보다 클 경우,
    ---> lst[i]lst[i][:100]으로 갱신한다.
    -> r_lst를 (len(lst[0])*len(lst))의 크기의 0으로 채워진 리스트로 선언한다.
    -> lst의 길이만큼 반복하는 i에 대한 for문을 돌린다.
    --> lst[0]의 길이만큼 반복하는 j에 대한 for문을 돌린다.
    ---> r_lst[j][i]lst[i][j]로 갱신한다.
    -> r_lst를 반환한다.
  • 계속 반복하는 while문을 돌린다.
    -> 만약 len(a)가 r보다 크고, len(a[0])가 c보다 클 경우,
    --> 만약 a[r][c]가 k일 경우,
    ---> while문을 종료한다.
    -> 만약 answer가 100이상일 경우,
    --> answer를 -1로 갱신한다.
    --> while문을 종료한다.
    -> 만약 len(a)len(a[0])보다 크거나 같을 경우,
    --> a를 cul_r()의 반환값으로 갱신한다.
    -> 그 외의 경우,
    --> a를 cul_c()의 반환값으로 갱신한다.
    -> answer를 1 증가시킨다.
  • answer를 출력한다.

Code

from collections import defaultdict
r, c, k=map(int, input().split())
a=[list(map(int, input().split())) for _ in range(3)]
r, c=r-1, c-1
answer=0
def cul_r():
    lst=[]
    for i in range(len(a)):
        d = defaultdict(int)
        for j in range(len(a[0])):
            if a[i][j]==0:
                continue
            d[a[i][j]]+=1
        result=[]
        for key, value in d.items():
            result.append((key, value))
        result.sort(key=lambda x: (x[1], x[0]))
        tmp=[]
        for x, y in result:
            tmp+=[x, y]
        lst.append(tmp)
    mx_l=0
    for i in range(len(lst)):
        mx_l=max(mx_l, len(lst[i]))
    for i in range(len(lst)):
        lst[i]+=[0]*(mx_l-len(lst[i]))
        if len(lst[i])>100:
            lst[i]=lst[i][:100]
    return lst
def cul_c():
    lst=[]
    for i in range(len(a[0])):
        d = defaultdict(int)
        for j in range(len(a)):
            if a[j][i]==0:
                continue
            d[a[j][i]]+=1
        result=[]
        for key, value in d.items():
            result.append((key, value))
        result.sort(key=lambda x: (x[1], x[0]))
        tmp=[]
        for x, y in result:
            tmp += [x, y]
        lst.append(tmp)
    mx_l = 0
    for i in range(len(lst)):
        mx_l = max(mx_l, len(lst[i]))
    for i in range(len(lst)):
        lst[i]+=[0]*(mx_l-len(lst[i]))
        if len(lst[i])>100:
            lst[i]=lst[i][:100]
    r_lst=[[0 for _ in range(len(lst))] for _ in range(len(lst[0]))]
    for i in range(len(lst)):
        for j in range(len(lst[0])):
            r_lst[j][i]=lst[i][j]
    return r_lst
while True:
    if len(a)>r and len(a[0])>c:
        if a[r][c]==k:
            break
    if answer>=100:
        answer=-1
        break
    if len(a)>=len(a[0]):
        a=cul_r()
    else:
        a=cul_c()
    answer+=1
print(answer)

좋은 웹페이지 즐겨찾기