문제 이해 단계
문제 자체는 굉장히 심플한 편이었다.
총 N개의 풍선이 있고 안에 있는 종이의 수만큼 이동한다.
여기서 생각해야 할 점은
이미 터진 풍선은 이동 횟수에 포함되지 않는다는 점과
1번째 풍선과 마지막 풍선이 순환 구조를 이룬다는 점이다.
문제 접근 단계
풍선 번호 이동 규칙을 보면, 원형 연결 리스트로 구현하여 풀라는 의도인 것 같다.
근데 솔직히 포인터 그런 걸로는 풀기 싫어서
vector를 사용해서 풀고자 생각했다.
풍선의 번호는 (인덱스 + 1)이고, 그 풍선 배열의 값을 종이라고 생각했다.
종이에는 0이 있을 수 없으니 선택된 풍선(터진 풍선)을 0으로 설정한다.
이렇게 하면 선택된 풍선의 값이 0이라면
이미 터진 풍선이라고 간주할 수 있다.
현재 풍선의 위치를 잡고, 그 위치를 기준으로 한 칸씩 이동한다.
이동하면서 해당 풍선의 값이 0이 아니면
이동 횟수를 더해주는 방식으로 짜면 괜찮을 거라고 생각했다.
여기서 포인트는
풍선의 이동 값이 양수일 때와 음수일 때를 나눠서 생각해야 한다는 점이었다.
음수일 경우 왼쪽으로 이동(index--)
양수일 경우 오른쪽으로 이동(index++)
문제 구현 단계
cout << "1" << " ";
int index = list[0];
list[0] = 0;
int cnt = 0;위의 코드를 짜준 이유는 문제에서
제일 먼저 1번 풍선을 터트리기 때문이다.
그렇기 때문에 첫 번째 풍선의 값을 0으로 만들어준다.
여기서 index는 이동값, cnt는 현재 지정된 풍선의 번호를 뜻한다.
for (int i = 1; i < list.size(); i++) {
int count = index;
if (index > 0) {
// 종이 값이 양수일때
while (count > 0) {
cnt = (cnt + 1 > list.size() - 1) ? 0 : cnt + 1;
if (list[cnt] != 0) count--;
}
}
else {
// 종이 값이 음수 일때
count *= -1; // 음수 값을 양수로 전환
while (count > 0) {
cnt = (cnt - 1 < 0) ? list.size()-1 : cnt -1;
if (list[cnt] != 0) count--;
}
}
index = list[cnt];
list[cnt] = 0;
cout << cnt + 1 << " ";
}풍선을 터트리고 선택하는 핵심 코드이다.
우선 1번째 풍선을 터트리고 시작했으니 반복 횟수는 1번 줄어든다.
count는 이동 횟수를 체크하기 위한 변수이다.
일단 index(이동값)을 받아서, 이 값이 양수일 때와 음수일 때를 구분하여 동작한다.
양수일 때를 살펴보면,
cnt값이 마지막 풍선이라면 첫 번째 풍선 인덱스(0)로 돌아가도록 하고, 그게 아니면 cnt + 1을 해준다.
그리고 해당 번째 풍선의 값이 0이 아니라면(이미 터진 풍선이 아니라면)
카운터 횟수를 빼줘 원하는 횟수만 움직이게 한다.
이 작업을 count가 0이 될 때까지 반복한다.
음수일 때도 똑같은 로직인데,
다른 것이라면 인덱스는 음수가 될 수 없기 때문에
-1을 곱해줘 강제로 양수로 만든다.
위 작업이 끝나면, 다음 index를 새로 이동한 풍선의 이동값으로 바꿔주고,
해당 풍선의 값을 0으로 바꿔준다.
그리고 인덱스 + 1로 해당 풍선의 번호를 출력한다.
밑에 코드는 해당 문제에 대한 전체 코드이다.
#include <iostream>
#include <vector>
using namespace std;
int main() {
cin.tie(NULL);
cout.tie(NULL);
ios::sync_with_stdio(false);
int N;
cin >> N;
vector<int> list;
while (N-- > 0) {
int value;
cin >> value;
list.push_back(value);
}
cout << "1" << " ";
int index = list[0];
list[0] = 0;
int cnt = 0;
for (int i = 1; i < list.size(); i++) {
int count = index;
if (index > 0) {
// 종이 값이 양수일때
while (count > 0) {
cnt = (cnt + 1 > list.size() - 1) ? 0 : cnt + 1;
if (list[cnt] != 0) count--;
}
}
else {
// 종이 값이 음수 일때
count *= -1; // 음수 값을 양수로 전환
while (count > 0) {
cnt = (cnt - 1 < 0) ? list.size()-1 : cnt -1;
if (list[cnt] != 0) count--;
}
}
index = list[cnt];
list[cnt] = 0;
cout << cnt + 1 << " ";
}
return 0;
}
시행착오
이 문제는 푸는데 굉장히 머리도 아프고 오래 걸렸다.
처음에는 큐로 이 문제를 구현하려고 했다.
하지만 문제 메모리 제한이 4MB인걸 모든 구현이 끝나고 나서 알았다.
그래서 멘붕에 빠지고 이를 배열로 짜려다 보니 너무 머리가 아팠다.
문제 구현 자체는 어렵지 않았으나
문제를 오래 푸니 머리가 안 돌아가서 오래 걸렸던 것 같다.
그래도 큐로 구현한 걸 버리긴 아쉬우니
밑에 코드로 남겨둘 테니 필요하다면 참고하길 바란다.
#include <iostream>
#include <utility>
#include <queue>
using namespace std;
int main() {
cin.tie(NULL);
cout.tie(NULL);
ios::sync_with_stdio(false);
int N;
cin >> N;
pair<short, short> p;
pair<short, short> temp;
queue<pair<short, short>> queue;
for (int i = 1; i < N+1; i++) {
int value;
cin >> value;
p = make_pair(i, value);
queue.push(p);
}
int count;
while (!queue.empty()) {
count = queue.front().second - 1;
cout << queue.front().first << " ";
queue.pop();
if (count < 0) count = queue.size() + count;
for (int i = 0; i < count; i++) {
temp = queue.front();
queue.pop();
queue.push(temp);
}
}
return 0;
}