(백준 1021번 회전하는 큐 C++) 라이님 블로그 대회 알고리즘 따라잡기 7) 리스트, 배열, 연결 리스트 1

아무래도 코드 디자인을 안 하고 짜다보니 코드에 예외도 많은 것 같고, 복잡하게 짜는 것 같아서 챗gpt의 도움을 받았다.

 

백준 1021번

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

1021번: 회전하는 큐

 

#include <iostream>
#include <deque>
using namespace std;

int main() {
	int N, M;
	cin >> N >> M;
	
	deque<int> dq;
	for (int i = 1; i <= N; i++) dq.push_back(i);
	
	int totalRotations = 0;
	while (M--) {
		int target, index = 0; 
		cin >> target;

		for (int i = 0; i < dq.size(); ++i) {
			if (dq[i] == target) {
				index = i;
				break;
			}
		}
		int index_2 = dq.size() - index;
		int rotations = min(index, index_2);
		totalRotations += rotations;

		if (index < index_2) {
			while (index--) {
				dq.push_back(dq.front());
				dq.pop_front();
			}
		}
		else {
			while (index_2--) {
				dq.push_front(dq.back());
				dq.pop_back();
			}
		}
		dq.pop_front();
	}
	printf("%d", totalRotations);
}

이 코드를 보면서 배운 점은

1. 자연수 input은 자연수로 생각해서 판단한다.

2. notation은 최대한 직관적이고 간결하게 적는다.

3. dq의 앞 원소를 뒤로 보낼 때는

dq.push_back(dq.front());

dq.pop_front()와 같이 서술한다.

 

아래는 내 코드..!

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <deque>
#include <vector>
#include <numeric>
#include <cmath>
using namespace std;

int main() {
	int N, M; scanf("%d %d", &N, &M);
	deque<int> dq; vector<int> v(N);
	for (int i = 0; i < N; i++) dq.push_back(i);
	fill_n(v.begin(), N, 1);

	int cnt = 0;
	int m = 0;
	while (m < M) {
		int head = *dq.begin();
		int temp; scanf("%d", &temp); temp--;

		if (temp == head) {
			//printf("temp == head\n");
			//printf("temp : %d, head : %d\n", temp, head);
			dq.pop_front();
			v[temp] = 0;
		}
		else {
			//printf("temp != head\n");
			int temp_sum = accumulate(v.begin(), v.begin() + abs(temp - head), 0);
			printf("temp_sum : %d\n", temp_sum);
			// head ... temp
            //★ 여기가 틀린 것 같음!!
			if ((temp_sum <= N - m - temp_sum-1 && head < temp) or (temp_sum > N - m - temp_sum-1 && head >= temp)) { // case 2로 접근
				printf("case2로 접근!\n");
				while (head != temp) {
					printf("while문! head : %d, temp : %d\n", head, temp);
					int dq_temp = dq.front();
					dq.pop_front();
					dq.push_back(dq_temp);
					head = *dq.begin();
					cnt++;
				}
				cnt--;
				//for (int i = 0; i < N - m; i++) printf("%d ", dq[i]); printf("\n");

			}
			else { // case 3로 접근
				printf("case3로 접근!\n");

				while (head != temp) {
					printf("while문! head : %d, temp : %d\n", head, temp);

					int dq_temp = dq.back();
					dq.pop_back();
					dq.push_front(dq_temp);
					head = *dq.begin();
					cnt++;
				}
				//cnt++;
				//for (int i = 0; i < N - m; i++) printf("%d ", dq[i]); printf("\n");
			}

			dq.pop_front();
			v[temp] = 0;
			//for (int i = 0; i < N - m-1; i++) printf("%d ", dq[i]); printf("\n");

		}
		m++;
	}
	printf("%d", cnt);
	return 0;

}