https://www.acmicpc.net/problem/1021
1) 풀이
문제에서 '위치'라는 말이 문제를 조금 헷갈리게 한다고 생각하는데,
이 위치를 인덱스라고 생각하지 말고,
1~n까지 덱에 삽입하고 이 삽입된 값들을 '위치'라고 생각하고
옮기면 되는 문제이다.
즉, 정리해보자면
'뽑고자 하는 수(위치)를 최소 연산(오른쪽/왼쪽으로 옮기기)으로
제일 앞으로 옮기고 pop_front 를 해라'
해당 문제에서 고려할 사항과 풀이 순서는 다음과 같다.
- 제일 앞에서만 수를 뽑을 수 있으므로, 덱(deque)을 이용함
* 큐(queue)는 맨뒤에서만 삽입하고 맨앞에서만 삭제할 수 있는 자료구조인 반면에, 덱(deque)은 양쪽 끝에서 삽입과 삭제가 가능한 자료구조임.
- 주어진 수(위치)를 맨 앞으로 옮길시 오른쪽/왼쪽 중 연산이 적게 드는 쪽 어딘지 계산
- 2, 3번 연산(오른쪽/ 왼쪽으로 옮기기)이 얼마나 진행되는지 카운팅
- 카운팅한 수 출력
처음엔 '적게 드는 연산'에만 너무 몰두한 나머지
입력되는 수 하나하나를 직접 오른쪽/왼쪽으로 옮겨보고
(덱에서 해당 수를 오른쪽으로 옮기며 카운팅, sort함수로 다시 정렬하여 왼쪽으로 카운팅)
조건 연산자를 통해 총 카운팅을 저장할 변수에 둘 중 더 작은 수를 더하려고 했다.
두번째 입력받은 수의 상황을 생각해볼 때부터
이 방법이 틀렸다는 걸 깨달았는데😂
두번째 입력받은 수를 맨앞으로 옮기는 상황을 생각해볼때
이전의 수를 옮기고 난 후 덱의 상황에서 진행되기 때문에
내가 생각한 방법은 카운팅은 쉽게 할 수 있을지 몰라도,
옮겨지고 난 후 덱의 상황을 처리하기 힘들었다.
그래서, 나는 어느쪽으로 옮기는 게 더 효율적인지
알아보기 위해 find 함수를 사용하였다.
💡find 함수란?
Iterator find (InputIterator first, InputIterator last, const T& val)
- val의 값이 어디의 위치에 존재하는지를 Iterator로 반환해줌
(val과 일치하는게 없을 시 마지막 end()를 반환)
- #include <algorithm> 을 포함시켜주어야 함
-iterator끼리 빼면 거리가 나오는 점을 이용하여 찾고자 하는 값의 인덱스를 알 수 있음!
(해
즉, find 함수로 입력받은 값이 현재 어느 idex에 위치해있는지 찾으면
해당값을 오른쪽으로 옮겼을 때의 연산의 수, 왼쪽으로 옮겼을 때의 연산을 계산해볼 수 있고,
계산된 결과 중 더 작은 값을 기준으로 연산을 수행하면 된다!
설명으로는 이해가 부족할 것 같으니, 아래의 코드와 주석을 살펴보자.
2) 최종 소스코드
#include <bits/stdc++.h>
using namespace std;
int n, m; //첫번째 줄에 입력할 n과 m
deque<int>d; // 1부터 n까지 들어있는 덱
vector<int>v; //m개의 입력받은 수를 저장할 벡터
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) { //1부터 n까지 삽입
d.push_back(i);
}
while (m--) { //뽑아야 하는 수(위치) 입력
int t;
cin >> t;
v.push_back(t);
}
int ans = 0; //총 연산횟수
for (auto c : v) {
int idx = find(d.begin(), d.end(), c)-d.begin();
//찾아야하는 수가 지금 어느 idex에 있는지 계산
int res = (idx <= (d.size()-idx) ? 0 : 1);
//idx: 왼쪽 연산 수. d.size()-idx: 오른쪽 연산 수
if (res == 0) {//왼쪽으로 옮기는 경우
while (c!=d.front()) {
d.push_back(d.front());
d.pop_front();
ans++;
}
d.pop_front(); //해당 수가 front에 도착하여 pop
}
else if (res == 1) {//오른쪽으로 옮기는 경우
while (c != d.front()) {
d.push_front(d.back());
d.pop_back();
ans++;
}
d.pop_front(); //해당 수가 front에 도착하여 pop
}
}
cout << ans << '\n';
}
3) 참고자료
'Problem Solving > 백준' 카테고리의 다른 글
[백준/c++] 4889 - 안정적인 문자열 (0) | 2021.03.05 |
---|---|
[백준/c++] 4949 - 균형잡힌 세상 (0) | 2021.03.04 |
[백준/c++] 5430 - AC (0) | 2021.03.04 |
[백준/c++] 2164 - 카드2 (0) | 2021.03.02 |
[백준/c++] 1874 - 스택 수열 (0) | 2021.02.25 |