백준 17140 이차원 배열과 연산 파이썬

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

17140번: 이차원 배열과 연산

처음 이 문제를 봤을때 dic를 쓸까 생각했지만 사용하기 어려워 list와 set을 사용해 풀었다.

시간초과나 메모리초과가 나오는 것인지 떨리면서 제출했는데 생각보다 시간이 별로 안 걸려서 놀랐다.

여러 시행착오가 있었지만 AC받았다.

실수 1. dp배열에 크기를 작게 해줘서 index에러가 났다. K<=100번이니 dp배열의 크기를 101로 해줬더니 에러가 안 났다.

실수 2. C연산에서 변경하고 남은 밑에 열을 0으로 초기화 해주지 않아서 잘못된 답이 나왔다. 초기화 해주니 알맞은 답이 나왔다.

def R(s): #R연산을 해주는 함수
    maxs=-1#행의 길이의 최댓값
    for i in range(len(s)):
        s2=[]#정렬된 리스트가 담길 리스트
        c=0#행의 길이
        for k in set(s[i]):#시간 복잡도를 줄이기 위해 set을 사용
            if k!=0:
                s2.append([s[i].count(k),k])#s[i]배열에 있는 k의 개수를 k와 함께 저장. 
        s2.sort()#정렬된 상태로 집어 넣으니 정렬해줌
        s[i]=[]#인덱스 하나하나 바꿔주는 방법도 있으나 시간 복잡도상으로 append를 써도 돼 빈리스트로 만든 뒤 추가해줌
        for o in s2:#s2에는 [[k개수,k],...,[k개수,k]]상태로 저장돼있음
            s[i].append(o[1])#정렬은 [k,k개수]이런 형식으로 정렬되니 저런 작업을 해줌
            s[i].append(o[0])
            c+=2#행의 길이가 2만큼 늘어나니 +2
        maxs = max(maxs,c)#최댓값 갱신
    for i in range(len(s)):
        s[i]+=[0]*(maxs-len(s[i]))#최댓값에 비해 부족한 길이를 더해줌


def C(s):#C연산을 해주는 함수
    t = len(s)#열의 길이가 달라질 수 있으니 변수로 저장
    dc = len(s[0])#행의 길이가 달라질 수 있으니 변수로 저장
    re=[]#행과 달리 append를 못 쓰고 index하나하나에 접근해야 함으로 정렬된 값을 저장해주는 리스트
    maxs=-1#열의 길이의 최댓값
    for i in range(len(s[0])):
        re.append([])
        s2=[]
        dp=[0]*(101)#숫자가 몇번 나오는지 count하기 위해 만든 배열
        for j in range(t):#열 탐색
            if s[j][i]!=0:
                s2.append(s[j][i])#뭔 숫자가 있는지 더해줌 나중에 set을 사용해 dp에 접근할것이기 때문
                dp[s[j][i]]+=1 #count해줌
               
                
        sre = set(s2)
        
        for k in sre:
            re[i].append([dp[k],k])#R함수와 같은 원리로 정렬시켜 저장해줌
        re[i].sort()
        maxs = max(maxs,len(sre))#열의 최댓값
       
    for _ in range(2*maxs-len(s)):#2*maxs인 이유 len(sre)가 1개가 늘어나면 열은 2개가 필요함
        s.append([0]*dc)# [0]*행의 최대 길이인으로 채워진 열을 행을 추가해 열의 길이를 늘려줌 
    
    for i in range(dc):
        for j,k in enumerate(re[i]):#enumerate를 사용해 index에 접근후 저장된 값으로 변경
            s[j*2][i]=k[1]
            s[j*2+1][i]=k[0]
        for k in range(j*2+2,len(s)):#위에 변경했는데 이전 정보가 남아 있을 수 있으니 0으로 치환
            s[k][i]=0
        
    

    
r,c,k=map(int,input().split())

s = [list(map(int,input().split())) for _ in range(3)]
t=0

try:#처음부터 정답인 경우는 바로 출력 r,c가 리스트 범위를 벗어날 수 있으니 예외처리 
    if s[r-1][c-1]==k:
        print(t)
        t=102
except:
        pass

    
while t<=100:#최대 100번이니 t가 100보다 크거나 같을때까지만 
    t+=1
    rl,cl = len(s),len(s[0])#R연산인지 C연산인지 확인해주기 위한것
    
    if rl>=cl:
        R(s)
    else:
        C(s)
   
    try:연산후 정답인 경우는 바로 출력 r,c가 리스트 범위를 벗어날 수 있으니 예외처리
        if s[r-1][c-1]==k:
            print(t)
            break
    except:
        pass
    
if t==101:#100번 연산했는데 답이 안 나왔음으로 -1 출력
    print(-1)