시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 746 | 251 | 204 | 33.663% |
우리는 웹 페이지에 접속할 때 '웹 브라우저'를 사용한다. 웹 브라우저에는 크게 뒤로 가기(Backward), 앞으로 가기(Frontward), 웹페이지 접속(Access) 기능이 있다.
사용자가 웹 사이트에 접속하면 컴퓨터의 캐시(cache)공간에 웹페이지 정보가 저장된다. 그리고 뒤로 가기 또는 앞으로 가기 기능을 사용하면 캐시 공간에 저장되어 있던 페이지의 정보를 불러오게 된다. 여기에 주헌이가 개발한 웹 브라우저에는 신기한 기능이 있는데, 바로 압축(Compress)이라는 기능이다. 압축 기능은 뒤로 가기 공간에 같은 번호의 페이지가 연속해서 들어있을 때, 이를 하나로 줄일 수 있는 기능이다.
각 기능의 작동방식은 각각 다음과 같다.
Q개의 작업을 모두 마친 뒤에 현재 접속 중인 페이지와 뒤로 가기 공간, 앞으로 가기 공간에 저장되어 있는 페이지의 번호를 구하여라.
초기 상태에는 뒤로가기 공간, 앞으로 가기 공간이 모두 비어있으며 어떤 페이지에도 접속해있지 않는 상태이다. 또한 같은 번호의 페이지에 여러번 접속할 수 있으며, 그럴 경우 같은 번호의 페이지이라도 방문 순서는 각기 다르게 취급된다. 이 문제에서 컴퓨터의 캐시 용량은 충분히 크다고 가정한다.
첫째 줄에 접속할 수 있는 웹페이지의 종류의 수 N, 사용자가 수행하는 작업의 개수 Q 가 각각 주어진다.(1 ≤ N, Q ≤ 2,000)
둘째 줄부터는 Q개의 작업이 주어지며, 각 작업이 의미하는 바는 다음과 같다.
A(접속)작업이 적어도 한 번은 등장한다.
3줄에 걸쳐서 출력한다.
첫째 줄에는 현재 접속 중인 페이지의 번호를 출력한다.
둘째 줄에는 뒤로 가기 공간에서 가장 최근에 방문한 순서대로 페이지의 번호를 출력한다. 저장된 페이지가 없다면 -1
을 출력한다.
셋째 줄에는 앞으로 가기 공간에서 가장 최근에 방문한 순서대로 페이지의 번호를 출력한다. 저장된 페이지가 없다면 -1
을 출력한다.
3 11 B F A 1 A 1 A 2 A 3 B A 1 A 1 A 2 C
2 1 2 1 -1
2 8 A 1 A 1 A 2 A 2 A 2 B B C
2 1 2 2
3 8 A 1 A 2 A 1 A 2 C B A 3 A 1
1 3 1 2 1 -1
아래 그림은 에제 입력 1을 나타내고 있다.
파란색 도형 안에 숫자는 페이지의 번호를 나타내고 있다.
University > 아주대학교 > 2021 아주대학교 프로그래밍 경시대회 APC > Div.2 C번