[C++] 백준 5430 : AC

골드 Ⅴ

 

우선 이문제를 더 쉽게 풀기 위해서는 연속된 R들을 모두 하나의 R로 생각하면 더 쉽게 풀 수 있다는 걸 알수있다

근데 그로인해 얻는 오버헤드 없앰이 그렇게 많지 않을거같아서.. 난 그렇게 안함!

아무튼 이 문제 까다로웠던 부분은 벡터(또는 배열)의 인덱스에 접근하는 부분이다.

나는 R과 D를 실제로 수행하는 건 비효율적이라고 생각해서,

 

입력으로 들어오는 array는 일단 저장해놓고 건드리지 않는다.

그 다음, left idx와 right idx, go_right 이라는 변수를 설정해두고

 

cmd(R과 D로 이루어짐) 이 어떻게 들어오냐에 따라서 li, ri, go_right의 값을 바꿔주고

그에 따라서 array의 값을 출력해 주도록 하였다.

 

더 자세히 말하면, R이 들어온 경우 go_right는 값을 flip 한다 (true -> false / false -> true)

D가 들어온 경우 go_right 인 경우 left index를 ++해주고,

go_right이 거짓인 경우 right index를 --해준다.

 

ex)

go_right = true

1 3 5 7 9

li           ri

 

D 실행

 

go_right = true

1 3 5 7 9

   li        ri

 

D 실행

 

go_right = true

1 3 5 7 9

      li    ri

 

R 실행

 

go_right = false

1 3 5 7 9

      li    ri

 

D 실행

 

go_right = false

1 3 5 7 9

      li ri

 

모든 cmd 연산이 끝난 후 go_right이 true냐 false냐에 따라서 배열을 읽어준다.

위의 예시의 경우 go_right가 false이므로 li <- ri 순으로 읽어준다.

[7, 5] 가 정답이 된다.

 

근데 이게.. li 와 ri 의 값이 배열이 empty 하게 되면 li > ri 가 된다. (정확하게는 li = ri + 1)

이 경우 li -> ri / li <- ri 순으로 읽게 하는 코드를 실행시킬 수 없으므로 이 부분은 따로 처리를 해준다

 

이걸 찾는게 어려웠고 다른건 평범했던 문제

 

근데 역시 C언어로 문자열 다루는건 힘들다..

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

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

	while (TC--) {
		char cmd[100001];
		scanf("%s", cmd);
		int N;
		scanf("%d", &N);
		char row[500000];
		scanf("%s", row);
		row[0] = ',';
		row[strlen(row) - 1] = ',';
		vector<int> arr;
		char *ptr = strtok(row, ",");
		while (ptr != NULL) {
			arr.push_back(atoi(ptr));
			ptr = strtok(NULL, ",");
		}

		int li = 0;
		int ri = N - 1;
		bool go_right = true;
		vector<int> ans;
		bool has_error = false;
		for (int i = 0; cmd[i] != '\0'; i++) {
			if (cmd[i] == 'R') {
				go_right = !go_right;
			}
			else {
				if (li > ri) {
					has_error = true;
					break;
				}
				if (go_right) li++;
				else ri--;
			}
		}


		if (has_error) printf("error\n");
		else {
			if (arr.empty() || li > ri) {
				printf("[]\n");
				continue;
			}
			printf("[");
			if (go_right) {
				for (int i = li; i < ri; i++) {
					printf("%d,", arr[i]);
				}
				printf("%d", arr[ri]);
			}
			else {
				for (int i = ri; i > li; i--) {
					printf("%d,", arr[i]);
				}
				printf("%d", arr[li]);
			}
			printf("]\n");
		}
	}
}