Level 2 [1차] 프랜즈 4블록 <KAKAO 2018 BLIND RECRUITMENT>

programmers.co.kr/learn/courses/30/lessons/17679

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

 

최종 코드

• GitHub github.com/hwayeon351/Programmers-Algorithms

hwayeon351/Programmers-Algorithms

def solution(m, n, board):
    answer = 0
    dx = [0, 1, 1]
    dy = [-1, -1, 0]
    erase = set()
    set_b = set()
    map_b = [list(board[i]) for i in range(m)]
    
    while True:
        #지울 블록 찾기
        erase.clear()
        for y in range(m-1, 0, -1):
            for x in range(0, n-1):
                now_b = map_b[y][x]
                if now_b == '0': continue
                set_b.clear()
                set_b.add((x, y))
                for d in range(3):
                    ny = y+dy[d]
                    nx = x+dx[d]
                    if map_b[ny][nx] == now_b:
                        set_b.add((nx, ny))
                        continue
                    break
                else:
                    erase.update(set_b)
                    
        #지울 블록이 없는 경우
        if len(erase) == 0: return answer
        
        #블록 지우기
        answer += len(erase)
        e_list = list(erase)
        while e_list:
            x, y = e_list.pop()
            map_b[y][x] = '0'

        #블록 내리기
        for col in range(n):
            for i in range(m-2, -1, -1):
                if map_b[i][col] == '0':
                    continue
                for j in range(m-1, i, -1):
                    if map_b[j][col] == '0':
                        map_b[j][col], map_b[i][col] = map_b[i][col], map_b[j][col]
                        break
    
    return answer

---

풀이 과정

풀이 시간  1시간 16분

def solution(m, n, board):
    answer = 0
    dx = [0, 1, 1]
    dy = [-1, -1, 0]
    erase = set()
    set_b = set()
    map_b = [list(board[i]) for i in range(m)]
    
    while True:
        #지울 블록 찾기 -> O(n^2)
        erase.clear()
        for y in range(m-1, 0, -1):
            for x in range(0, n-1):
                now_b = map_b[y][x]
                if now_b == '0': continue
                set_b.clear()
                set_b.add((x, y))
                for d in range(3):
                    ny = y+dy[d]
                    nx = x+dx[d]
                    if map_b[ny][nx] == now_b:
                        set_b.add((nx, ny))
                        continue
                    break
                else:
                    erase.update(set_b)
                    
        #지울 블록이 없는 경우
        if len(erase) == 0: return answer
        
        #블록 지우기 -> O(n)
        answer += len(erase)
        e_list = list(erase)
        while e_list:
            x, y = e_list.pop()
            map_b[y][x] = '0'

        #블록 내리기 -> O(n^3)
        for col in range(n):
            for i in range(m-2, -1, -1):
                if map_b[i][col] == '0':
                    continue
                for j in range(m-1, i, -1):
                    if map_b[j][col] == '0':
                        map_b[j][col], map_b[i][col] = map_b[i][col], map_b[j][col]
                        break
    
    return answer
    #시간복잡도 = O(n^4), 공간복잡도 = O(n^2)

---

이전 풀이

 

def find_erase_block(brd):
    erase = []
    for i in range(len(brd)-1):
        for j in range(len(brd[0])-1):
            c = brd[i][j]
            if c == '0': continue
            if brd[i][j+1] == c and brd[i+1][j+1] == c and brd[i+1][j] == c:
                erase.append((i,j))
                erase.append((i,j+1))
                erase.append((i+1,j))
                erase.append((i+1,j+1))
    return list(set(erase))

def solution(m, n, board):
    answer = 0
    brd = []
    erase = []
    for i in range(len(board)):
        brd.append(list(board[i]))
    erase = find_erase_block(brd)
    while(len(erase) > 0):
        answer += len(erase)
        for i, j in erase:
            brd[i][j] = "0"
        for i in range(m-1, -1, -1):
            for j in range(n):
                if brd[i][j] == "0":
                    for k in range(i-1, -1, -1):
                        if(brd[k][j] != "0"):
                            brd[i][j] = brd[k][j]
                            brd[k][j] = "0"
                            break
        erase = find_erase_block(brd)
    return answer

 프랜즈 4블록은 KAKAO 2018 BLIND RECRUITMENT [1차] 코딩테스트의 6번 문제이다.(다른 문제들의 풀이도 아래 참고를 통해 살펴 볼 수 있다.)

나는 지울 수 있는 블록이 있는지 먼저 체크하고 해당 블록들을 지우는 과정을 반복하는 방법으로 구현했다.

 

1. 입력 board를 2차원 리스트 형태로 바꾸기

    for i in range(len(board)):
        brd.append(list(board[i]))

 입력으로 들어오는 board는 한 행을 하나의 문자열로 제공하고 있다. 이를 각각 리스트로 만든 후 brd 리스트에 넣어줌으로써 2차원 리스트 형태로 만든다.

 

 

2. 지울 수 있는 블록 체크하기 find_erase_block()

def find_erase_block(brd):
    erase = []
    for i in range(len(brd)-1):
        for j in range(len(brd[0])-1):
            c = brd[i][j]
            if c == '0': continue
            if brd[i][j+1] == c and brd[i+1][j+1] == c and brd[i+1][j] == c:
                erase.append((i,j))
                erase.append((i,j+1))
                erase.append((i+1,j))
                erase.append((i+1,j+1))
    return list(set(erase))

 brd[0][0]부터 brd[len(brd)-1][brd[len(brd)-1]까지 지울 수 있는 블록이 있는지를 탐색한다.

1. brd[i][j]를 c에 담는다.
2. c == '0'이면 블록이 없음을 의미하므로 continue 해준다.
3. c != '0'이고, brd[i][j+1] == c and brd[i+1][j+1] == c and brd[i+1][j] == c 이면, 4개의 블록이 같은 블록이므로 지울 수 있는 블록이다. 따라서, 4개의 블록 위치를 tuple형태로 erase 리스트에 추가한다.

위 과정을 반복하여 얻은 erase 리스트를 set으로 변환하여 중복값을 삭제하고 이를 다시 리스트 형태로 return한다.

 

 

3. 블록 지우기

    while(len(erase) > 0):
        answer += len(erase)
        for i, j in erase:
            brd[i][j] = "0"
        for i in range(m-1, -1, -1):
            for j in range(n):
                if brd[i][j] == "0":
                    for k in range(i-1, -1, -1):
                        if(brd[k][j] != "0"):
                            brd[i][j] = brd[k][j]
                            brd[k][j] = "0"
                            break
        erase = find_erase_block(brd)
    return answer

 find_erase_block() 함수 반환값인 erase가 0이 될 때까지, 즉, 지울 블록이 없을 때까지 while문을 반복한다.

1. answer += len(erase) 하여 지울 수 있는 블록 개수를 더해준다.
2. 지울 위치들이 tuple 형태로 저장되어 있는 erase를 통해 brd[i][j] = '0'으로 만들어 블록을 지워준다.
3. 지워진 블록으로 인해 생긴 빈 자리에 위에 있는 블록들을 채워주기 위해 brd를 재설정 해준다. n번째 행부터 차례대로 살펴 올라가면서 빈 자리를 찾으면 i행의 한 칸 위부터 위로 탐색하면서 빈 자리를 채울 블록을 찾아주는 방법이다. 아래 과정을 반복한다.
   1. brd[i][j] == '0'인 경우, for문을 통해 i-1부터 0행까지 한 칸씩 위로 올라가며 빈 자리를 채울 블록을 찾는다.
   2. brd[k][j] != '0'으로 블록을 찾으면, brd[i][j] = brd[k][j]로 바꿔주어 블록을 아래로 내려주고, brd[k][j] = '0' 해준 다음 break한다.
4. 2.과정이 끝나 brd가 재정렬 되었으면, 다시 또 지울 블록이 있는지 찾아준다. erase = find_erase_block(brd)

지울 블록이 더이상 없다면 return answer 한다.

---

참고

• 1. 비밀지도 2021/02/09 - [분류 전체보기] - Level 1 [1차] 비밀지도 Python3

Level 1 [1차] 비밀지도 Python3

• 2. 다트게임 2021/02/09 - [코테 노트/프로그래머스] - Level 1 [1차] 다트게임 Python3

Level 1 [1차] 다트게임 Python3

• 3. 캐시 2021/02/09 - [코테 노트/프로그래머스] - Level 2 [1차] 캐시

Level 2 [1차] 캐시

• 4. 셔틀버스 https://hwayomingdlog.tistory.com/105

Level 3 [1차] 셔틀버스 Python3

• 5. 뉴스 클러스터링 2021/02/09 - [코테 노트/프로그래머스] - Level 2 [1차] 뉴스 클러스터링

Level 2 [1차] 뉴스 클러스터링

• 7. 추석트래픽 https://hwayomingdlog.tistory.com/106

Level 3 [1차] 추석 트래픽 Python3