BOJ - 이차원 배열과 연산 17140번 (python)

❓ 문제 - 백준 이차원 배열과 연산 17140번 - python 풀이법

 

출처 

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

17140번: 이차원 배열과 연산

 

 

📝 문제해결법

1. 이 문제는 구현으로 풀었다.

• 문제에서 주어진 방법으로 R연산과 C연산을 하면 연산 횟수 count가 1 증가한다. 만약 연산 횟수가 100회 이상이면 -1을 출력하고 종료한다.
• 만약 입력에서 주어진 r 행 c 열 위치의 값이 k값과 같으면 count 값을 출력한 후 while을 빠져나와 종료한다.
• 만약 행의 길이의 최대값이 열의 길이의 최대값 보다 크거나 같으면 R연산을 수행하기 위해 cal_r() 함수를 호출한다. R연산시 열의 길이의 최대값이 변경될 수 있다.
• 만약 열의 길이의 최대값이 행의 길이의 최대값 보다 작으면 C연산을 수행하기 위해 cal_c() 함수를 호출한다. C연산시 행의 길이의 최대값이 변경될 수 있다.

2. cal_r(), cal_c()

• 행과 열의 길이의 최대값을 전역변수로 선언하고 해당 연산 후의 R연산시 열의 길이의 최대값이 변경될 수 있고, C연산시 행의 길이의 최대값이 변경될 수 있기 때문에 최대값을 갱신할 r_m_c(R연산), r_c_r (C연산)변수를 사용한다.
• cal_r() : 행단위로 연산을 수행하기 위해 한 행에 대한 정보를 data 리스트에 담아오고 해당 리스트에서 숫자의 갯수를 딕셔너리를 사용하여 세어주고, 0이 키 값으로 포함되어 있을 경우 제거한다. 그 후 리스트 형태로 변경한 후 정렬을 수행한다. (숫자의 갯수를 기준으로 오름차순 정렬 후, 만약 같은 숫자의 갯수가 있을 경우 숫자의 크기로 오름차순 정렬). 만약 정렬 후 생성된 값들이 범위 100을 넘을 시, 100개까지 잘라서 변경해줘야 하므로 길이를 조정한 후, 한 행에서 정렬 후 생성된 리스트의 길이와 r_m_c 값을 비교한 후 최대값으로 갱신해준다. 그 후 정렬을 통해 생성된 리스트의 값을 행과 열의 인덱스에 맞추어 arr 배열에 값을 변경하고, 정렬 후 생성된 리스트 이외에 값들은 0 으로 초기화 해준다. 또한 열의 길이의 최대값을 연산 후 최대 열의 갯수 r_m_c로 변경한다.
• cal_c() : 열단위로 연산을 수행하기 위해 한 열에 대한 정보를 data 리스트에 담아오고 해당 리스트에서 숫자의 갯수를 딕셔너리를 사용하여 세어주고, 0이 키 값으로 포함되어 있을 경우 제거한다. 그 후 리스트 형태로 변경한 후 정렬을 수행한다. (숫자의 갯수를 기준으로 오름차순 정렬 후, 만약 같은 숫자의 갯수가 있을 경우 숫자의 크기로 오름차순 정렬). 만약 정렬 후 생성된 값들이 범위 100을 넘을 시, 100개까지 잘라서 변경해줘야 하므로 길이를 조정한 후, 한 열에서 정렬 후 생성된 리스트의 길이와 r_m_r 값을 비교한 후 최대값으로 갱신해준다. 그 후 정렬을 통해 생성된 리스트의 값을 행과 열의 인덱스에 맞추어 arr 배열에 값을 변경하고, 정렬 후 생성된 리스트 이외에 값들은 0 으로 초기화 해준다. 또한 행의 길이의 최대값을 연산 후 최대 행의 갯수 r_m_c로 변경한다.

 

 

💻 소스코드

# 이차원 배열과 연산 - BOJ 17140
# 구현 + dict
arr = [[0]*101 for _ in range(101)]

r, c, k = map(int, input().split())
m_r, m_c = 3, 3
for i in range(1, 4):
    data = map(int, input().split())
    arr[i][1:4] = data

count = 0

def cal_r():
    global m_r, m_c
    r, c = m_r, m_c
    r_m_c = -1
    for i in range(1, r+1):
        data = arr[i][1:c+1]
        dict = {data[j]:data.count(data[j]) for j in range(len(data))}
        if 0 in dict.keys():
            dict.pop(0)
        tp = list(dict.items())
        tp.sort(key=lambda x:(x[1], x[0]))
        if len(tp) > 50:
            l = 50
        else:
            l = len(tp)

        r_m_c = max(r_m_c, l * 2)
        temp = []
        for t in range(l):
            a, b = tp[t]
            temp.append(a)
            temp.append(b)
        arr[i][1:l * 2] = temp
        for t in range(l*2+1, 101):
            arr[i][t] = 0
    m_c = r_m_c


def cal_c():
    global m_r, m_c
    r, c = m_r, m_c
    r_m_r = -1
    for i in range(1, c + 1):
        data = []
        for j in range(1, r+1):
            data.append(arr[j][i])
        dict = {data[j]: data.count(data[j]) for j in range(len(data))}
        if 0 in dict.keys():
            dict.pop(0)
        tp = list(dict.items())
        tp.sort(key=lambda x: (x[1], x[0]))
        if len(tp) > 50:
            l = 50
        else:
            l = len(tp)
        r_m_r = max(r_m_r, l * 2)
        temp = []
        for t in range(l):
            a, b = tp[t]
            temp.append(a)
            temp.append(b)
        for t in range(len(temp)):
            arr[t+1][i] = temp[t]
        for t in range(2*l+1, 101):
            arr[t][i] = 0
    m_r = r_m_r

while True:
    if count > 100:
        print(-1)
        break
    if arr[r][c] == k:
        print(count)
        break

    if m_r >= m_c:
        cal_r()
        count += 1
    else:
        cal_c()
        count += 1