처음에 생각한 방법
1. circular queue를 생성.
int head = 배열의 처음을 가리킴. 배열의 인덱스로 참조.
int tail = 배열의 마지막 원소를 가리킴. 배열의 인덱스로 참조.
두 개의 변수를 가지고 있고, tail = (tail+1)%SZ 와 같은 방식으로 이동을 한다.
2. 뽑아내려고 하는 수의 위치가 head, tail 중 가까운 것에 따라 동작을 다르게 함.
- head와 가까움 -> 2번 작업 ( 왼쪽으로 이동 )
- tail과 가까움 -> 3번 작업 ( 오른쪽을 이동 )
3. 배열에 저장해 놓은 값 = 초기 원소의 위치 (뽑아내려고 하는 수의 위치는 값으로 참조)
0 1 2 3 4 5 6 7 8 9 <= 배열 index
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
이걸 기반으로 1차원 배열로 구현을 하는데
pop을 했을 때 그 index를 어떻게 처리해줄지, 이것저것 너므 어려워ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ
구현에서 막혀버렷댱,,,, 2시간 넘겼으니 다른 사람 코드보고 공부했음
일단 내 코드 - 시간초과 나옴
#include<iostream>
#include<vector>
using namespace std;
int queue[50] = { 0, };
int n, m; // n: 큐의 크기, m:뽑아내려고 하는 수의 개수
// from : head or tail
// to : 구하려는 값
int getDistance(int from, int to) {
int res = abs(from - to);
int cnt_zero = 0; // 0이 몇개 있는지 세기.
// 0은 이미 pop 한 자리이기때문에 카운트해줄 필요가 없음.
if (from<to) {
for (int i = from; i <=to; i++) {
if (queue[i]==0) {
cnt_zero++;
}
}
}
else { // to>from
for (int i =to; i <= from; i++) {
if (queue[i] == 0) {
cnt_zero++;
}
}
}
return res - cnt_zero;
}
// way = 0 : 왼쪽으로(2번 작업)
// = 1 : 오른쪽으로(3번 작업)
int movePoint(int _from, int _steps, int way) {
int res = _from;
if (way == 0) { // 왼쪽으로 이동. head++
int count_steps = 0;
while (count_steps < _steps) {
res = (res + 1) % n;
if (queue[res]!=0) {
count_steps++;
}
}
}
else { // 오른쪽으로 이동. head--
int count_steps = 0;
while (count_steps < _steps) {
if (res - 1 < 0) {
res = n + res-1;
res = res % n;
}
else {
res--;
}
if (queue[res] != 0) {
count_steps++;
}
}
}
if (res<0) {
res = n + res;
}
return res;
}
int main() {
vector<int> res;
int head = 0;
int tail=0;
cin >> n >> m;
tail = n-1; // 큐의 마지막 인덱스를 가리키고 있다.
// queue에 원소 넣어주기 - 처음 queue의 위치를 나타내는 수임.
for (int j = 0; j < n; j++) {
queue[j] = j + 1;
}
int count = 0; // result. 2번, 3번 연산의 최솟값
for (int i = 0; i < m; i++) {
int temp;
cin >> temp;
res.push_back(temp);
}
for (int j = 0; j < res.size(); j++) {
while (1) {
if (queue[head] == res[j]) {
// pop
queue[head] = 0;
head++;
break;
}
// head와 더 가까울 경우 -> 2번 작업
// tail과 더 가까울 경우 -> 3번 작업
int distance_from_head = getDistance(head, res[j] - 1);
int distance_from_tail = getDistance(tail, res[j] - 1);
if (distance_from_head < distance_from_tail) {
//2번 작업 -> 왼쪽으로 이동 head++
head = movePoint(head, distance_from_head, 0);
tail = movePoint(tail, distance_from_head, 0);
count += distance_from_head;
}
else { //distance_from_head > distance_from_tail
// 3번 작업 -> 오른쪽으로 이동 head--
distance_from_tail++;
head = movePoint(head, distance_from_tail, 1);
tail = movePoint(tail, distance_from_tail, 1);
count += distance_from_tail;
}
}
}
cout << count;
return 0;
}
=> 1. c++의 STL 를 잘 활용하자! 괜히 1차원 배열로 구현하려해서,,,, 엄청난 삽질,,,,
2. stl deque 공부하기
다른 분의 코드 : http://dailyddubby.blogspot.com/2018/05/128-1021.html
-> 이 분 코드 깔끔함! stl deque사용하셨음
2019.03.26(화)
5개월만에 다시 풀었다
방법 1. recursive func로 왼쪽이동, 오른쪽이동 모두 연산해보며 최소값 구하는 방법 -> 시간초과!
방법 2. main에서 반복문으로, 뽑아내는 원소의 인덱스가 왼쪽에서 가까운지 오른쪽에서 가까운지 그때그때 확인하는 방법 -> OK
나는 당연히 방법1로 완전탐색으로 해야하는 줄 알았는데,,,, 안그러면 예외처리가 안될줄알았는데,,,,
완전탐색인지 그냥 방법2처럼 풀어도되는지 차이점 알려주세요,,,,,ㅠㅠ
(std vector사용)
방법1 c++ 구현코드 -> 시간초과
#include < iostream >
#include < vector >
using namespace std;
int N,M;
int answer = 987654321;
void func(vector < int > _q, vector < int > _idx_q,
int _depth, int _way){
// 탈출조건
if( _idx_q.empty()){
if(_depth < answer) answer = _depth;
return;
}
if(_q[0]==_idx_q[0]){
_q.erase(_q.begin());
_idx_q.erase(_idx_q.begin());
}else{
if(_way==2){ // 왼쪽 이동
int tmp = _q.front();
_q.erase(_q.begin());
_q.push_back(tmp);
_depth++;
}else{ //_way==3 // 오른쪽 이동
int tmp = _q.back();
_q.pop_back();
_q.insert(_q.begin(), tmp);
_depth++;
}
}
// 탈출조건 2
// 다음 단계로 넘어가기 전에
// 이미 _depth가 answer보다 큰 경우, 연산을 멈춰도 괜찮다.
if(_depth > answer) return;
func(_q,_idx_q,_depth,2);
func(_q,_idx_q,_depth,3);
}
int main(void){
vector < int > q;
vector < int > idx_q;
// 입력
cin >> N >> M;
for(int i=1; i<=N; i++) q.push_back(i);
for(int i=0; i < M; i++){
int tmp;
cin >> tmp;
idx_q.push_back(tmp);
}
// 연산
func(q,idx_q,0,2);
func(q,idx_q,0,3);
cout << answer << endl;
return 0;
}
방법2 c++ 구현코드 -> Ok
#include < iostream >
#include < vector >
using namespace std;
int N,M;
int answer = 0;
// return 2 : 왼쪽 이동
// retrun 3 : 오른쪽 이동
int getFasterWay(vector < int > _q, vector< int > _q_idx){
// 왼쪽 이동
int findNum = _q_idx.front();
int cnt =0;
for(int i=0; i < _q.size(); i++){
if( findNum == _q[i]) break;
cnt++;
}
if( cnt < = (_q.size()/2) ) return 2;
else return 3;
}
int main(void){
vector < int > q;
vector < int > idx_q;
// 입력
cin >> N >> M;
for(int i=1; i < =N; i++) q.push_back(i);
for(int i=0; i < M; i++){
int tmp;
cin >> tmp;
idx_q.push_back(tmp);
}
// 연산
int way;
while(1){
// 탈출조건
if( idx_q.empty()) break;
// 연산
if(q[0]==idx_q[0]){
q.erase(q.begin());
idx_q.erase(idx_q.begin());
}else{
way = getFasterWay(q,idx_q);
if(way==2){ // 왼쪽 이동
int tmp = q.front();
q.erase(q.begin());
q.push_back(tmp);
answer++;
}else{ //_way==3 // 오른쪽 이동
int tmp = q.back();
q.pop_back();
q.insert(q.begin(), tmp);
answer++;
}
}
}
cout << answer << endl;
return 0;
}
