문제
https://www.acmicpc.net/problem/5430
예제
태그
- 구현
- 자료 구조
- 문자열
- 파싱
- 덱
풀이
덱을 사용하지 않고 arraylist를 이용하여 reverse, delete를 할 경우 시간초과가 난다.
덱을 사용하여 reverse를 직접하지 않고 포인터를 사용하여 앞, 뒤만 delete를 해줘 시간초과를 막는다.
코드
처음 시간초과 코드
/**
* 시간 초과 코드
* Arraylist 사용
* collections.reverse() 사용
* d_cnt의 개수를 세서 그 개수가 n보다 크면 error
* 시간 복잡도 : T(100) * P(100000) * N(100000) * N(100000)
*/
package implement;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
public class P_5430 {
static int T;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
T = Integer.parseInt(br.readLine());
for (int tc = 0; tc < T; tc++) {
String P = br.readLine();
int d_cnt = 0; // D의 개수
for (int i = 0; i < P.length(); i++) {
if(P.charAt(i) == 'D'){
d_cnt++;
}
}
int n = Integer.parseInt(br.readLine());
String arr_input = br.readLine();
// D의 개수가 n보다 크면 error
if(d_cnt > n){
System.out.println("error");
}
else{
// 입력받은 것을 arraylist에 저장
String input = "";
for (int i = 0; i < arr_input.length(); i++) {
if(arr_input.charAt(i) == '[' || arr_input.charAt(i) == ']'){
continue;
}
else{
input += arr_input.charAt(i);
}
}
StringTokenizer st = new StringTokenizer(input, ",");
ArrayList<Integer> num = new ArrayList<>();
for (int i = 0; i < n; i++) {
num.add(Integer.parseInt(st.nextToken()));
}
// Arraylist인 num을 주어진 P에 따라 조작
for (int i = 0; i < P.length(); i++) {
if(P.charAt(i) == 'R'){
reverse(num);
}
else{
delete(num);
}
}
// answer를 출력
String answer = "[";
for(int val : num){
answer += Integer.toString(val) + ",";
}
answer = answer.substring(0, answer.length()-1);
answer += "]";
System.out.println(answer);
}
}
}
// R : 뒤집는 메서드
static ArrayList<Integer> reverse(ArrayList<Integer> arr){
Collections.reverse(arr);
return arr;
}
// D : arraylist의 처음을 삭제
static ArrayList<Integer> delete(ArrayList<Integer> arr){
arr.remove(0);
return arr;
}
}
정답 코드
/**
* 앞서 푼 문제 시간초과 이유
* 1) R : collections.reverse() 사용 -> O(n^2) 시간초과
* 2) 배열 입력을 받을 때 그것을 String으로 저장하고 [, ] 를 제거한 새로운 String을 또 생성
* 그리고 그것을 ,로 구분한 StringTokenizer를 사용하여 시간초과
*
* 해결책
* 1) deque를 사용하여 앞 또는 뒤를 제거
* -> boolean형 isFirst를 생성하여 true이면 포인터가 앞, false이면 포인터가 뒤로 설정
* -> D를 만나면 포인터 위치에서 제거
* 2) 배열 입력을 받고 바로 substring함수를 사용하여 [ ] 제거
* -> split(,)을 사용하여 바로 숫자만 deque에 저장
*/
package implement;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
public class P_5430 {
static int T; // 전체 Test case 수
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
T = Integer.parseInt(br.readLine());
for (int tc = 0; tc < T; tc++) {
String P = br.readLine(); // R,D 명령어
int n = Integer.parseInt(br.readLine()); // 숫자 배열 수
String arr_input = br.readLine(); // 입력받은 배열
Deque<Integer> deque = new ArrayDeque<>(); // 문제 해결을 위한 deque
// [ ] 제거 후 ,로 구분하여 숫자만 deque에 저장
for(String s : arr_input.substring(1, arr_input.length()-1).split(",")){
// 조건문을 걸어주지 않으면 맨 마지막 테스트 케이스처럼 [] 아무것도 들어오지 않을 때 nullpointerror가 난다
if(!s.equals("")){
deque.add(Integer.valueOf(s));
}
}
boolean isFirst = true; // 포인터가 맨 앞인지 뒤인지 체크하는 변수
boolean flag = false; // 답을 나타내기 위한 변수 -> true면 error
for (int i = 0; i < P.length(); i++) {
// reverse
if(P.charAt(i) == 'R'){
isFirst = !isFirst; // 뒤집어준다
}
// delete
else{
if(deque.size() == 0){
flag = true;
break;
}
// 포인터가 맨 앞이면 deque에서 맨 앞 제거
if(isFirst){
deque.pollFirst();
}
// 포인터가 맨 뒤이면 deque에서 맨 뒤 제거
else{
deque.pollLast();
}
}
}
if(flag){
System.out.println("error");
}
else{
StringBuilder sb = new StringBuilder("[");
while(!deque.isEmpty()){
// isFirst == true : 맨 앞부터 출력
if(isFirst){
sb.append(deque.pollFirst());
}
// isFirst == false : 맨 뒤부터 출력
else{
sb.append(deque.pollLast());
}
if(deque.size() != 0){
sb.append(',');
}
}
sb.append(']');
System.out.println(sb.toString());
}
}
}
}
출처
안녕하세요