문제

문제 링크

코드

나의 코드

def findBox(m, n, gmap):
    """
        사각형은 왼쪽 위의 블럭으로 대표할 수 있다.
        그리고 지워야 할 블록을 set으로 저장한다. -> 중복 허용 하면 안됨
    """
    blocks = set()
    for y in range(m-1):
        for x in range(n-1):
            if (gmap[y][x] != '-1') and (gmap[y][x] == gmap[y][x+1]) and (gmap[y][x] == gmap[y+1][x]) and (gmap[y][x] == gmap[y+1][x+1]):
                blocks.add(''.join([str(y), str(x)]))
    return blocks
                
def solution(m, n, board):
    # 정답
    answer = 0
    
    # 문제 표현
    omap = [[] for _ in range(n)]
    for row in board:
        lst = list(row)
        for i in range(n):
            omap[i].append(lst[i])
    gmap = []
    for row in omap:
        row = row[::-1]
        gmap.append(row)
    m, n = n, m
    
    # 2 ~ 4 반복 + 종료 조건
    while findBox(m, n, gmap):
        values = findBox(m, n, gmap)
        
        # 없애기
        blocks = set()
        for value in values:
            int_value = [int(value[0]), int(value[1])]
            for i in range(2):
                for j in range(2):
                    blocks.add(''.join([str(int_value[0]+i), str(int_value[1]+j)]))
        for block in blocks:
            value = [int(block[0]), int(block[1])]
            gmap[value[0]][value[1]] = '-1'
        answer += len(blocks)
        
        # 공백 처리하기
        for i, row in enumerate(gmap):
            k = row.count('-1')
            row = [x for x in row if x != '-1']
            for _ in range(k):
                row.append('-1')
            gmap[i] = row

        # print(answer)
        # for row in gmap:
        #     print(row)
        # print("----------------------")
            
    return answer

GPT 4의 코드

def find_blocks(m, n, board):
    to_remove = set()
    for i in range(m-1):
        for j in range(n-1):
            if board[i][j] == board[i][j+1] == board[i+1][j] == board[i+1][j+1] != '':
                to_remove |= {(i, j), (i, j+1), (i+1, j), (i+1, j+1)}
    return to_remove

def solution(m, n, board):
    board = [list(x) for x in board]
    total_removed = 0

    while True:
        to_remove = find_blocks(m, n, board)
        total_removed += len(to_remove)

        if not to_remove:
            return total_removed

        for i, j in to_remove:
            board[i][j] = ''

        for _ in range(m):
            for i in range(m-1):
                for j in range(n):
                    if board[i+1][j] == '':
                        board[i+1][j], board[i][j] = board[i][j], board[i+1][j]

나의 코드와 GPT 코드 간의 차이

코드의 개선 사항

1. 함수 이름 변경: findBox에서 find_blocks로 변경하여 함수의 기능을 더 명확하게 표현하였습니다.
2. 중복 함수 호출 제거: find_blocks 함수를 한 번만 호출하여 중복 연산을 제거하였습니다.
3. 튜플 사용: 좌표를 문자열 대신 튜플로 저장하여 코드의 복잡성을 줄였습니다.
4. 블록 제거 방식 변경: 블록을 제거할 때 -1 대신 빈 문자열('')을 사용하여 코드의 가독성을 향상시켰습니다.
5. 블록 이동 방식 변경: 블록을 아래로 이동시킬 때, 각 열을 따라 아래로 이동하면서 빈 칸을 찾아 블록을 이동시키는 방식을 사용하여 코드의 가독성을 향상시켰습니다.

내 코드가 더 느린 이유

첫 번째 코드가 두 번째 코드보다 느릴 수 있는 주요 이유는 findBox 함수를 두 번 호출하고 있기 때문입니다. 이 함수는 m x n 크기의 2차원 리스트를 두 번 순회하므로, 이 함수를 두 번 호출하면 2차원 리스트를 네 번 순회하게 됩니다. 이는 불필요한 연산을 수행하게 되므로, 실행 시간을 늘리게 됩니다.

또한, 첫 번째 코드는 블록을 제거한 후 빈 공간을 채우는 과정에서 리스트의 count 메소드와 리스트 컴프리헨션을 사용하고 있습니다. 이는 블록을 제거한 후 빈 공간을 채우는 과정을 더 복잡하게 만들며, 추가적인 시간을 소비하게 됩니다.

반면, 두 번째 코드는 find_blocks 함수를 한 번만 호출하고, 블록을 제거한 후 빈 공간을 채우는 과정에서 리스트의 인덱스를 직접 조작하므로, 더 효율적으로 동작합니다.

따라서, 첫 번째 코드가 두 번째 코드보다 느릴 수 있습니다. 이러한 문제를 해결하기 위해서는 첫 번째 코드에서 findBox 함수를 한 번만 호출하도록 수정하고, 블록을 제거한 후 빈 공간을 채우는 과정을 더 효율적으로 구현하면 됩니다.

즉, 내 코드는 시간 복잡도가 높았다는게 문제였다.그 이유는 위와 같으나, 실패했던 케이스를 찾을 순 없었다. 그런데 공통적이었던 것은 n, m이 모두 30인 경우에서 내 코드가 실패했다는 점이다. 시간 초과 전에 5번 케이스는 실패했지만 실행 속도가 어쩌면 영향을 줬을 지도 모르겠다는 추측을 한다. 아니면 사용 가능한 메모리가 매우 제한적이어서 메모리 초과가 발생했을 수도 있다.

고쳐야 할 점

1. 함수의 호출을 최소화 하자.
2. 리스트 컴프리헨션보단 직접 리스트의 인덱스를 통해 값을 조작하자.
3. 코드의 가독성을 높이기 위해 함수의 역할을 하나로 제한하자.
4. 해쉬값을 얻기 위해 문자열을 사용하지 말자. 튜플을 사용하자.