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

정민경·2023년 2월 6일
0

baekjoon

목록 보기
27/57
post-thumbnail

- 문제 (2346번) : 풍선 터뜨리기

  • 풍선안에 들어있는 숫자만큼 움직여 모든 풍선을 터뜨렸을 때 터뜨린 풍선의 위치를 순서대로 출력
    • 풍선 안의 숫자가 양수 : 그 수만큼 오른쪽으로 이동
    • 풍선 안의 숫자가 음수 : 그 수만큼 왼쪽으로 이동

- 입력 및 출력

[ 입력 ]

  • 첫째 줄에 풍선의 개수 N 입력
  • 두번째 줄에 공백을 사이에 두고 풍선안에 들어있는 수 입력

[ 출력 ]

  • 터진 풍선의 번호를 차례로 출력

- 문제 풀이

  • 풍선 안에 들어있는 수가 양수인지 음수인지에 따라 터진 풍선을 기준으로 오른쪽으로 갈지 왼쪽으로 갈지 결정해야 한다.

    따라서 이건 원형으로 생각할 수 있고, 뒤에 있는 수가 앞으로 오기도, 앞에 있는 수가 뒤로 가기도 해야하므로 queue 가 아닌 양방향 queue인 dequeue를 사용해 문제를 해결한다.

  • 입력받은 숫자가 양수
    • 가장 앞의 숫자를 back으로 보냄.
    • 이때 첫번째 숫자는 이미 터져 없어졌고, 그 다음으로 한번 옮긴 후 계산해야하므로 가장 앞의 숫자를 back으로 한번 보낸것으로 간주
  • 입력받은 숫자가 음수
    • 가장 뒤의 숫자를 front로 보냄.

- 최종 코드

0개의 댓글