백준 5340 풀이
https://www.acmicpc.net/problem/5430
AC
풀이
라이브러리 함수를 써서 R이면 실제로 뒤집어서 구현하면 정확하겠지?
라는 생각으로 처음에는 문제를 풀었다.
하지만 입력값에 비해 시간이 부족하기때문에 정확하긴 했지만 시간초과를 받았다.
그럼 이제 어떻게 시간을 줄 일 수 있을까?
시간을 줄이는 것에 고민을 많이했다. 여러가지 방법을 써보았지만 시간이 그렇게 감소하는 것 같지 않았다.
결국 질문게시판을 확인했는데, 굳이 배열을 뒤집지않고 답을 구할 수 있는 방법이 있었다.
boolean 변수를 만들어 true면 뒤집힌것, false면 그대로인것.
이렇게 처리를 하고 나중에 해당 boolean 변수에 맞게 앞에서 출력 또는 뒤에서 출력하는 식으로 할 수 있었다.
이를 구현하기 위해서는 deque이 필요하다.
그렇게 시간 초과 문제는 해결되었다. 하지만 이번에는 반례가 있어 통과하지 못했고 반례를 찾기 위해 다시 고민에 들어갔다.
빈 배열과 R만 입력받았을 경우 최종적으로 빈 배열을 출력한다.
이게 내가 미처 발견하지 못한 반례였고 이 부분을 처리해 모든 테스트를 통과했다.
참고
https://www.acmicpc.net/board/view/25456
import java.io.*;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
public class Main {
static int[] dx = {0, 0, -1, 1};
static int[] dy = {1, -1, 0, 0};
static boolean visit[][];
static int n, m;
static int graph[][];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int t = Integer.parseInt(br.readLine());
for (int i = 0; i < t; i++) {
solution(br, bw);
}
br.close();
bw.close();
}
private static void solution(BufferedReader br, BufferedWriter bw) throws IOException {
String[] op = br.readLine().split("");
int n = Integer.parseInt(br.readLine());
String line = br.readLine();
String line1 = line.substring(1, line.length() - 1);
String[] nums = line1.split(",");
Integer[] arr = new Integer[n];
Deque<Integer> deque;
boolean reverse = false;
if(line.equals("[]"))
deque = new ArrayDeque<>();
else {
for (int j = 0; j < n; j++) {
try {
arr[j] = Integer.parseInt(nums[j]);
} catch (NumberFormatException e) {
bw.write("error\n");
return;
}
}
deque = new ArrayDeque<>(Arrays.asList(arr));
}
for (String str : op) {
if (str.equals("R")) {
if (!deque.isEmpty()) {
reverse = !reverse;
}
} else if (str.equals("D")) {
if (!deque.isEmpty())
if (reverse)
deque.pollLast();
else
deque.pollFirst();
else {
bw.write("error\n");
return;
}
}
}
StringBuilder ans = new StringBuilder("[");
if (!reverse) {
if(!deque.isEmpty()) {
int len = deque.size();
for (int j = 0; j < len - 1; j++) {
ans.append(deque.pollFirst()).append(",");
}
ans.append(deque.pollFirst());
}
} else {
while (deque.size()>1) {
int a = deque.pollLast();
ans.append(a).append(",");
}
ans.append(deque.pollLast());
}
ans.append("]");
bw.write(ans + "\n");
}
}
Author And Source
이 문제에 관하여(백준 5340 풀이), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@estry/백준-5340-풀이저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)