[c++] 백준 회전하는 큐(1021)

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

문제가 이해가 안됨. 보고 또 보고 이해함.

지민이의 큐는 저 위의 3가지 밖에 동작을 할 수 없다.

따라서, 무조건 첫 번째 원소만 뽑을 수 있고, 뒤에서 뽑을 수 없음

(덱의 구조상 뒤에서 삭제도 가능한데 이것을 생각하면 안됨. 이게 어떻게 덱 문제인지..? --> 자세히 보니 큐 문제이긴 한데, 뒤에서 삽입이 가능해야 하니 덱을 사용해야 한다. 자체적으로 조건을 걸어줘서 풀어야 하는 듯.)

 

또한, 1번의 연산은 count를 하지 않고, 2번과 3번만 count해야 한다.

 

그러므로 뽑고자 하는 원소를 최소한의 연산으로 큐의 앞쪽에 위치시키도록 하면 된다.

풀이

1. 덱에 인덱스 번호를 저장해서 초기화 해야 한다.

• 왜냐하면, 덱에 있는 원소들의 위치가 변화하기 때문이다.
• 이게 무슨 말이냐면, 문제에서 "지민이가 뽑아내려고 하는 원소의 위치"는 처음 덱에 대한 위치이다. 변경된 덱의 위치가 아니기 때문에, 초기 덱의 위치(인덱스)를 숫자로 저장해 놓아야 찾을 수 있다.
• 주어진 크기 N만큼 1~N까지 덱에 차례대로 push back() 한다. 

2. 찾으려는 "원소의 위치"가 덱의 front에서 가까운지, back에서 가까운지 찾아준다.

• 최소한의 연산을 수행해서 찾아야 하기 때문에, front와 back에서 차례대로 연산을 수행해 찾을 때 어디가 가까운지 파악하고 수행해야한다.
• front에서부터 찾을시, front 값들은 back으로 push된다. back에서 찾을시, back 값들은 front로 push된다.
• 그렇기 때문에 덱의 구조가 달라지고, 다음 iteration에서 찾을 숫자에도 영향이 미친다.
• 여기서, 어떻게 찾을 것인지 2가지 방법이 있다.
• 1) 덱의 구조에서 처음부터 반복문으로 값을 받아 찾으려는 값이 맞는지 확인하고, 반복되는 수만큼 count해준다. 그리고 이를 덱의 크기/2 보다 작으면, front부터 찾고 아니면 back에서부터 찾는다. (내가 수행한 방법)
• 2) #include <algorithm>에서 find()를 사용해서 원하는 값의 인덱스를 찾는다. (정답 코드 방법)

3. 문제에서의 2번과 3번의 연산을 수행하면서, 수행횟수를 세어준다.

• front에서부터 수행할 시, 맨 처음 값을 맨 뒤에 push, 맨 처음 값 제거(pop)
• back에서부터 수행할 시, 맨 마지막 값을 맨 앞에 push, 맨 마지막 값 제거(pop)
• 수행시마다 개수 세어줌

 

코드

 

알게 된 점

1) 덱의 이론은 쉬운데 코드가 생각보다 어려웠음.

2) 알고리즘 라이브러리의 find()에 대해서 알게됨. 특정 값의 인덱스 찾을 때 유용할 듯.

    find(start iterator, end iterator, value)
     : 시작 iter ~ end iter까지 중 value를 가르키는 iterator를 반환.

    index만을 얻기 위해서는 start iterator를 빼주어야 한다.
     ex) index = find(start iterator, end iterator, value) - start iterator

DQ.begin(), DG.end()는 iterator. 아래 링크 참고.

https://forward-gradually.tistory.com/15

c++ iterator에 대해서

 

git 코드

https://github.com/intlabSeJun/c-plus-coding-test/blob/master/7.%20%EB%8D%B1/%ED%9A%8C%EC%A0%84%ED%95%98%EB%8A%94%20%ED%81%90.cpp