⭐⭐⭐⭐[코드트리] [시뮬레이션] 1차원 폭발 게임

 

 

문제

1이상 100이하의 숫자가 적혀있는 N개의 폭탄이 쌓여있습니다.

이때 M개 이상 연속으로 같은 숫자가 적혀있는 폭탄들은 터지게 되고, 중력에 의해 위에 있던 폭탄들은 밑으로 떨어지게 됩니다. M개 이상 연속한 폭탄은 부분만 터져서는 안되고 전부 다 터져야 합니다.

예를 들어 다음과 같은 예시에서 M이 2인 경우 3이라는 숫자가 연속하여 M번 이상 나오므로 그 폭탄들이 터지게 됩니다.

만약 M개 이상인 폭탄들의 쌍이 여러 개라면 동시에 터지게 됩니다.

 

이 과정을 M개 이상 연속한 숫자를 갖는 폭탄들이 존재하지 않을때까지 계속 반복했을 때, 최종 결과를 출력하는 프로그램을 작성해주세요.

위의 예에서 M=2인 경우 진행 과정은 다음과 같습니다.

 

입력 형식

첫째 줄에는 N과 M이 공백을 사이에 두고 주어집니다.

두 번째 줄 부터 N개의 줄에 걸쳐 각 폭탄의 숫자가 주어집니다. 숫자는 위에 있는 폭탄에 적혀있는 숫자부터 아래 방향으로 순서대로 주어집니다.

• 1≤N≤100
• 1≤M≤100

출력 형식

첫 번째 줄에는 최종적으로 남게 된 폭탄의 개수를 출력합니다.

두 번째 줄 부터는 한 줄에 하나씩 위에서부터 아래 방향으로 각 폭탄에 적혀있는 숫자를 출력합니다.

 

입출력 예제

예제1

입력:

8 2
1
3
3
3
2
1
1
2

 

출력:

1
1

 

---

진짜 꼭 기억해야할 문제이다.

- 폭발할 폭탄은 0으로 만들고 

- 폭발할 연속된 폭탄 번호는 start와 end로 구분한다

- start부터 end까지 폭발할 폭탄의 수가 조건 개수 m보다 크거나 같으면 

폭발 시키는데 이때 폭발하는 폭탄은 0이 된다. 

 

import sys

def count_explode_bomb(start, num):
    for end in range(start + 1, len(arr)):  # 현재위치 다음 위치부터 끝까지 
        if arr[end] != num:
            return end - 1
        
    return len(arr) - 1

if __name__=="__main__":
    # 변수 선언 및 입력
    n, m = tuple(map(int, input().split()))
    arr = [int(input()) for _ in range(n)]

    while True:
        did_explode = False
        
        for start, num in enumerate(arr):
            if num == 0:
                continue

            end = count_explode_bomb(start, num)
            
            if (end-start+1) >= m:
                arr[start:end + 1] = [0] * (end - start + 1)    # 터질 폭탄의 num을 0으로 만듬 
                did_explode = True
            
        arr = list(filter(lambda x: x > 0, arr))
        '''
        또는 
        new_arr=[]
        for a in arr:
            if a!=0:
                new_arr.append(a)
        arr=new_arr
        '''
        
        if not did_explode:     # 리스트 한바퀴 돌면서 터진적이 없으면 더이상 터질게 없으므로 while문 탈출
            break

    print(len(arr))
    for num in arr:
        print(num)