영화관 좌석 단말 패킷 복구

문제

영화관 좌석 단말은 중앙 장치로 바이트 스트림을 보낸다. 스트림에서 프레임은 다음과 같이 구성된다. 맨 앞 1바이트는 동기 바이트 0xA5이다. 다음 1바이트는 페이로드 길이 L (0 ≤ L ≤ 255)이다. 이어서 L바이트의 페이로드가 오고, 마지막 1바이트는 체크섬이다. 체크섬은 길이 바이트와 페이로드 L바이트를 모두 XOR한 값을 8비트 비트 반전(0xFF와 XOR)한 값이다. 즉 프레임의 전체 길이는 L + 3바이트이다. 수신기는 스트림의 위치 0부터 다음 규칙으로 파싱한다. 현재 위치를 i라 하자. 1. i번 바이트가 0xA5이고, 프레임이 스트림 안에 끝까지 들어가며(체크섬 위치 i+2+L이 스트림의 마지막 바이트 위치 이하), 체크섬이 올바르면 이 프레임을 정상 프레임으로 인정하고 i를 L+3만큼 증가시킨다. 인정된 프레임의 내부 바이트는 다시 검사하지 않는다. 2. 그 외의 모든 경우(동기 바이트가 아님, 프레임이 잘렸음, 체크섬 불일치)에는 i를 1만 증가시킨다. i가 스트림 길이에 이를 때까지 반복한다. L이 1 이상인 정상 프레임은 페이로드 첫 바이트의 상위 3비트(값 0~7)를 프레임 종류로 갖는다. L이 0인 프레임은 어떤 종류에도 속하지 않는다. 정상 프레임의 수, 어떤 정상 프레임에도 속하지 않은 바이트의 수, 그리고 종류 0~7 각각의 정상 프레임 수를 구하는 프로그램을 작성하시오.

입력

첫 줄에 스트림의 바이트 수 N이 주어진다. (1 ≤ N ≤ 200,000) 둘째 줄에 스트림을 바이트당 두 자리 16진수(대문자 0-9, A-F)로 공백 없이 이어 붙인 길이 2N의 문자열이 주어진다.

출력

첫 줄에 정상 프레임의 수와 정상 프레임에 속하지 않은 바이트의 수를 공백으로 구분하여 출력한다. 둘째 줄에 종류 0부터 7까지의 정상 프레임 수를 공백으로 구분하여 출력한다.

20
A5024007BA11A500FFA501E31DA5012000A50501

3 8
0 0 1 0 0 0 0 1

6
A503A500FF00

1 3
0 0 0 0 0 0 0 0

6
A503A500FFA6

1 0
0 0 0 0 0 1 0 0

출처: Devin.KR 자체 제작