샘은 외부 세계랑 통신할 수 있는 고대 통신 채널을 발견했다. 하지만 채널 속도가 매우 느려 샘과 그의 친구들은 압축 코드를 사용해 더 빨리 통신하고자 한다. 샘은 고민 끝에 이진 접두사 코드를 사용하고자 한다.
접두사 코드는 시스템에서 유효한 코드가 다른 코드의 접두사가 아닌 가변 길이 코드 시스템이다. 예를 들어 {a=0,b=10,c=11}은 접두사 코드지만 {a=0,b=10,c=01}은 그렇지 않습니다. 왜냐하면 0은 01의 접두사기 때문이다.
이런 접두사 코드(0과 1로 구성된 코드)는 이진 트리로 표현될 수 있으며, 여기서 기호는 leaf고 루트에서 leaf까지 경로를 해당 코드로 제공한다. 간단히 말해 왼쪽 아래(자식)로 가는 경로는 0,오른쪽 아래(자식)로 가는 경로는 1이라고 가정한다.(전형적인 이진트리) 예를 들어, 아래의 그림은 {a=0, b=10, c=11} 및 {a=000, b=001, c=01, d=10, e=110, f=111}을 이진 트리를 사용해 표현한 그림이다. 아래 그림에서 k는 깊이다.
또한 이진트리는 문자열을 사용해 압축적으로 표현할 수 있다. 트리의 루트 노드가 인덱스 0에 있고, 노드의 왼쪽 자식과 오른쪽 자식이 각각 2k+1,2k+2에 있다고 가정한다. 표현한 문자열의 예시로 *a***bc 이런 식으로 표현이 가능하며, *는 정보가 없는 leaf를 표현한다.
샘과 그의 친구들은 이진 접두사 코드를 사용해 메시지를 이진 형태로 압축해 빠른 전송이 가능해졌다. 압축된 메시지는 루트 노드에서 시작해 왼/오 자식으로 이동하는 이진 트리를 사용해 다음 값이 0인지 1인지에 따라 디코딩이 가능해졌다. 문자를 나타내는 leaf 노드에 도달하면 문자가 출력되고, 루트노드에 재시작해 나머지 메시지 디코딩이 가능하다.
당신은 문자열 형식으로 제공된 이진 접두사 코드를 사용해 샘이 이진 숫자로 인코딩된 문자열을 디코딩하는 프로그램을 짜라.
입력 첫 번째 줄에는 테스트케이스 수인 T를 입력받는다. 그 다음 줄에는 각 테스트케이스마다 입력받는데, 디코딩할 문자 수, 이진 접두사 코드 문자열, 디코딩할 문자의 수만큼 디코딩해야할 문자열 k를 입력받는다. 디코딩할 모든 문자열은 접두사 코드에 있는 문자로 구성되어 있다.
wlskrla7 1년 전 1
샘은 외부 세계랑 통신할 수 있는 고대 통신 채널을 발견했다. 하지만 채널 속도가 매우 느려 샘과 그의 친구들은 압축 코드를 사용해 더 빨리 통신하고자 한다. 샘은 고민 끝에 이진 접두사 코드를 사용하고자 한다.
접두사 코드는 시스템에서 유효한 코드가 다른 코드의 접두사가 아닌 가변 길이 코드 시스템이다. 예를 들어 {a=0,b=10,c=11}은 접두사 코드지만 {a=0,b=10,c=01}은 그렇지 않습니다. 왜냐하면 0은 01의 접두사기 때문이다.
이런 접두사 코드(0과 1로 구성된 코드)는 이진 트리로 표현될 수 있으며, 여기서 기호는 leaf고 루트에서 leaf까지 경로를 해당 코드로 제공한다. 간단히 말해 왼쪽 아래(자식)로 가는 경로는 0,오른쪽 아래(자식)로 가는 경로는 1이라고 가정한다.(전형적인 이진트리) 예를 들어, 아래의 그림은 {a=0, b=10, c=11} 및 {a=000, b=001, c=01, d=10, e=110, f=111}을 이진 트리를 사용해 표현한 그림이다. 아래 그림에서 k는 깊이다.
또한 이진트리는 문자열을 사용해 압축적으로 표현할 수 있다. 트리의 루트 노드가 인덱스 0에 있고, 노드의 왼쪽 자식과 오른쪽 자식이 각각 2k+1,2k+2에 있다고 가정한다. 표현한 문자열의 예시로 *a***bc 이런 식으로 표현이 가능하며, *는 정보가 없는 leaf를 표현한다.
샘과 그의 친구들은 이진 접두사 코드를 사용해 메시지를 이진 형태로 압축해 빠른 전송이 가능해졌다. 압축된 메시지는 루트 노드에서 시작해 왼/오 자식으로 이동하는 이진 트리를 사용해 다음 값이 0인지 1인지에 따라 디코딩이 가능해졌다. 문자를 나타내는 leaf 노드에 도달하면 문자가 출력되고, 루트노드에 재시작해 나머지 메시지 디코딩이 가능하다.
당신은 문자열 형식으로 제공된 이진 접두사 코드를 사용해 샘이 이진 숫자로 인코딩된 문자열을 디코딩하는 프로그램을 짜라.
입력
첫 번째 줄에는 테스트케이스 수인 T를 입력받는다.
그 다음 줄에는 각 테스트케이스마다 입력받는데, 디코딩할 문자 수, 이진 접두사 코드 문자열, 디코딩할 문자의 수만큼 디코딩해야할 문자열 k를 입력받는다. 디코딩할 모든 문자열은 접두사 코드에 있는 문자로 구성되어 있다.
출력
각 테스트 케이스마다, 디코딩한 문자를 출력한다.