백준 1021 cpp // 데큐, 규칙찾기, find함수 사용법

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

1021번: 회전하는 큐

 

※ 주의 : pop은 앞에서만 가능.

 

*의사코드 

- 모두 앞으로 보낼때 vs 모두 뒤로 보낼때 이동횟수가 적은것을 선택한다.

 

while(m-- // 목표)

1. while(앞!=목표){

cnt1++, q1, 뒤로보내는 로직

}

while(앞!=목표){

cnt2, q2, 앞으로 보내는로직

}

2. 두 카운트 중 최소값 선택

d=최소값인큐

d.pop_front()

ret+=cnt

 

*내 코드

#include<bits/stdc++.h>
using namespace std;

int n,m,ret;
deque<int> d;
vector<int> v;

void printD(deque<int> d){
	for (auto i : d) {
		cout << i << " ";
	}
	cout << "\n";

}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n >> m;

	for (int i = 1; i <= n; ++i) {
		d.push_back(i);
	}

	for (int i = 0; i < m; ++i) {
		int target;
		cin >> target;
		//v.push_back(target);

		int cnt1 = 0;
		deque<int> q1 = d;
		while (q1.front() != target) {
			cnt1++;
			//뒤로이동
			int temp = q1.front();
			q1.pop_front();
			q1.push_back(temp);
		}
		int cnt2 = 0;
		deque<int> q2 = d;
		while (q2.front() != target) {
			cnt2++;
			//앞으로이동
			int temp = q2.back();
			q2.pop_back();
			q2.push_front(temp);
		}

		//뒤로이동하는게 최소값인경우
		if (cnt1 <= cnt2) {
			d = q1;
			//cout << "뒤로 : ";
			//printD(d);
			d.pop_front();	//정답은 pop해준다
			ret += cnt1;
		}//앞으로 이동하는게 최소값인 경우
		else {
			d = q2;
			//cout << "앞으로 : ";
			//printD(d);
			d.pop_front();
			ret += cnt2;
		}
	}

	cout << ret;

	
}

 

*바킹독 코드

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

 

* find함수 사용법 : find(begin,end,target)-begin

find(begin, end, 찾는값) // 찾는값의 iter를 반환한다.

여기서 - begin을 하면 

반환 : 두 iter사이의 거리 == 찾는 원소의 idx 가 된다.

int main()
{
    vector<int> v = { 1, 2, 3, 4, 5 };

    cout << "Index of 3 : " << find(v.begin(), v.end(), 3) - v.begin() << endl;
    cout << "Index of 6 : " << find(v.begin(), v.end(), 6) - v.begin();
}

 

*코드 이해

if (idx < DQ.size() - idx) { //목표가 앞쪽에 가까우면 뒤로보낸다
    DQ.push_back(DQ.front());
    DQ.pop_front();
}
else {
    DQ.push_front(DQ.back());
    DQ.pop_back();
}

if문은 이런 상황을 말한다. -> (앞원소를) 뒤로보내는게 최적인 상황 

else는 아래 상황 -> (뒤원소를) 앞으로보내는게 최적인 상황.