백준 AC(5430)

AC

1. 힌트

1) R연산을 실제로 원소를 모두 뒤집게 구현하면 $O(N)$의 시간 복잡도를 가지는데, 모든 연산이 R연산이 들어온다면 전체 시간 복잡도는 $O(N \times P)$가 되어 시간 초과를 피할 수 없다.

2) D연산을 수열의 양 끝에 하는 것으로 수열을 실제로 뒤집지 않을 수 있다.

3) 수열의 양 끝의 삭제 연산은 인덱스 두개를 유지하면서도 할 수 있지만, 덱 자료구조를 사용할 수도 있다.

2. 접근

1) 문제를 단순화할 수 없을까?

힌트 1)에서 본 것 처럼, 실제로 수열을 계속 뒤집을 순 없다. 그런데 문제에서 수열의 앞 뒤 구분은 우리가 D연산을 할 때만 필요한 구분이므로 D연산이 시행되어야 하는 방향만을 유지하면 실제로 뒤집지 않아도 된다.

3. 구현

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder ans = new StringBuilder();
		int TC = Integer.parseInt(br.readLine());
		for (int tc = 0; tc < TC; tc++) {
			String P = br.readLine();
			int N = Integer.parseInt(br.readLine());
			Deque<Integer> dq = new LinkedList<>();
			String S = br.readLine();
			S = S.substring(1, S.length() - 1);
			StringTokenizer st = new StringTokenizer(S, ",");
			for (int i = 0; i < N; i++) dq.offer(Integer.parseInt(st.nextToken()));
			int d = 1; // 왼쪽에서 오른쪽 방향 (-1이면 반대)
			boolean ok = true; // 에러가 발생하지 않았는지 여부
			for (int i = 0; i < P.length(); i++) {
				switch (P.charAt(i)) {
				case 'R':
					d *= -1;
					break;
				case 'D':
					if (!dq.isEmpty()) 
						if (d == 1) dq.pollFirst();
						else dq.pollLast();
					else ok = false;
					break;
				}
				if (!ok) break;
			}
			if (ok) {
				ans.append("[");
				int range = dq.size();
				for (int i = 0; i < range; i++) {
					ans.append(d == 1 ? dq.pollFirst() : dq.pollLast());
					if (i != range - 1) ans.append(",");
				}
				ans.append("]");
			} else {
				ans.append("error");
			}
			ans.append("\n");
		}
		System.out.print(ans);
	}

}

1) 시간 복잡도

모든 연산은 $O(1)$이고, 연산은 $P$개 주어지므로 $O(P)$

2) 테스트 케이스