[코드트리] 1차원 폭발 게임 C++

문제

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

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

 

계획세우기

1. m개 이상 같은 수가 없을 때까지 반복(m=1이라면 배열에 있는 수들이 전부 터짐. n=0)
2. 같은 수가 m개 이상 있는 구간을 0으로 전부 바꾸기
3. 빈 공간을 찾아서 0이 아닌 수 앞으로 당겨주기

 

풀이(성공)

#include <iostream>

using namespace std;

int n, m;
int bombs[101]; // 1이상 100이하의 숫자가 적혀있는 N개의 폭탄

// 배열의 원소들을 앞으로 당기는 
void MakeCompact(){
    // 빈 공간 찾기
    int endOfIdx=0;
    for(int i=0; i<n; i++){
        if(bombs[i]==0) {
            endOfIdx=i;
            break;
        }
    }

    // 원소들 앞으로 당기기
    for(int i=endOfIdx; i<n; i++){
        if(bombs[i]!=0){
            bombs[endOfIdx]=bombs[i];
            bombs[i]=0;
            endOfIdx++;
        }
    }
    
    // 배열 갯수 갱신
    n=endOfIdx;
}

bool IsExploding(){
    bool isExplode=false;

    int cnt=1;
    // 폭발될 숫자가 있나 확인
    for(int i=1; i<n; i++){
        if(bombs[i-1]==bombs[i]) cnt++;
        else cnt=1;
        if(cnt>=m){
            isExplode = true;
            break;
        }
    }
    return isExplode;
}

// m개 이상 연속 같은 숫자가 있으면 해당 숫자 폭탄이 전부 터짐
void Explode(){
    while (true){
        if(m==1) {
            n=0;
            break;
        }
        if(!IsExploding()) break;

        //M개 이상인 폭탄들의 쌍이 여러 개라면 동시에 터지게 됩니다.
        int cnt=1, sIdx=0;
        for(int i=1; i<n; i++){
            if (bombs[i]==0) continue;
            if (bombs[i-1]==bombs[i]) cnt++;
            else {
                cnt=1;
                sIdx=i;
            }

            if(cnt>=m){
                int removeNum=bombs[sIdx];
                for(int j=sIdx; j<n; j++){
                    if(bombs[j]!=removeNum) break;
                    bombs[j]=0;
                }
            }
        }

        MakeCompact();
    }
}

int main() {
    // input
    cin >> n >> m;
    for(int i=0; i<n; i++){
        cin >> bombs[i];
    }

    // solution
    Explode();

    // output
    cout << n << '\n';
    for(int i=0; i<n; i++){
        cout << bombs[i] <<'\n';
    }

    return 0;
}

풀이(실패)

M개 이상인 폭탄들의 쌍이 여러 개라면 동시에 터진다는 조건이 있었는데, 해당 조건을 반영하지 않아서 틀렸다.

#include <iostream>

using namespace std;

int n, m;
int bombs[101]; // 1이상 100이하의 숫자가 적혀있는 N개의 폭탄

// 배열의 원소들을 앞으로 당기는 
void MakeCompact(int startIdx){
    // 원소들 앞으로 당기기
    for(int i=startIdx; i<n; i++){
        if(bombs[i]!=0){
            bombs[startIdx]=bombs[i];
            bombs[i]=0;
            startIdx++;
        }
    }

    // 배열 갯수 세기
    int cnt=0;
    for(int i=0; i<n; i++){
        if(bombs[i]==0) break;
        cnt++;
    }
    n=cnt;
}

int IdxToStartExploding(){
    bool isExplode=false;

    int cnt=1, idx=0;
    // 폭발될 숫자가 있나 확인
    for(int i=1; i<n; i++){
        if(bombs[i-1]==bombs[i])cnt++;
        else {
            idx=i;
            cnt=1;
        }
        if(cnt>=m){
            isExplode = true;
            break;
        }
    }

    if(isExplode) return idx;
    else return -1;
}

// m개 이상 연속 같은 숫자가 있으면 해당 숫자 폭탄이 전부 터짐
void Explode(){
    while (true){
        if(m==1) {
            n=0;
            break;
        }
        // 지울 숫자가 처음 나오는 idx
        int start=IdxToStartExploding();
        if(start==-1) break; // -1이면 지울 수가 없다는 의미
        // 지울 숫자
        int removeNum=bombs[start];
        for(int i=start; i<n; i++){
            if(bombs[i]!=removeNum) break;
            bombs[i]=0;
        }

        MakeCompact(start);
    }
}

int main() {
    // input
    cin >> n >> m;
    for(int i=0; i<n; i++){
        cin >> bombs[i];
    }

    // solution
    Explode();

    // output
    cout << n << '\n';
    for(int i=0; i<n; i++){
        cout << bombs[i] <<'\n';
    }

    return 0;
}