[BOJ] 백준 5430 AC (Swift)

문제

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

5430번: AC

풀이

먼저, 입력에 괄호가 들어있어서 이를 제거해주어야 합니다.
dropFirst, dropLast 메서드를 사용해서 괄호를 제거할 수 있습니다.
그 이후 "," 문자열을 기준으로 나누어 줍니다.

입력을 파싱해서 Array로 만들어 주었습니다.

함수는 "R"(뒤집기)과 "D"(버리기)로 두가지로 이루어져있습니다.

뒤집는 것은 revsersed 메서드, 버리는 것은 removeFirst를 사용할 수 있을 것 같은데
이 둘은 시간 복잡도가 $O(n)$ 입니다.

함수가 최대 10만의 길이이고 array도 최대 10만 이므로,
함수를 수행하면서 array에 reversed, removeFirst를 사용하면 $O(n^2)$의 시간 복잡도가 예상이 되는데,
이는 100억 이므로 시간내에는 해결할 수 없습니다.

그러면 어떻게 해야할까요?

저는 head, tail이라는 index를 가리킬 두개의 포인터를 변수로 작성하였습니다.
초기에 head는 0번을 가리키고, tail은 배열의 크기를 가리키도록 하였습니다.
만약 D가 들어왔다면 head에 1을 더해주고, 나중에 출력할 때, head부터 tail 까지의 요소들만 출력해주면 되지않을까요?

R 연산은 배열을 뒤집게 되는데 실제로 뒤집진 않고, 뒤집어져 있다고만 생각을 하고
뒤집어져 있다면 tail에 1을 빼주어서 뒤집어서 버린것과 같이 구현할 수 있습니다.

뒤집어져 있는지 확인할 수 있는 변수를 하나 따로 두었고,
R 함수가 들어오면 toggle 해주었습니다.

에러는 어떻게 알 수 있을까요?
head가 tail 보다 커진다면 배열이 비어있는 경우에 D 연산을 수행한 것이므로 에러입니다.

이제 head 부터 tail 까지의 요소를 출력해주면 되는데 뒤집어져 있다면 뒤집어서 출력해주고,
올바르게 있다면 그냥 출력해주면 끝 입니다.

소스코드

후기

head, tail이라는 index를 가리킬 두개의 포인터 아이디어를 떠올리는게 핵심이였던 문제입니다.