[문제 풀이] 프렌즈4블록

코딩테스트 연습 - [1차] 프렌즈4블록

 

해결 과정

 구현 문제. 차근차근 따라가면 되는데, 조금 쉽게 접근하기 위해 자료의 형태를 변경했다. 위에서 아래로 블럭이 내려오는 구조를 오른쪽에서 왼쪽으로 블록이 이동하는 구조로 사용할 수 있도록, board 자체를 변경했다. 리스트에서 자료를 삭제하면 알아서 오른쪽 아이템이 빈 왼쪽 공간으로 이동할 수 있다는 점에 착안했다. 

 문제는 테스트케이스 10번 테스트케이스가 통과하지 못하는 것. 질문하기를 좀 살펴보니, 몇 개만 내려오다가 특정 아이템은 내려오고 있지 못하는게 아니냐는 문장을 발견. del 해주는 코드를 짤 때, 1: [2, 3, 4] 처음에는 무조건 개수만큼(여기선 3개) 특정 index(여기선 2)를 del 해줬는데, 1: [2, 3, 6] 이렇게 나올 수도 있으리라 생각하고 코드를(del b[d][dd][0]) 변경하니(del b[d][dd[d][i] - i]) 통과. 이렇게 임의로 생각하는 부분에서 일부 테케를 놓칠 수도 있겠다 싶었다.

 

나의 풀이

from collections import defaultdict

def selectCandidates(x,y):
    try:
        if b[x][y] == b[x+1][y] == b[x][y+1] == b[x+1][y+1] and b[x][y] >= 'A' and b[x][y] <= 'Z':
            return {(x, y), (x+1, y), (x, y+1), (x+1, y+1)}
        else:
            return {}
    except:
        return {}

def solution(m, n, board):
    answer = 0    

    global b
    b = []

    for j in range(n):
        temp = []
        for i in reversed(range(m)):
            temp.append(board[i][j])
        b.append(temp)

    while True:
        candidates = set()
        for i in range(n-1):
            for j in range(m-1):
                candidates.update(selectCandidates(i, j))

        if len(candidates) == 0:
            break
        else:
            dd = defaultdict(list)
            for c in sorted(list(candidates)):
                dd[c[0]].append(c[1])
            
            for d in dd:
                for i in range(len(dd[d])):
                    del b[d][dd[d][i] - i]

            answer += len(candidates)

    return answer

 

다른 풀이

 

 

IDEA