[백준 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가 너무 편한걸 몸소 느낌

 

소스코드

 

 

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