[코드트리 챌린지] 1주차 - Simulation / Python 파이썬

저번주에 해시맵에 막혀서 654점 나와서 계속 해시맵만 풀었더니 실력이 퇴화했나 ^^,,,

오늘 진단 결과 시뮬레이션이 약하다길래 오랜만에 시뮬레이션 문제 풀어보기로 함

 

목차

 

🔥 문제 링크

https://www.codetree.ai/missions/2/problems/The-1D-bomb-game?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

 

 

🔥 문제 

 

 

 

 

 

🔥 풀이

터질 폭탄이 있는지 체크하는 과정과 폭탄이 터지는 과정을 모듈화했다.

터질 폭탄이 있다면 폭탄 터지는 과정을, 터질 폭탄이 없다면 while문을 종료

 

 

✅ 터질 폭탄이 있는지 체크하는 함수

✔️ 인덱스 0부터 터질 폭탄이 있는지 탐색 

✔️ 연속된 폭탄의 개수를 cnt 변수에 기록하고 다른 숫자의 폭탄이 나왔을 때, 이전까지 저장된 cnt 개수와 m 값을 비교하여 터질 폭탄이 있는 배열인지 결정

✔️ m개 이상의 폭탄이 연속돼있으면 True 리턴 → 폭탄 터뜨릴 준비

✔️ m개 이하의 폭탄이 연속돼있으면 다음 인덱스로 기준 인덱스를 바꾸고 탐색

✔️ 전체를 탐색했는데 터뜨릴 폭탄이 없으면 False를 리턴하여 While문 종료하도록 설정

def check_bombs():
    cnt = 1
    for i in range(len(bombs)):
        for j in range(i+1, len(bombs)):
            if bombs[i] == bombs[j]:
                cnt += 1
            else:
                break
        
        if cnt >= m:
            return True

        cnt = 1
    
    return False

 

 

✅ 폭탄을 터뜨리는 함수

✔️ 폭탄이 있는지 체크하는 함수처럼 폭탄 배열을 돌면서 연속된 폭탄의 개수 기록

✔️ 연속된 폭탄이 있다면 다음부터는 그 폭탄 이후부터 탐색하면 되므로 같은 숫자의 폭탄이라고 탐색이 완료된 인덱스를 idx 변수에 저장

✔️ 연속된 폭탄의 개수가 m보다 크면 기준폭탄 인덱스부터 idx 인덱스까지의 값을 0으로 변경 → 폭탄 터뜨리기

✔️ 폭탄을 다 터뜨렸으면 0이 아닌 배열의 값들만 모아 새로 배열을 만들어줌 → 터지지 않은 폭탄 모아 새로운 배열 만들기

def boom():
    idx = 0

    for i in range(len(bombs)):
        if i < idx:
            continue

        cnt = 1
        for j in range(i+1, len(bombs)):
            if bombs[i] == bombs[j]:
                cnt += 1
                idx = j+1
            else:
                idx = j
                break
    
        if cnt >= m :
            for j in range(i, idx):
                bombs[j] = 0
    
    new_bombs = []
    for i in bombs:
        if i != 0:
            new_bombs.append(i)
    
    return new_bombs

 

 

 

 

🔥 코드

def boom():
    idx = 0

    for i in range(len(bombs)):
        if i < idx:
            continue

        cnt = 1
        for j in range(i+1, len(bombs)):
            if bombs[i] == bombs[j]:
                cnt += 1
                idx = j+1
            else:
                idx = j
                break
    
        if cnt >= m :
            for j in range(i, idx):
                bombs[j] = 0
    
    new_bombs = []
    for i in bombs:
        if i != 0:
            new_bombs.append(i)
    
    return new_bombs

def check_bombs():
    cnt = 1
    for i in range(len(bombs)):
        for j in range(i+1, len(bombs)):
            if bombs[i] == bombs[j]:
                cnt += 1
            else:
                break
        
        if cnt >= m:
            return True

        cnt = 1
    
    return False

n, m = map(int, input().split())

bombs = [0]*n

for i in range(n):
    bombs[i] = int(input())

if m == 1:
    print(0)
else:
    while check_bombs():
        # print(bombs)
        bombs = boom()

    count_bombs = len(bombs)

    print(count_bombs)
    if not count_bombs == 0:
        for bomb in bombs:
            print(bomb)