17410 - 이차원 배열과 연산

 

---

 

문제

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

17140번: 이차원 배열과 연산

 

풀이

해당문제의 핵심요소는 

 

1. 배열의 크기를 어떻게 늘리느냐

 

배열의 크기 같은경우에는 늘리지말고, 최대치를 선언한다음에 바운더리를 정해주는 식으로 해결하면 된다.

초기값은 3, 3이고, 연산에 따라 행이나 열의 사이즈를 늘리면 된다.

 

2. 정렬을 어떻게 할 것인가

 

정렬 같은경우에는 우선 최소힙을 사용해서 수와, 수가 카운트 된 횟수를 체크한다.

 

ex> [2, 2, 1, 4] 면 하나씩 꺼내주고, 각 횟수를 카운트 하고, 새로운 배열에 저장한다.

 

그러면 [[1, 1], [2, 2], [4, 1]] 와 같이 저장될 것이다.

 

수가 나온 횟수 기준으로 오름차순, 만약 해당 횟수가 같다면 수를 기준으로 오름차순 하면 된다.

=> [[2,2], [1,1], [4,1]]

 

이 값들을 기존 배열에 잘 넣어주면 된다.

 

단 이 때, 기존의 행 사이즈나 열 사이즈보다 클 수 있기에, 항상 갱신로직을 실행해야 한다. 

(위 예시도 길이가 4에서 6으로 늘어났음)

 

100을 넘어가면 -1을 return 해주고 아니라면 시간초를 출력해주면 된다.

 

코드

import heapq
import copy

def operate_R():

    global r_size, c_size, arr

    for i in range(r_size):
        mid = []
        for j in range(c_size):
            heapq.heappush(mid, arr[i][j])
        l = 0
        res = []
        while mid:
            val = heapq.heappop(mid)
            if val == 0: continue
            l += 1
            count = 1
            while mid:
                if val != mid[0]:
                    break
                count += 1
                heapq.heappop(mid)
            res.append([val, count])
        l *= 2

        c_size = max(l, c_size)

        res = sorted(res, key=lambda x: (x[1], x[0]))
        j = 0
        k = 0

        while True:
            if j >= l: break
            arr[i][j] = res[k][0]
            arr[i][j + 1] = res[k][1]

            j += 2
            k += 1

        for m in range(l, c_size):
            arr[i][m] = 0


def operate_C():

    global r_size, c_size, arr

    for i in range(c_size):
        mid = []
        for j in range(r_size):
            heapq.heappush(mid, arr[j][i])
        l = 0
        res = []
        while mid:
            val = heapq.heappop(mid)
            if val == 0: continue
            l += 1
            count = 1
            while mid:
                if val != mid[0]:
                    break
                count +=1
                heapq.heappop(mid)
            res.append([val, count])
        l *= 2
        r_size = max(l, r_size)

        res = sorted(res, key=lambda x: (x[1], x[0]))
        j = 0
        k = 0

        while True:
            if j >= l : break
            arr[j][i] = res[k][0]
            arr[j+1][i] = res[k][1]

            j+=2
            k+=1
        for m in range(l, r_size):
            arr[m][i] = 0


# Initialize
r, c, k = map(int, input().split())
arr = [[0] * 100 for _ in range(100)]
r_size = 3
c_size = 3
answer = 0

for i in range(3):
    v1, v2, v3 = map(int, input().split())
    arr[i][0] = v1
    arr[i][1] = v2
    arr[i][2] = v3

while True:
    if arr[r - 1][c - 1] == k or answer >= 101:
        break

    if r_size >= c_size:
        operate_R()
    else:
        operate_C()

    answer += 1

print(answer) if answer <= 100 else print(-1)

 

후기

 

처음에 배열 회전을 활용해서 R연산과 C연산을 한개의 함수로 처리할려 했는데 어줍짢게 하다가 엎었다.

 

중복코드를 최대한 지양하겠다고 마음먹은지 얼마 안됐는데 ... ㅋㅋㅋ 오늘 에너지로는 머리 굴리기가 힘들었던 거 같다