https://www.acmicpc.net/problem/1021
풀이
문제 자체는 어렵지 않으나, 어떻게 코드로 구현할 지 어려웠다.
우선 왜 덱인가?
문제에서는 왼쪽과 오른쪽을 한 칸씩 이동한다고 기술되어 있지만 이는 사실 삽입/삭제과정이 일어나고 있다.
단방향이 아닌 양방향에서 push/pop이 일어나고 있으므로 deque이 가장 효율적인 자료구조일 것이다.
가장 중요한 로직은 왼쪽으로 갈 지 오른쪽으로 갈 지 정하는 조건을 설정하는 것이었는데, 적어보면 쉽게 size - idx와 idx를 비교하여 결정함을 알 수 있다.
하지만 나는 종이에 위와 같이 그림을 그려놓고도 deque method가 제공하는 것(front()와 back()를 이용하여 변수 값 비교)에 집중하려 했고 값에 집착하며 idx를 매번 돌기 싫다는 생각을 가지게 되었다.
그러다가 생각의 흐름이 이상한 곳으로 가.. 결국 어떻게 하지?라는 딜레마에 걸렸고 가장 비효율적인 풀이를 생각했다.
내 풀이
#include <bits/stdc++.h>
using namespace std;
int right(deque<int>dq,int pos) {
int cnt = 0;
while (dq.front() != pos) {
int temp = dq.back();
dq.pop_back();
dq.push_front(temp);
cnt++;
}
return cnt;
}
int left(deque<int>dq, int pos) {
int cnt = 0;
while (dq.front() != pos) {
int temp = dq.front();
dq.pop_front();
dq.push_back(temp);
cnt++;
}
return cnt;
}
int main() {
cin.tie(0);
ios::sync_with_stdio(0);
int N; cin >> N;
int M; cin >> M; int sum = 0;
deque<int> dq;
for (int i = 1; i <= N; i++) dq.push_back(i);
while (M--) {
int pos;
cin >> pos;
int r = right(dq, pos); int l = left(dq, pos);
if (r > l) {
sum += l;
while (l--) {
int temp = dq.front();
dq.pop_front();
dq.push_back(temp);
}
dq.pop_front();
}
else {
sum += r;
while (r--) {
int temp = dq.back();
dq.pop_back();
dq.push_front(temp);
}
dq.pop_front();
}
}
cout << sum;
}
시간이 넉넉하게 2초가 주어졌으므로 이 풀이도 통과는 한다.(정말 쓰레기 같은 풀이다.)
하지만 PS는 항상 간결한 코드로..
모범 답안
// Authored by : haneulkimdev
// Co-authored by : BaaaaaaaaaaarkingDog
// http://boj.kr/9571e70535a34702812d2a03510ac182
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
deque<int> DQ;
for (int i = 1; i <= n; i++) DQ.push_back(i);
int ans = 0;
while (m--) {
int t;
cin >> t;
int idx = find(DQ.begin(), DQ.end(), t) - DQ.begin(); // idx : t가 있는 위치
while (DQ.front() != t) {
if (idx < DQ.size() - idx) {
DQ.push_back(DQ.front());
DQ.pop_front();
}
else {
DQ.push_front(DQ.back());
DQ.pop_back();
}
ans++;
}
DQ.pop_front();
}
cout << ans;
}
/*
20번째 줄에서, 지금은 idx가 항상 DQ.size()보다 작아서 문제가 없지만
DQ.size()는 unsigned int(or unsigned long long)이기
때문에 만약 idx가 DQ.size()보다 컸다면 overflow가 발생해
의도한대로 동작하지 않을 수 있음을 인지해야 함. 그래서 size()로
받아온 값에 대해서는 안전하게 (int)DQ.size() 로 항상 형변환을
하는 것도 괜찮음.
*/
이 풀이를 보며 느낀것은
1. C++ Library에서 제공하는 함수를 공부하는 것은 다다익선이다.
2. 하지만 양에 집중해야할 것이 아닌 질에 집중해야할 것
이다.
무슨 말이냐면, 위에 주석에서도 쓰여있듯 size method는 unsigned int(unsinged long long)을 반환하기 때문에 음수로 넘어갈 시 overflow가 발생한다.
물론 이렇게 코드가 짜여지는 경우가 흔하다고 할 순 없겠지만 실제 상황에서는 모든 경우의 수를 고려해야한다.
string find만 알고 있었지 algorithm 라이브러리에 존재하는 find는 처음 알았다. 역시 iterator를 return한다.
(사실 모른다고 하더라도 직접 for문을 통해 구성할 수 있었다.)
InputIterator find(InputIterator first, InputIterator last, const T& val);
// range : [first,last) return : iterator +) This func uses operator==
'Baekjoon' 카테고리의 다른 글
[C++] 2178번 : 미로탐색 (0) | 2024.03.20 |
---|---|
[C++] 1926번 : 그림 (0) | 2024.03.12 |
[C++] 2164번: 카드2 (0) | 2024.03.07 |
[C++] 10845 : 큐/18258 : 큐2 (1) | 2024.03.06 |
[C++] 2493번 : 탑 (0) | 2024.03.05 |