[문제 링크]

https://www.acmicpc.net/problem/1021

[입출력 예]

[소스코드 - 내 풀이]

#include <bits/stdc++.h>
using namespace std;
int main(){
 
  //n,m입력받기
  int n, m;
  cin>>n>>m;
 
  deque<int> D;
 
  //덱에 숫자 채우기
  for (int i=1; i<=n; ++i){
    D.push_back(i);
  }
 
  //정답
  int cnt=0;
 
  while(m--){
    int x,tmp;
    tmp=0;
    cin>>x;
      while(D.front()!=x){
        D.push_back(D.front());
        D.pop_front();
        tmp++;
      }
      if (tmp>D.size()/2){
        cnt+=(D.size()-tmp);
      }
      else{
        cnt+=tmp;
      }
      D.pop_front();
  }
 
  cout<<cnt;
 
 
  return 0;
}
 
/*
[코멘트]
1. 처음 접근 시 문제 조건을 제대로 안 읽어서 앞에서도 뽑고 뒤에서도 뽑을 수 있는 줄 알았음.
2. 결국 위 풀이는 덱 풀이가 아닌 큐로 푼 것이었는데, 아래 모범 답안은 덱 풀이임.
3. find메소드로 iterator 범위와 목표값을 주면 iterator를 얻을 수 있음. 여기서 begin을 빼주면 인덱스가 나옴.
*/

[소스코드 - 모범답안]

// 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() 로 항상 형변환을
하는 것도 괜찮음.
*/