호텔리어

면접 대비

시간 제한1초메모리 제한256 MB

요약

방이 10개인 호텔에서 왼쪽이나 오른쪽 입구로 들어온 손님을 가장 가까운 빈 방에 배정하고, 퇴실 기록을 반영해 마지막 방 상태를 출력합니다.

문제

아무개는 방이 10개인 호텔을 운영한다. 방은 왼쪽에서 오른쪽으로 0번부터 9번까지 번호가 매겨져 있다.

호텔에는 입구가 두 개 있다. 하나는 왼쪽 끝에, 다른 하나는 오른쪽 끝에 있다. 손님이 왼쪽 입구로 들어오면 빈 방 중 왼쪽 입구에서 가장 가까운 방에 배정된다. 마찬가지로 오른쪽 입구로 들어오면 빈 방 중 오른쪽 입구에서 가장 가까운 방에 배정된다.

어느 날 아무개가 방 배정 목록을 잃어버렸다. 다행히 아무개는 기억력이 완벽해서, 손님이 언제 어느 입구로 왔고 언제 떠났는지 모두 기억하고 있다. 처음에 호텔은 비어 있었다. 아무개의 기억을 바탕으로 방 배정 목록을 복원하는 프로그램을 작성하라.

첫 줄에 아무개의 기억에 있는 사건의 수 $n$ ( $1 \le n \le 10^5$ )이 주어진다.

둘째 줄에는 사건을 시간 순서대로 나타낸 길이 $n$ 의 문자열이 주어진다. 각 문자의 의미는 다음과 같다.

손님이 들어올 때는 항상 빈 방이 하나 이상 있다. 숫자가 주어지면 그 방에는 반드시 손님이 있다. 처음에는 모든 방이 비어 있다.

방 $0$ 부터 $9$ 까지의 배정 상태를 한 줄에 출력한다. 빈 방은 0, 손님이 있는 방은 1로 나타내며, 공백 없이 출력한다.

첫 번째 예제에서 각 동작 후의 상태는 다음과 같다.

따라서 최종 상태는 1010000011이다.

두 번째 예제에서 각 동작 후의 상태는 다음과 같다.

따라서 최종 상태는 1100000010이다.