백준 17140 : 이차원 배열과 연산

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

17140번: 이차원 배열과 연산

하루에 최소 2문제씩 풀고 있는데, 힘들어 죽겠다. 마지막까지 파이팅!

 

1. R연산만 만들 수 있으면 C연산은 배열 회전 후 R 연산하면 된다!

 말 그대로다. 전부다 구현하려면 인덱싱 문제 머리 쥐어뜯다가 틀린다. 해당 문제를 풀면서 얻은 통찰력은 R연산을 기준으로 C연산은 배열 회전만 시키면 된다는 것이었다. 배열 회전 설명은 생략. 그럼 이제 각각의 숫자를 세고 어떻게 정렬할 것인가 생각을 해보자.

 다음과 같이 1차원 배열을 기준으로 생각해보자

 이렇게 되면 위의 정보는 다음과 같이 정리할 수 있다.

 이제 조건을 생각해보자. 

1. 수의 등장 횟수가 커지는 순으로 정렬한다.
2. 수의 등장 횟수가 동일한 그룹의 경우에는 해당 숫자가 커지는 순으로 정렬한다.

 아무리 봐도 sort 같은 함수를 사용해서는 도저히 정렬할 수 없는 문제이다. 그래서 각 숫자에 대한 정보를 딕셔너리에 담아서 활용했다. 딕셔너리의 키 값을 하나씩 올려가면서 각 숫자별로 등장 횟수가 같은 것을 수집해서 새로운 배열로 만들어 줄 수 있도록 했다. 예를 들어, 다음과 같은 상황이라고 생각해보자

num에 해당하는 것이 딕셔너리의 key 값이고,  count가 딕셔너리의 value라고 하자. 그리고 최초에 찾는 값이 1이라고 한다면 각 key값의 value를 탐색하면서 1인 것들을 찾는다. 그렇다면 다음과 같이 임시 리스트에 넣을 수 있다.

그리고 다음으로 찾을 값은 2이다. 똑같은 방식으로 탐색하면,

이렇게 완성시킬 수 있다. 그러면 우리가 원하는 [2, 1, 3, 1, 5, 1, 1, 2, 4, 2]를 만들 수 있다.

2. 주의할 점!

 본 문제에서는 예제 5를 통해 친절히 일어날 수 있는 오류에 대해 설명해주고 있다. 그것은 배열이 변형되면서 인덱싱이 안 되는 경우다. 찾고자 하는 위치는 [3, 3]에서 k = 3인 경우이다. 그리고 배열은 다음과 같다.

행과 열이 같기 때문에 R연산이고, 1초 이후의 해당 배열은 다음과 같이 된다.

여기에서 [3, 3]을 서치 하게 되면 bound of index 에러가 뜨게 된다. 이 반례 없었으면 안심하고 제출할 뻔했다. 항상 반례를 생각하는 습관을 기르자. 배열이 변형되면서 좌표 탐색이 안 되는 경우가 있으니 반드시 조건문을 걸고 만족하는 경우에만 값을 확인할 수 있도록 해야 한다. 배열의 크기는 가변적이다.

3. 전체 코드

메모리 : 115452 KB, 시간 : 272 ms, 풀이 시간 : 73 분

r, c, k = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(3)]
r, c, k = r - 1, c - 1, k
def check(arr):
    num_row = len(arr)
    num_col = len(arr[0])
    if num_row >= num_col : return 'R'
    else : return 'C'

def calc_R(arr):
    new_arr = []
    max_row = 0
    for i in range(len(arr)):
        temp = arr[i]
        max_num = max(arr[i])
        info = {}
        for j in range(1, max_num+1):
            if temp.count(j) != 0 :
                info[j] = temp.count(j)
        # info [1] 기준으로 정렬하자
        size = len(info)
        temp_list = []
        num = 1
        while size:
            for j in info :
                if info[j] == num :
                    temp_list.append(j)
                    temp_list.append(num)
                    size -= 1
            num += 1
        max_row = max(max_row, len(temp_list))
        new_arr.append(temp_list)
    for i in range(len(new_arr)):
        if len(new_arr[i]) < max_row :
            while True :
                new_arr[i].append(0)
                if len(new_arr[i]) == max_row : break
    return new_arr

def calc_C(arr):
    temp_arr = []
    # 90도 회전시키자
    temp = []
    for j in range(len(arr[0])):
        for i in range(len(arr)):
            temp.append(arr[i][j])
        temp_arr.append(temp)
        temp = []
    temp_arr = calc_R(temp_arr)
    # 다시 뒤집어주자
    num_r = len(temp_arr[0])
    num_c = len(temp_arr)
    new_arr = [[] for _ in range(num_r)]
    for i in range(num_c):
        temp = temp_arr[i]
        for j in range(num_r):
            new_arr[j].append(temp[j])
    return new_arr

def solve(arr):
    time = 0
    while True :
        if 0 <= r < len(arr) and 0 <= c < len(arr[0]) :
            if arr[r][c] == k:
                break
        calc = check(arr)
        if calc == 'R' : arr = calc_R(arr)
        else : arr = calc_C(arr)
        # size check
        size_row = len(arr)
        size_col = len(arr[0])
        if size_row > 100 :
            arr = arr[:100]
        if size_col > 100 :
            temp = []
            for b in range(100):
                temp.append(arr[b][:100])
            arr = temp.copy()
        time += 1
        if time > 100 : break
    if time > 100 :
        print(-1)
    else :
        print(time)
solve(board)