[algorithm] 2018 Kakao Blind Recruitment 1차 - 프렌즈4블록

1. 문제

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

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

 

2*2 블록 의 형태로 4개 블록이 모여있을 경우에 블록이 사라지고 남은 블록은 아래로 떨어진다.

사라질 블록을 찾는 코드는 일반적인 map searching과 유사하다.

다만 남는 블록이 아래로 떨어지는 것에 대해서 구현하기 위해 고민이 필요했다.

 

2. 풀이

 

def solution(m, n, board):
    newboard=[]
    for i in range(n):
        arr=""
        for line in board:
            arr+=line[i]
        newboard.append(arr)
    answer = 0
    while True:
        removeset =[]
        for i in range(n-1):
            for j in range(m-1):
                sample = newboard[i][j]
                if sample == ' ':
                    continue
                if newboard[i+1][j] == sample and newboard[i][j+1]==sample and newboard[i+1][j+1]==sample:
                    removeset.append((j,i))
                    removeset.append((j,i+1))
                    removeset.append((j+1,i))
                    removeset.append((j+1,i+1))
        li= sorted(list(set(removeset)))
        #print(li)
        if len(li)==0:
            break
        for j,i in li:
            newboard[i]=" "+newboard[i][:j]+newboard[i][j+1:]
        answer+=len(li)
    #print(newboard)
    return answer

 

입력의 배치정보는  행별로 같은 리스트에 묶여있는데

열별로 리스트로 묶는 것이 블록들이 빈자리에 맞춰 아래로 내려오는 것을 구현하기에 더 용이할 것 같아서 

행열을 바꾼 새로운 맵을 만들었다 ( newboard)

 

출처 : https://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/

2*2 블록을 찾을 때는 for문으로 순회하며 찾는다.

이 때, 위의 그림의 라이언과 같이 두개 이상의 2*2 블록에 중첩되는 경우가 생길 수 있기 때문에

set으로 한번씩만 지워질 수 있도록 한다.  -  set(removeset)

 

출처 : https://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/

행/열 방향을 바꿔주었을 때의 장점이 여기서 나오게 되는데

newboard[i]=" "+newboard[i][:j]+newboard[i][j+1:]

해당 셀을 삭제하고 제일앞에 빈칸을 넣어주면 하나씩 내려간 셈이 된다.

이렇게 더이상 삭제할 셀이 없을 때까지 반복한다.