https://www.acmicpc.net/problem/2346
2346번: 풍선 터뜨리기
1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선
www.acmicpc.net
소스코드
풀이
★ 알고리즘을 풀다보면 리스트를 좌우로 회전하는 문제를 많이 만날 수 있습니다. 그런 유형을 만날 때마다 일일이 구현하는 경우가 대부분이었는데, deque의 rotate함수를 사용하면 회전을 쉽게 구현할 수 있습니다!
★ rotate()함수는 인자로 양수를 넣어줄 경우 오른쪽 회전을 하게 되고, 음수를 줄 경우 왼쪽 회전을 하게 됩니다.
ex)
dq = deque([1,2,3,4,5])
dq.rotate(3)
[5,1,2,3,4] -> [4,5,1,2,3] -> [3,4,5,1,2]
dq.rotate(-2)
[4,5,1,2,3] -> [5,1,2,3,4] 순으로 바뀌게 됩니다 !
★ 문제에서는 해당 풍선 안에 들어있는 수가 음수일수도, 양수일 수도 있습니다. 만약 양수일 경우 오른쪽 회전을 하게 되는데, 답을 구하기 위해선 왼쪽 회전을 해줘야합니다. 그렇기에 인자에 '-'부호를 붙여줍니다 ! 이와 마찬가지로 음수일 경우에는 오른쪽 회전을 해야하기 때문에 인자에 '-' 부호를 붙여줍니다.
★ 마지막으로 풍선 안에 들어있는 수가 양수일 경우 그 수에 1을 뺀 값만큼만 이동해야 합니다 ! 그 이유는 제거되는 풍선을 제외하고 그 이후 수들이 왼쪽 회전을 해야하기 때문입니다. 음수일 경우에는 뒤에서부터 앞으로 오는 오른족 회전을 하기 때문에 그 수만큼 그대로 rotate 해주면 됩니다 :)
'Algorithm > 백준' 카테고리의 다른 글
| [백준 알고리즘] 16928번: 뱀과 사다리 게임 (Python, BFS) (0) | 2023.10.18 |
|---|---|
| [백준 알고리즘] 13549번: 숨바꼭질 3 (Python, BFS) (0) | 2023.10.18 |
| [백준 알고리즘] 2776번: 암기왕 (Python) (0) | 2023.10.17 |
| [백준 알고리즘] 2660번: 회장뽑기 (Python, BFS) (1) | 2023.10.17 |
| [백준 알고리즘] 4358번: 생태학 (Python) (0) | 2023.10.16 |