[백준(BOJ)] 2346번 풍선 터뜨리기 C++

문제 : https://www.acmicpc.net/problem/2346

2346번: 풍선 터뜨리기

어떤 문제인가?

1번 풍선부터 N번 풍선까지 각 풍선마다 다음 풍선으로 이동하는 번호가 존재한다.

 

N을 입력한 후 1번 풍선부터 시작해 모든 풍선이 터지는 순서를 출력하면 된다.

 

접근 방법

먼저 풍선의 번호와 각 풍선의 이동 크기를 저장할 자료구조가 필요했다.

큰 생각 없이 vector와 pair를 사용하기로 결정했다.

vector<pair<int,int>>balloon;

 

그리고 입력받은 n만큼 for문을 반복하며 풍선의 숫자와 입력받은 이동 크기를 vector에 추가한다.

 

int n;
cin >>n;

for(int i=0;i<n;i++){
    int a;
    cin >> a;
    balloon.push_back(pair<int,int>(i+1, a));
}

 

이제 1번 풍선부터 터뜨리며 다음 풍선으로 이동해야 한다.

1번 풍선부터 시작이니 vector의 front의 저장되어있을 것이다.

 

1. vector front의 first(풍선 번호)를 출력한다.

2. vector front의 second(이동 크기)를 index라는 변수에 저장한다.

3. 터뜨린다는 의미는 삭제를 의미한다 -> vector에서 삭제한다.

 

이때 index는 양의 정수, 음의 정수가 모두 가능하다. 

그렇기 때문에 두 가지 경우로 나뉜다.

그래서 각각의 경우를 처리하는 함수(moveRight, moveLeft)를 선언하고 index가 양의 정수이면 moveRight, 음의 정수이면 moveLeft를 사용한다.

for(int i=0 ; i<n;i++){
    cout << balloon.front().first << " ";
    int index = balloon.front().second;
    balloon.erase(balloon.begin());

    if (index > 0) {
        moveRight(index);
    }
    else {
        moveLeft(index);
    }
}

 

양의 방향으로 이동하는 경우(moveRight)

void moveRight(int a){
    for (int i = 0; i < a-1; i++) {
        balloon.push_back(balloon.front());
        balloon.erase(balloon.begin());
    }
}

 

함수는 간단하다,

이동할 크기 a-1 만큼 vector의 맨 앞 원소를 맨뒤에 넣어준다.

vector에 저장되어있는 원소들 입장에서는 왼쪽으로 이동한 거지만,

사실은 문제의 의도에 따라 오른쪽으로 이동해 다음 터뜨릴 풍선의 위치를 찾은 거기 때문에 함수의 이름을 moveRight라고 선언했다.

이 함수를 통해 오른쪽만큼 이동(vector상에서는 원소들의 좌측 이동)을 통해 다음으로 터뜨릴 풍선이 vector의 front에 존재한다.

 

 

음의 방향으로 이동하는 경우(moveLeft)

void moveLeft(int a){
    a= -a;
    for (int i = 0; i < a; i++) {
        balloon.insert(balloon.begin(), balloon.back());
        balloon.erase(balloon.end()-1);
    }
}

메커니즘은 똑같다. 단지, 어디를 삭제하고 어디에 추가하냐가 다른 것뿐이다. 

코드를 보면 충분히 이해가 될 것이라 생각한다.

 

 

무엇이 어려웠는가?

문제를 봤을 때 머릿속으로 이렇게 풀어야겠구나 생각은 했지만 문제를 많이 풀어보지 않아서인지 코드로 어떻게 풀어내야 할지는 고민을 조금 했다.

 

내가 생각한 자료구조가 vector였기에 그냥 끝까지 vector로 풀이를 했다. 다시 생각해보니 queue를 사용했으면 훨씬 간단한 코드가 나왔을 것 같다.

 

 

 

배운 점

내가 생각한 풀이 방법을 코드로 표현할 수 있는 능력을 키워야겠다고 생각했다.

머리로는 logic을 알아도 코드로 표현하지 못하면 과연 무슨 소용인가 싶다.

 

또, 문제에서 요구하는 최적의 자료구조를 떠올리는 연습이 더 필요하다고 느꼈다.

이는 많은 반복과 노력에서 해결될 것이라 믿는다.

 

 

시간 복잡도

n번만큼 입력 O(n)

n번만큼 출력 부분 실행 O(n)

 

따라서 O(n)의 시간 복잡도를 갖는다.

 

https://github.com/farmJun/Algorithm_BOJ_PS/blob/main/%EC%8D%B8%EB%A8%B8%EC%BD%94%EB%94%A9/2346.cpp

GitHub - farmJun/Algorithm_BOJ_PS: 백준 알고리즘 문제풀이 기록 레포짓입니다.