[알고리즘] 프로그래머스 프렌즈 4블록 파이썬

[프로그래머스] LEVEL2 프렌즈 4블록

👻 문제

👻 나의 풀이

장황하다.

2*2 범위의 글자가 모두 같은 공간을 찾기 위해 board를 완전 탐색하였다.

찾는 족족 answer를 증가시키면 같은 블록에 대해 중복으로 수가 증가해버린다. 또한, 찾는 족족 블록을 터뜨린다면 이후의 과정에서 함께 터뜨려야 할 블록을 찾을 수 없게 된다. 따라서 알파벳의 특징인 대소문자를 이용했다.

터져야 할 블록이 발견되면 바로 지우는 것이 아닌 소문자로 잠시 변환했다. 그리고 완전 탐색이 마무리되기 전까지는 소문자 형태를 유지하여 비교가 가능하면서 중복으로 블록을 세는 일 또한 없게 하였다.

여기까지 탐색의 과정을 설명했다. 다음은 자리 재정비에 관한 코드 설명이다.

구현을 하면서도 삼중 for문을 사용하는 알고리즘이 과연 옳은 건지, 다른 방법이 있지 않을지 하며 나의 풀이에 확신을 갖지 못했다. 결국 다른 알고리즘을 참고하여 나의 코드로 변환했다.

board에서 또한 완전 탐색을 통해 소문자 블록이 발견되면 해당 열의 가장 위쪽으로 옮겼다. 옮기기 위해서는 swap을 사용했다. 그리고 옮겨진 블록은 터뜨렸다.

def isUpper(s):
    return True if ord('A') <= ord(s) <= ord('Z') else False
def isLower(s):
    return True if ord('a') <= ord(s) <= ord('z') else False
def solution(m, n, b):
    board = [list(b[i]) for i in range(m)]
    answer = 0
    stop = False
    while not stop:
        stop = True
        # 탐색
        for i in range(m-1):
            for j in range(n-1):
                if board[i][j] == '':
                    continue
                a = board[i][j]
                b = board[i][j+1]
                c = board[i+1][j]
                d = board[i+1][j+1]
                if a.upper()==b.upper() and b.upper()==c.upper() and c.upper()==d.upper():
                    board[i][j] = a.lower()
                    board[i][j+1] = b.lower()
                    board[i+1][j] = c.lower()
                    board[i+1][j+1] = d.lower()
                    stop = False
        # 자리 재정비
        for i in range(m):
            for j in range(n):
                if board[i][j] == '':
                    continue
                elif isLower(board[i][j]):
                	answer += 1
                    for k in range(i, 0, -1):
                        board[k][j], board[k-1][j] = board[k-1][j], board[k][j]
                    board[0][j] = ''
    return answer

대소문자를 변환해야 했기에 코드가 꽤나 복잡했다.

보완할 수 있었던 곳은 아래와 같다.

board = list(map(list, b))

if a.upper()==b.upper()==c.upper()==d.upper():

파이썬의 특징을 꼭 잘 활용하자.

👻 다른 풀이

합집합 사용하기

중복이 없어야하는 조건을 set의 합집합을 통해 해결한다.

def pop_num(b, m, n):
    pop_set = set()
    # search
    for i in range(n-1):
        for j in range(m-1):
            if b[i][j] == b[i+1][j] == b[i][j+1] == b[i+1][j+1] != '_':
                pop_set |= set([(i, j), (i+1, j), (i, j+1), (i+1, j+1)]) # 중복 없음
    # set_board
    for i, j in pop_set:
        b[i][j] = 0
    for i, row in enumerate(b): # 이를 위해 행열 위치 교체
        empty = ['_'] * row.count(0)
        b[i] = empty + [block for block in row if block != 0]
    return len(pop_set)
     
def solution(m, n, board):
    count = 0
    b = list(map(list, zip(*board))) # 행열 바꾸기
    while True:
        pop = pop_num(b, m, n)
        if pop == 0:
            return count
        count += pop

👻 얻어가기

*

unpack

zip()

반복 가능한 자료형을 같은 위치의 원소끼리 묶어줌

pairs = [('a', 1), ('b', 2), ('c', 3)]
tuple1, tuple2 = zip(*pairs)
print(tuple1, tuple2)
# 결과: ('a', 'b', 'c') (1, 2, 3)