[Algorithm] 백준 5430 - AC (JAVA)

[Algorithm] 백준 5430 - AC (JAVA)

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

틀린 코드

public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); StringBuilder sb = new StringBuilder(); int n = Integer.parseInt(br.readLine()); for (int i = 0; i < n; i++) { String mission = br.readLine(); int num = Integer.parseInt(br.readLine()); String word = br.readLine(); sb.append(chk(mission, num, word)).append("

"); } bw.write(sb.toString()); bw.flush(); br.close(); bw.close(); } public static String chk(String mission, int num, String word) { word = word.replace("[",""); word = word.replace("]",""); ArrayList arr = new ArrayList<>(); StringTokenizer st = new StringTokenizer(word,","); for (int i = 0; i < num; i++) { arr.add(Integer.parseInt(st.nextToken())); } for (int i = 0; i < mission.length(); i++) { if (mission.charAt(i) == 'R') { Collections.reverse(arr); } else { if (arr.isEmpty()) return "error"; arr.remove(0); } } return arr+""; } }

시간 초과 발생 배열을 뒤집는 과정에 연산이 많이 발생하는 것 같다.

Deque를 사용하여 배열을 뒤집지 말고 계산해보자.

정답 코드

import java.io.*; import java.util.ArrayDeque; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); StringBuilder sb = new StringBuilder(); ArrayDeque deque; StringTokenizer st; int n = Integer.parseInt(br.readLine()); while (n--> 0) { String mission = br.readLine(); int num = Integer.parseInt(br.readLine()); st = new StringTokenizer(br.readLine(), "[],"); deque = new ArrayDeque<>(); for (int i = 0; i < num; i++) { deque.add(Integer.parseInt(st.nextToken())); } sb.append(chk(mission, deque)).append("

"); } bw.write(sb.toString()); bw.flush(); br.close(); bw.close(); } public static String chk(String mission, ArrayDeque deque) { ArrayDeque reverseDeque = new ArrayDeque<>(); boolean turn = false; for (int i = 0; i < mission.length(); i++) { if (mission.charAt(i) == 'R') { turn = !turn; continue; } else { if (turn) { if (deque.isEmpty()) return "error"; else deque.removeLast(); } else { if(deque.isEmpty()) return "error"; else deque.removeFirst(); } } } if (!turn) return print(deque); else { while(!deque.isEmpty()) { int tmp = deque.pollLast(); reverseDeque.add(tmp); } return print(reverseDeque); } } public static String print(ArrayDeque deque) { StringBuilder sb = new StringBuilder(); sb.append('['); if(!deque.isEmpty()) sb.append(deque.poll()); while (!deque.isEmpty()) { sb.append(',').append(deque.poll()); } sb.append(']'); return sb.toString(); } }

배열 사이에 공백이 있으면 안된다. (문제를 잘 보자...)

R을 입력받았을 때 배열을 돌리지 않고 boolean으로 판별 후 앞 또는 뒤 원소 제거

from http://sasca37.tistory.com/125 by ccl(A) rewrite - 2021-12-21 21:27:36