https://www.acmicpc.net/problem/1021
1021번: 회전하는 큐
첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가
www.acmicpc.net
풀이
문제 자체는 어렵지 않으나, 어떻게 코드로 구현할 지 어려웠다.
우선 왜 덱인가?
문제에서는 왼쪽과 오른쪽을 한 칸씩 이동한다고 기술되어 있지만 이는 사실 삽입/삭제과정이 일어나고 있다.
단방향이 아닌 양방향에서 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==
C++ 레퍼런스 - find 함수 (<algorithm>)
모두의 코드 C++ 레퍼런스 - find 함수 ( ) 작성일 : 2019-01-19 이 글은 91665 번 읽혔습니다. 범위 안에 원하는 값을 찾는다. 범위 안 (first 부터 last 전 까지) 의 원소들 중 val 과 일치하는 첫 번째 원소를
modoocode.com
'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 |