두 출력 목록을 문자열 first, second로 표현해요. 매번 둘 중 하나의 아직 출력하지 않은 첫 문자를 꺼내 이어 붙여요. 각 목록 안의 원래 순서는 유지해야 해요. 모든 문자를 한 번씩 써서 target을 만들고, 같은 목록에서 연속으로 선택하는 횟수는 limit 이하여야 해요.
solution(first, second, target, limit)가 가능하면 1, 불가능하면 0을 반환하도록 작성해 주세요. 같은 문자가 두 목록에 있어도 어느 목록에서 선택했는지에 따라 연속 횟수가 달라져요.
매개변수와 반환값
- first와 second의 길이는 각각 0~6, 영문 소문자만 포함해요. 둘 다 빈 문자열이어도 돼요.
- target 길이는 두 길이의 합이며 영문 소문자만 포함해요.
- limit는 1~3이에요. 빈 target은 두 목록이 모두 비어 있으면 만들 수 있어요.
- 반환값은 0 또는 1인 정수예요.
예시
first = 'ab',second = 'cd',target = 'acbd',limit = 1이면 결과는1이에요.first = 'ab',second = 'cd',target = 'abcd',limit = 1이면 결과는0이에요.
실행용 입출력
첫 줄에 limit, 다음 세 줄에 first, second, target을 차례대로 입력해요. 빈 문자열은 빈 줄이에요. 결과 하나를 출력해요.
예시 입력
1 ab cd acbd
예상 결과
1
예시 입력
1 ab cd abcd
예상 결과
0
핵심 개념
dp-2d: first에서 쓴 문자 수 i와 second에서 쓴 문자 수 j에 따라 다음 문자가 달라져요. 여기에 마지막 목록과 연속 선택 횟수도 붙여 상태를 구분해요.array-1d: 문자열의first[i]는 다음에 꺼낼 문자예요. 문자열이 비어 있을 수 있으므로 인덱스로 읽기 전에 길이를 확인해요.conditionals: 문자가 같아도 두 목록 선택을 각각 검토해야 해요. 하나를 먼저 골라 버리면 뒤에서 가능한 경로를 놓칠 수 있어요.
(i, j, last, run)은 네 값을 묶은 튜플이에요. last는 first를 선택했으면 0, second를 선택했으면 1이에요. 시작 상태에서는 아직 선택한 목록이 없어 last를 2, 연속 횟수를 0으로 두어요. 첫 선택의 연속 횟수는 1로 시작해요. 집합 set()에 튜플을 넣으면 같은 상태의 중복을 없앨 수 있어요. .add(tuple)은 상태를 추가해요. value if condition else other는 조건에 따라 값을 고르고, any(...)는 하나라도 참이면 참이에요. int(True)는 1, int(False)는 0이에요.
첫 예시에서는 처음 (0,0,2,0)에서 first의 a를 고르면 (1,0,0,1), 다음 second의 c를 고르면 (1,1,1,1)이 돼요. i·j는 각 목록에서 이미 쓴 문자 수, run은 마지막 목록에서 연속으로 선택한 횟수예요. 현재 target 문자 하나를 읽은 결과는 next_states에 따로 모으고, 그 문자의 모든 선택을 확인한 뒤 states를 바꿔요. 그래야 같은 target 문자를 한 반복 안에서 여러 번 쓰지 않아요.