[코드트리] - 격자 숫자 놀이

https://www.codetree.ai/training-field/frequent-problems/problems/matrix-number-play/submissions?page=1&pageSize=20&order=tier

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제 종류

구현, 행열변환

풀이방법

이 문제는 단순히 특정 조건에 맞게 배열을 다시 구성해주면 되는 문제다. 조건 중 행과 열을 기준으로 배열을 재구성하는 로직이 있는데 행일 경우, 열일 경우를 다르게 생각하지말고 같은 로직을 수행한다고 생각하면 간단히 풀 수 있는 문제다.

행과열일때 조건을 구분하지 않는 방법은 열에 추가할경우 기존 배열의 열과 행 정보를 뒤집어줘서 같은 로직을 적용하는 것이다

소요시간

설계: 20분

구현: 40분

코드 (Python)

def get_next_arr(arr):
    # 무조건 행기준이라고 생각함 (열기준일때는 돌린 배열이 들어와야함)
    cur_r = len(arr)
    cur_c = len(arr[0])
    num_d = [{i: 0 for i in range(101)} for i in range(cur_r)]
    for x in range(cur_r):
        for y in range(cur_c):
            num = arr[x][y]
            num_d[x][num] += 1

    # 0.숫자, 1.숫자의 개수
    temp_arr = [[] for i in range(cur_r)]

    for x in range(cur_r):
        for num in range(101):
            # 숫자가 존재하고 0 이 아닐경우
            if num == 0:
                continue
            if num_d[x][num] != 0:
                temp_arr[x].append((num, num_d[x][num]))
        # 1.개수가 적은순 2. 숫자가 작은순으로 정렬
        temp_arr[x].sort(key=lambda x: (x[1], x[0]))

    real_arr = [[] for i in range(cur_r)]
    max_l = 0
    for x in range(cur_r):
        for num, cnt in temp_arr[x]:
            real_arr[x].append(num)
            real_arr[x].append(cnt)
        max_l = max(max_l, len(real_arr[x]))

    for x in range(cur_r):
        if len(real_arr[x]) < max_l:
            dist = max_l - len(real_arr[x])
            for di in range(dist):
                real_arr[x].append(0)
        # max 만큼 채우고 100까지 자름
        real_arr[x] = real_arr[x][:100]

    return real_arr


def in_range(x, y, n, m):
    return 0 <= x < n and 0 <= y < m


def main():
    r, c, k = map(int, input().split())
    r -= 1
    c -= 1
    ans = -1
    arr = [list(map(int, input().split())) for i in range(3)]

    for turn in range(101):
        # 끝낫는지 확인
        cur_r = len(arr)
        cur_c = len(arr[0])

        if in_range(r, c, cur_r, cur_c) and arr[r][c] == k:
            ans = turn
            break
        if cur_r >= cur_c:
            next_arr = get_next_arr(arr)
            arr = next_arr
        else:
            temp_rotate_arr = list(map(list, zip(*arr)))
            next_arr = get_next_arr(temp_rotate_arr)
            arr = list(map(list, zip(*next_arr)))

    print(ans)


main()