[구현] 백준 17140 : 이차워 배열과 연산 - 파이썬 Python

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

17140번: 이차원 배열과 연산

 

R 연산과 C 연산을 나누어서 생각했다

각 연산에서의 진행 과정은 아래와 같다

• 모든 row (R연산) 혹은 col (C연산)에 대해 각 수의 개수 카운팅 하면서 dictionary에 추가 
• dictionary를 tuple로 풀어서 sort (1 idx 우선, 2 idx 다음) 
• sort된 튜플을 풀어서 새로운 A로 생성
• col_cnt (C연산) 혹은 row_cnt (R연산)을 갱신

R,C 연산의 시간복잡도

최대 크기 100이고 해당 최대를 N으로 가정

모든 행에 대하여 정렬 진행 - O(N^2*logN)

연산은 총 100으로 제한되어 있기 때문에 O(100 * N^2 * logN) = 1000000 * 6.xxx 

헤맷던 주의점

문제를 제대로 안읽어서 헤맸다

0인 경우에는 skip해주어야 한다

 

r, c, k = map(int, input().split())
# idx 0에서 시작하는 것으로 보정
r = r-1
c = c-1

A = []
for _ in range(3):
    A.append(list(map(int, input().split())))

row_cnt, col_cnt = 3, 3



def sort_R():
    global col_cnt
    new_A = []
    new_col_cnt = 0
    for row_list in A:
        dict = {}
        for elem in row_list:
            # 0인 경우 카운팅 하지 않으므로 skip
            if elem == 0:
                continue

            if elem in dict:
                dict[elem] += 1
            else:
                dict[elem] = 1
        
        sorted_tuple = sorted(dict.items(), key=lambda x:(x[1], x[0]))

        # col_cnt 갱신을 위한 가장 큰 col_cnt 측정
        # 100개로 valid
        sorted_tuple_len = len(sorted_tuple)
        if sorted_tuple_len > 50:
            sorted_tuple = sorted_tuple[0:50]
            new_col_cnt = max(new_col_cnt, 100)
        else:
            new_col_cnt = max(new_col_cnt, len(sorted_tuple)*2)
        # col_cnt 갤신
        col_cnt = new_col_cnt
        tmp = []
        for t in sorted_tuple:
            tmp.append(t[0])
            tmp.append(t[1])
        new_A.append(tmp)

    for row in new_A:
        rest_cnt = col_cnt - len(row)
        for _ in range(rest_cnt):
            row.append(0)

    return new_A



def sort_C():
    global row_cnt, col_cnt
    new_A = [[0]*100 for _ in range(100)]

    new_row_cnt = 0
    for cIdx in range(col_cnt):
        dict = {}
        for rIdx in range(row_cnt):
            # 0인 경우 카운팅 하지 않으므로 skip
            if A[rIdx][cIdx] == 0:
                continue
            
            if A[rIdx][cIdx] in dict:
                dict[A[rIdx][cIdx]] += 1
            else:
                dict[A[rIdx][cIdx]] = 1
        
        sorted_tuple = sorted(dict.items(), key=lambda x:(x[1], x[0]))
        # col_cnt 갱신을 위한 가장 큰 col_cnt 측정
        # 100개로 valid
        sorted_tuple_len = len(sorted_tuple)
        if sorted_tuple_len > 50:
            sorted_tuple = sorted_tuple[0:50]
            new_row_cnt = max(new_row_cnt, 100)
        else:
            new_row_cnt = max(new_row_cnt, len(sorted_tuple)*2)
     
        

        for tIdx in range(len(sorted_tuple)):
            new_A[tIdx*2][cIdx] = sorted_tuple[tIdx][0]
            new_A[tIdx*2+1][cIdx] = sorted_tuple[tIdx][1]

    # row cnt를 모든게 끝난 후 갱신 해주어야 함!!!
    row_cnt = new_row_cnt
    
    return new_A



time = 0
while True:

    if 0<=r<row_cnt and 0<=c<col_cnt and A[r][c] == k:
        print(time)
        break

    if time > 100:
        print(-1)
        break
    if row_cnt >= col_cnt:
        A = sort_R()

    else:
        A = sort_C()

    time+=1