[알고리즘/문제풀이/BOJ 5430번] AC

AC문제는 큐를 활용한 문제이다. 큐의 pop을 활용하는 문제로 뒤집기 함수로가 추가된 문제이다. 뒤집기의 경우 pop할 때 경우에 따라 head와 tail 중 1개를 선택하여 1만큼 이동시키면 된다. 주의할 점은 테스트 케이스의 입력이 큰 편이라 수행시간에 여유가 없다는 점이다. 가능하면 O(n+p)의 시간에 수행하여야 한다.  

문제를 풀면서 놓쳤던 부분은 다음과 같다. 먼저 모든 처리를 하고 출력을 할 때 출력형식에 맞추어 출력하는 것에 모든 것의 성패가 달렸다는 점을 느낄 수 있었다. 다 풀었다고 느꼈을 때 자만하지 말고 끝까지 주의를 기울여 풀어야 한다는 점이다. 입력에서도 입력 버퍼에 무엇이 있는지 주의를 기울여야 한다는 점이다. ps에서 끝까지 방심하지 말라는 교훈을 얻은 것 같다.

작성한 코드는 다음과 같다.

---

#include<stdio.h>

int T;
char function[100020];

int n;
int element[1000020];
int head, tail;
int r_flag;

int k;
int x;
int temp;

int main(void) {
	scanf("%d", &T);

	for (int i = 0; i < T; i++) {
		k = 0;
		head = 0;
		tail = 0;
		r_flag = 0;
		x = 0;
		scanf("%s", function);
		scanf("%d%*c",&n);

		getchar();
		for (int j = 0; j < n; j++) {
			x = 0;
			while ((temp = getchar()) != ',' && temp != ']') {
				x = x * 10;
				x = x + temp - '0';
			}
			element[j] = x;
		}
		getchar();

		tail = n;

		while (function[k] != 0) {
			if (function[k] == 'R') {
				r_flag = (r_flag + 1) % 2;
			}
			else {
				if (head == tail) {
					printf("error\n");
					break;
				}
				else {
					if (r_flag == 0) {
						head = head + 1;
					}
					else {
						tail = tail - 1;
					}
				}
			}
			k++;
		}

		if (function[k] == 0) {
			printf("[");
			if (r_flag == 0) {
				for (int j = head; j < tail - 1; j++) {
					printf("%d,", element[j]);
				}
				if (head == tail) printf("]\n");
				else printf("%d]\n", element[tail - 1]);
			}
			else {
				for (int j = tail-1; j >head; j--) {
					printf("%d,", element[j]);
				}
				if (head == tail) printf("]\n");
				else printf("%d]\n", element[head]);
			}
		}
	}
}

문제의 지문은 다음의 링크에서 확인할 수 있다.

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