문자열 추측
면접 대비시간 제한2초메모리 제한512 MB
숨겨진 문자열의 길이 N-1 이하인 모든 접두사와 접미사 2N-2개가 주어질 때, 원래 문자열을 복원하고 각 입력 줄이 접두사인지 접미사인지 순서대로 판별한다.
문제
길이가 N인 문자열 S가 있다. S는 알파벳 소문자로만 이루어져 있다.
문자열 S의 길이가 N-1 이하인 모든 접두사와 접미사를 이용해 원래 문자열 S를 만들어보려고 한다. S의 모든 접두사와 접미사가 주어졌을 때, 원래 문자열 S가 무엇인지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 문자열 S의 길이 N(2 ≤ N ≤ 100)이 주어진다. 다음 2N-2개의 줄에 걸쳐서 문자열 S의 접두사와 접미사가 한 줄에 하나씩 주어진다. 모든 접두사와 접미사가 주어지기 때문에, 길이가 i(1 ≤ i ≤ N-1)인 문자열의 개수는 항상 2개이다.
출력
첫째 줄에 입력으로 주어진 접두사와 접미사를 이용해 만들 수 있는 문자열 S를 출력한다.
둘째 줄에는 입력으로 주어진 문자열이 접두사이면 'P', 접미사이면 'S'를 순서대로 출력한다.
힌트
문자열 S의 접두사는 S의 부분 문자열 중에서 시작이 첫 번째 문자인 것이고, 접미사는 끝이 마지막 문자인 것이다.
S = "hello"인 경우 접두사는 다음과 같이 5가지가 있다.
- h
- he
- hel
- hell
- hello
접미사는 다음과 같다.
- o
- lo
- llo
- ello
- hello