[백준 5430] 알고리즘 10^2일차 : AC

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

5430번: AC

문자열 Java

R(순서 뒤집기)과 D(맨 앞 원소 제거)로 이루어진 일련의 명령을 입력받아 최종배열상태 혹은 error를 출력하는 문제

(어머 나 문제 요약 완전 잘해)

*error는 배열이 비어있는데 D를 수행할때 발생

 

접근방법

이 문제의 포인트는 선영이가 주말에 할 일이 없어서 새로운 언어 AC를 만들었다는 것.

은 아니고 R명령이 들어올 때마다 reverse같은 STL을 사용하면 안된다는 것. -> O(n)

Deque로 풀어야 합니다. boolean 변수하나 생성해서 포인터가 앞에 있는지 끝에 있는지 저장한다.

pointerFirst 변수 생성 초기값 true (포인터가 앞에 있음)

R명령 -> pointerFirst 토글! 

D명령 -> deque 비어있으면 -> error 

                deque 비어있지 않으면 -> 포인터가 앞쪽에 있으면 pollFirst() , 포인터가 끝에 있으면 pollLast()

 

마지막에 출력할땐

error 면 에러 출력

error 없고 포인터가 앞에 있으면 dq 그대로 출력,

                 포인터가 뒤에 있으면 reverse 해서 출력 (이때 deque -> array -> list) 해줌..

그리고 공백 모두 지워줌

 

오답노트

처음에 신나게 arrayList로 만들고 R명령 마다 Collections.reverse를 수행해줬다.

다 풀고 나니까 이게 골5..? 합리적의심이 들었다. 역시나 시간초과

Java로 문제 푸는거에 아직 안익숙해서 io로 Scanner와 sout쓰고 있었는데

이것도 BufferedReader&Writer로 바꿔줬다. 하지만 여전히 시간초과라 FAQ봤는데 reverse쓰면 안된다고 되어있어서

deque로 풀었다.

 

새삼 모든 문자열 관련 문제는 Java가 너무 편한걸 몸소 느낌

 

소스코드

 

	import java.io.*;
	import java.util.*;
	public class S5430 {
	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 t = 0; t < T; t++) {
	String func = br.readLine();
	int n = Integer.parseInt(br.readLine());
	String arr = br.readLine();
	arr = arr.substring(1, arr.length() - 1);
	List<String> sl = new ArrayList<>(Arrays.asList(arr.split(",",n).clone()));
	if(n == 0){
	sl.removeAll(sl);
	}
	Deque<String> dq = new ArrayDeque<>(sl);
	boolean error = false;
	boolean pointerFirst = true;
	for (char p : func.toCharArray()) {
	if (p == 'R') {
	pointerFirst = !pointerFirst;
	} else {
	//p == 'D'
	if (dq.isEmpty()) {
	error = true;
	break;
	} else {
	if(pointerFirst){
	dq.pollFirst();
	}else{
	dq.pollLast();
	}
	}
	}
	}
	if(error){
	bw.write("error\n");
	} else {
	if (pointerFirst) {
	bw.write(dq.toString().replaceAll(" ","")+"\n");
	}
	else {
	List<Object> result = Arrays.asList(dq.toArray());
	Collections.reverse(result);
	bw.write(result.toString().replaceAll(" ","")+"\n");
	}
	}
	}
	br.close();
	bw.close();
	}
	}

view raw S5430 hosted with ❤ by GitHub

 

ㅎ git gist 쓰고 싶어서 다시올립니다~