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

• 이거 문제 제목에 왜 1차가 있나 했더니...
  • 2018년 카카오 블라인트 채용 테스트 1차 문제라서 [1차]라고 써있는거구나.
  • 2018년에만 3번을 했네... 그래서 [3차]까지 있다.
  • 근데 2019년 부터는 저 표시가 없엉.
    • 암튼...

문제 설명

블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록".
같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.

만약 판이 위와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워진다. 같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다.

블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다.

만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면 다시 지워지고 떨어지고를 반복하게 된다.

위 초기 배치를 문자로 표시하면 아래와 같다.

TTTANT
RRFACC
RRRFCC
TRRRAA
TTMMMF
TMMTTJ

각 문자는 라이언(R), 무지(M), 어피치(A), 프로도(F), 네오(N), 튜브(T), 제이지(J), 콘(C)을 의미한다

입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라.

제한 사항

입력형식

• 입력으로 판의 높이 m, 폭 n과 판의 배치 정보 board가 들어온다.
• 2 ≦ n, m ≦ 30
• board는 길이 n인 문자열 m개의 배열로 주어진다. 블록을 나타내는 문자는 대문자 A에서 Z가 사용된다.

출력형식

• 입력으로 주어진 판 정보를 가지고 몇 개의 블록이 지워질지 출력하라.

입출력 예

m	n	board	answer
4	5	["CCBDE", "AAADE", "AAABF", "CCBBF"]	14
6	6	["TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"]	15

입출력 예 설명

• 입출력 예제 1의 경우, 첫 번째에는 A 블록 6개가 지워지고, 두 번째에는 B 블록 4개와 C 블록 4개가 지워져, 모두 14개의 블록이 지워진다.
• 입출력 예제 2는 본문 설명에 있는 그림을 옮긴 것이다. 11개와 4개의 블록이 차례로 지워지며, 모두 15개의 블록이 지워진다.

풀이

• 이건 뭐 풀이가 필요가 없다.
• 그냥 어릴 때 게임 만들었던 식으로 무지성으로 만들어버리면 됨.
• 구현 문제잖아...? 알고리즘 문제는 아닌 듯...

def solution(m, n, board):
    # 아래로 내려가는 방식이니까 큐를 수직으로 세워서 만드는게 좋을 듯
    게임보드 = [[0]*m for _ in range(n)]
    비트보드 = [[0]*m for _ in range(n)]
    
    # 게임보드 데이터 채우기
    for h in range(n):
        for w in range(m):
            게임보드[h][w] = board[w][h]

    def 비트보드초기화():
        for h in range(n):
            for w in range(m):
                비트보드[h][w] = 0
    비트보드초기화()
    
    def 게임보드그리기():
        for h in range(n):
            for w in range(m):
                print(게임보드[h][w],end=" ")
            print(" ")
        for h in range(n):
            for w in range(m):
                print(비트보드[h][w],end=" ")
            print(" ")
    게임보드그리기()
    
    지워질프렌즈, 지워진프렌즈 = 1, 0
    limit = 5
    while 지워질프렌즈 > 0 and limit > 0:
        limit -= 1
        지워질프렌즈 = 0 # 지워질 프렌즈 체크
        for h in range(n-1):
            for w in range(m-1):
                프렌즈 = 게임보드[h][w]
                if 프렌즈 != ' ' and 프렌즈 == 게임보드[h+1][w] and 프렌즈 == 게임보드[h+1][w+1] and 프렌즈 == 게임보드[h][w+1]:
                    비트보드[h][w], 비트보드[h+1][w], 비트보드[h+1][w+1], 비트보드[h][w+1] = 1, 1, 1, 1
                    지워질프렌즈 = 1
        if 지워질프렌즈 == 0:
            break
        
        for h in range(n): # 지워질 프렌즈 카운트
            지워진프렌즈 += 비트보드[h].count(1)
        
        for h in range(n): # 게임보드/비트보드 낙하
            a = 비트보드[h].count(1)
            for i in range(a):
                게임보드[h].pop(비트보드[h].index(1))
                비트보드[h].pop(비트보드[h].index(1))
                게임보드[h].insert(0, ' ')
                비트보드[h].insert(0, 0)
            
    비트보드초기화()
    게임보드그리기()
    
    return 지워진프렌즈

• 잘 되나 확인하고

테스트 1
입력값 〉	4, 5, ["CCBDE", "AAADE", "AAABF", "CCBBF"]
기댓값 〉	14
실행 결과 〉	테스트를 통과하였습니다.
출력 〉	C A A C  
C A A C  
B A A B  
D D B B  
E E F F  
0 0 0 0  
0 0 0 0  
0 0 0 0  
0 0 0 0  
0 0 0 0  
         
         
         
    D D  
E E F F  
0 0 0 0  
0 0 0 0  
0 0 0 0  
0 0 0 0  
0 0 0 0  

테스트 2
입력값 〉	6, 6, ["TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"]
기댓값 〉	15
실행 결과 〉	테스트를 통과하였습니다.
출력 〉	T R R T T T  
T R R R T M  
T F R R M M  
A A F R M T  
N C C A M T  
T C C A F J  
0 0 0 0 0 0  
0 0 0 0 0 0  
0 0 0 0 0 0  
0 0 0 0 0 0  
0 0 0 0 0 0  
0 0 0 0 0 0  
        T T  
          M  
    T F M M  
A A F R M T  
    N A M T  
    T A F J  
0 0 0 0 0 0  
0 0 0 0 0 0  
0 0 0 0 0 0  
0 0 0 0 0 0  
0 0 0 0 0 0  
0 0 0 0 0 0

• 코드 수정해서 채점!

def solution(m, n, board):
    게임보드 = [[0]*m for _ in range(n)]    # 아래로 내려가는 방식이니까 큐를 수직으로 세워서 만드는게 좋을 듯
    비트보드 = [[0]*m for _ in range(n)]

    for h in range(n):
        for w in range(m):
            게임보드[h][w] = board[w][h]    # 게임보드 데이터 채우기
    
    지워질프렌즈, 지워진프렌즈 = 1, 0
    while True:
        지워질프렌즈 = 0                      # 지워질 프렌즈 체크
        for h in range(n-1):
            for w in range(m-1):
                프렌즈 = 게임보드[h][w]
                if 프렌즈 != ' ' and 프렌즈 == 게임보드[h+1][w] and 프렌즈 == 게임보드[h+1][w+1] and 프렌즈 == 게임보드[h][w+1]:
                    비트보드[h][w], 비트보드[h+1][w], 비트보드[h+1][w+1], 비트보드[h][w+1] = 1, 1, 1, 1
                    지워질프렌즈 = 1
        if 지워질프렌즈 == 0:
            break
        for h in range(n): # 지워질 프렌즈 카운트
            지워진프렌즈 += 비트보드[h].count(1)
        for h in range(n): # 게임보드/비트보드 낙하
            a = 비트보드[h].count(1)
            for i in range(a):
                게임보드[h].pop(비트보드[h].index(1))
                비트보드[h].pop(비트보드[h].index(1))
                게임보드[h].insert(0, ' ')
                비트보드[h].insert(0, 0)
    
    return 지워진프렌즈

• 통과 했는데 점수가 1점...
  • 점수가 짜다 ㅋㅋㅋ

정확성  테스트
테스트 1 〉	통과 (0.03ms, 10.4MB)
테스트 2 〉	통과 (0.04ms, 10.4MB)
테스트 3 〉	통과 (0.01ms, 10.4MB)
테스트 4 〉	통과 (1.21ms, 10.4MB)
테스트 5 〉	통과 (23.87ms, 10.4MB)
테스트 6 〉	통과 (3.06ms, 10.6MB)
테스트 7 〉	통과 (0.64ms, 10.4MB)
테스트 8 〉	통과 (1.19ms, 10.4MB)
테스트 9 〉	통과 (0.03ms, 10.6MB)
테스트 10 〉	통과 (0.44ms, 10.5MB)
테스트 11 〉	통과 (2.00ms, 10.6MB)

• 고수의 풀이... 흠... 속도가 별로 안빠른데? 그 중 좀 빠른 거 찾아봄

def solution(m, n, board):
    board = [list(b) for b in board]
    board = [list(reversed([b[i] for b in board])) for i in range(n)]
    remove_target = get_remove_target(board)
    while not "".join([str.strip("".join(t)) for t in remove_target]) == "":
        for i in range(len(board)):
            for j in range(len(board[i]) - 1, -1, -1):
                if "*" == remove_target[i][j]:
                    del board[i][j]
        remove_target = get_remove_target(board)
    cnt = 0
    for b in board:
        cnt += len(b)
    return m * n - cnt


def get_remove_target(board):
    remove_target = [list(" " * len(board[i])) for i in range(len(board))]
    for i in range(len(board) - 1):
        for j in range(len(board[i]) - 1):
            try:
                if board[i][j] == board[i + 1][j] and board[i + 1][j] == board[i + 1][j + 1] and board[i + 1][j + 1] == \
                        board[i][j + 1]:
                    remove_target[i][j] = "*"
                    remove_target[i + 1][j] = "*"
                    remove_target[i][j + 1] = "*"
                    remove_target[i + 1][j + 1] = "*"
            except IndexError:
                continue
    return remove_target
    
정확성  테스트
테스트 1 〉	통과 (0.04ms, 10.2MB)
테스트 2 〉	통과 (0.06ms, 10.3MB)
테스트 3 〉	통과 (0.02ms, 10.2MB)
테스트 4 〉	통과 (0.91ms, 10MB)
테스트 5 〉	통과 (23.10ms, 10.3MB)
테스트 6 〉	통과 (2.60ms, 10.3MB)
테스트 7 〉	통과 (0.36ms, 10.3MB)
테스트 8 〉	통과 (0.72ms, 10.4MB)
테스트 9 〉	통과 (0.04ms, 10.3MB)
테스트 10 〉	통과 (0.38ms, 10.2MB)
테스트 11 〉	통과 (0.93ms, 10.2MB)

• 이쪽이 코드가 더 짧아...

def solution(m, n, board):
    board.reverse()
    field = [list(cols) for cols in zip(*board)]
    answer = 0

    while True:
        bomb = set()
        for row in range(n - 1):
            for col in range(m - 1):
                try:
                    if field[row][col] == field[row + 1][col] == field[row][col + 1] == field[row + 1][col + 1]:
                        bomb.update({(row, col), (row + 1, col), (row, col + 1), (row + 1, col + 1)})
                except:
                    break

        if not len(bomb):
            break

        for r, c in bomb:
            field[r][c] = ''
            answer += 1

        for row in range(n):
            field[row] = list(''.join(field[row]))

    return answer
    
정확성  테스트
테스트 1 〉	통과 (0.03ms, 10.2MB)
테스트 2 〉	통과 (0.04ms, 10.1MB)
테스트 3 〉	통과 (0.01ms, 10.1MB)
테스트 4 〉	통과 (0.82ms, 10.3MB)
테스트 5 〉	통과 (17.61ms, 10.2MB)
테스트 6 〉	통과 (1.80ms, 10.4MB)
테스트 7 〉	통과 (0.38ms, 10.3MB)
테스트 8 〉	통과 (1.35ms, 10.2MB)
테스트 9 〉	통과 (0.04ms, 10.2MB)
테스트 10 〉	통과 (0.48ms, 10.2MB)
테스트 11 〉	통과 (1.03ms, 10.3MB)

• 이거 두줄로 합쳤으면 더 빨라졌을 듯?

• 최종. 별 차이 없네...

def solution(m, n, board):
    게임보드 = [[0]*m for _ in range(n)]    # 아래로 내려가는 방식이니까 큐를 수직으로 세워서 만드는게 좋을 듯
    비트보드 = [[0]*m for _ in range(n)]

    for h in range(n):
        for w in range(m):
            게임보드[h][w] = board[w][h]    # 게임보드 데이터 채우기
    
    지워질프렌즈, 지워진프렌즈 = 1, 0
    while True:
        지워질프렌즈 = 0                      # 지워질 프렌즈 체크
        for h in range(n-1):
            for w in range(m-1):
                프렌즈 = 게임보드[h][w]
                if 프렌즈 != ' ' and 프렌즈 == 게임보드[h+1][w] and 프렌즈 == 게임보드[h+1][w+1] and 프렌즈 == 게임보드[h][w+1]:
                    비트보드[h][w], 비트보드[h+1][w], 비트보드[h+1][w+1], 비트보드[h][w+1] = 1, 1, 1, 1
                    지워질프렌즈 = 1
        if 지워질프렌즈 == 0:
            break
        for h in range(n): # 지워질 프렌즈 카운트 + 게임보드/비트보드 낙하
            a = 비트보드[h].count(1)
            지워진프렌즈 += a
            for i in range(a):
                게임보드[h].pop(비트보드[h].index(1))
                비트보드[h].pop(비트보드[h].index(1))
                게임보드[h].insert(0, ' ')
                비트보드[h].insert(0, 0)
    
    return 지워진프렌즈
    
정확성  테스트
테스트 1 〉	통과 (0.03ms, 10.4MB)
테스트 2 〉	통과 (0.04ms, 10.5MB)
테스트 3 〉	통과 (0.01ms, 10.6MB)
테스트 4 〉	통과 (1.20ms, 10.5MB)
테스트 5 〉	통과 (21.22ms, 10.5MB)
테스트 6 〉	통과 (3.26ms, 10.4MB)
테스트 7 〉	통과 (0.65ms, 10.4MB)
테스트 8 〉	통과 (1.16ms, 10.4MB)
테스트 9 〉	통과 (0.03ms, 10.5MB)
테스트 10 〉	통과 (0.47ms, 10.6MB)
테스트 11 〉	통과 (1.46ms, 10.3MB)