[2018 KAKAO BLIND RECRUITMENT / 프로그래머스] 17679번 : [1차] 프렌즈4블록

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/17679

 

Lv2 문제다!

로직은 정답과 같은 방향으로 진행한 것 같은데 구현이 시간복잡도가 높아서 계속 시간초과가 발생해서 틀렸던 문제다 

 

문제 이해

1. 2 x 2 행렬 단위로 탐색하는데, 모두 같은 문자로 이루어져 있는 경우 모든 좌표를 기록한다

2. 해당 좌표의 값들을 모두 0으로 바꾼다(캐릭터가 사라진다)

3. 하나의 열에서 없어진 0의 위에 있는 문자들을 문자가 있는 전 행까지 내린다 

4. 1-3과정을 반복한다

4 -1. 만약 1번을 만족하는 좌표가 더이상 있지 않은 경우(flag == False)에는 루프를 break한다 

 

3번 과정에 대한 추가 설명

캐릭터가 사라지면 행이 변하므로 열은 신경쓰지 않아도 된다 

가장 마지막 행부터 올라가면서 탐색하는데 이때 0인 값이 있다면 해당 열 위에 0이 아닌 문자인 좌표가 있는지 while을 통해 탐색한다

만약 x < 0이라면 i,j 위로는 문자가 없으므로 board[i][j] = 0 이라 하고,

만약 x >= 0 이라면 i,j 위로는 0이 아닌 문자가 있으므로 위의 문자를 i,j로 옮긴다 

 

- 정답 풀이 :

board는 모두 문자열로만 이루어져있기 때문에 모두 list로 바꿔줘야한다 

def solution(m, n, board) :
    answer = 0
    board = list(list(b) for b in board)

    while True :
        delete = []
        flag = False
        # 제거할 위치 찾기
        for i in range(m-1) :
            for j in range(n-1) :
                if board[i][j] != 0 and board[i][j] == board[i][j+1] == board[i+1][j] == board[i+1][j+1] :
                    delete.append((i, j))
                    delete.append((i, j+1))
                    delete.append((i+1, j))
                    delete.append((i+1, j+1))
                    flag = True

        if flag == False :
            break

        # 위치 제거
        for x, y in delete :
            board[x][y] = 0

        # 남쪽 방향으로 위치 이동
        for i in range(m-1, -1, -1) :
            for j in range(n) :
                if board[i][j] == 0 :
                    x = i - 1
                    while x >= 0 and board[x][j] == 0 :
                        x -= 1
                    #i,j 위로 0이 아닌 문자가 있는 경우에는 그 문자를 i,j로 옮긴다     
                    if board[x][j] != 0 and x >= 0 :
                        board[i][j] = board[x][j]
                        board[x][j] = 0

    for i in range(m) :
        answer += board[i].count(0)

    return answer

 

- 시도해본 풀이 :

시간초과 발생

def check(board, alphabet, x, y):
    count = []
    n , m = len(board[0]), len(board)
    if x + 1 < m and y + 1 < n:
        for i in range(x, x + 2):
            for j in range(y, y + 2):
                if board[i][j] == alphabet:
                    count.append([i, j])
    return count
                
def solution(m, n, board):
    for i in range(m):
        board[i] = list(board[i])
    count = 0
    #없애야 할 원소들 좌표 추가하기
    while True:
        result = []
        flag = False
        for x in range(m):
            for y in range(n):
                temp = check(board, board[x][y], x, y)
                if len(temp) == 4:
                    flag = True
                    for i in range(4):
                        result.append(temp[i])
                    
        if not flag:
            break
        
        #원소들 없애기    
        for i in range(len(result)):
            a, b = result[i]
            if board[a][b] != 0:
                count += 1
                board[a][b] = 0        
                
        for j in range(1, n):
            start , end = 0, 0
            for i in range(1, m):
                if board[i - 1][j] != 0 and board[i][j] == 0:
                    start = i
                if board[i - 1][j] == 0 and board[i][j] != 0:
                    end = i - 1
            diff = end - start + 1
            #j열에서 0행부터 start -1 행까지의 원소들
            for i in range(start):
                board[i + diff][j] = board[i][j]
                board[i][j] = 0
                
    return count