3876번 - sed 이용 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 76 | 28 | 25 | 54.348% |
문제
sed는 입력으로 주어지는 문자열에 등장하는 문자열 α를 다른 문자열 β로 바꾸는데 사용되는 리눅스 유틸이다. 여기서 입력으로 주어지는 문자열은 파일의 각 한 줄이다. sed는 다음과 같은 2가지 과정을 거친다.
- 입력 문자열에서 겹치지 않는 α를 표시한다. 이때, α가 서로 겹칠 수는 있다. 만약, 겹치지 않게 선택하는 경우가 여러 가지 있을 때는 가장 왼쪽 것을 선택한다.
- 위에서 표시한 모둔 문자열 α를 문자열 β로 바꾼다. 나머지 문자는 바꾸지 않고 그대로 놔둔다.
예를 들어, α가 "aa"이고, β가 "bca", 입력 문자열이 "aaxaaa"라면 sed를 실행한 결과는 "bcaxbcaa"가 된다. ("aaxbcaa", "bcaxabca"는 될 수 없다) 이 결과 "bcaxbcaa"를 가지고 다시 sed를 실행하면 결과는 "bcaxbcbca"가 된다.
문자열을 바꾸는 규칙의 쌍 (αi, βi) (i = 1,2,...,n), 초기 문자열 γ, 최종 문자열 δ가 주어진다. 이때, sed를 이용해서 γ를 δ로 바꿀 때, 문자열 바꾸는 회수의 최솟값을 구하려고 한다.
하나의 규칙(αi, βi)은 위에서 설명한 것 같이, 입력 문자열에서 겹치지 않는 모든 부분 문자열 αi를 βi로 동시에 바꾸는 것을 의미한다.
한 규칙(αi, βi)을 여러 번 사용해도 되고, 사용하지 않아도 된다.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 다음과 같은 형식이다.
n α1 β1 α2 β2 ... αn βn γ δ
n은 문자열을 바꾸는 규칙의 쌍의 개수이다. αi와 βi는 공백으로 구분되어 있으며, 1 ≤ |αi| < |βi| ≤ 10을 만족한다. (|s|는 문자열 s의 길이) 모든 i≠j에 대해서 αi≠αj이며, n ≤ 10, 1 ≤ |γ| < |δ| ≤ 10 이다. 모든 문자열을 알파벳 소문자로만 이루어져 있고, 입력의 마지막 줄에는 0이 하나 주어진다.
출력
각 테스트 케이스에 대해서, γ를 δ로 바꿀 때 필요한 문자열 바꾸는 회수의 최솟값을 출력한다. 만약 γ를 δ로 바꿀 수 없다면, -1을 출력한다.
예제 입력 1
2 a bb b aa a bbbbbbbb 1 a aa a aaaaa 3 ab aab abc aadc ad dee abc deeeeeeeec 10 a abc b bai c acf d bed e abh f fag g abe h bag i aaj j bbb a abacfaabe 0
예제 출력 1
3 -1 7 4
출처
ICPC > Regionals > Asia Pacific > Japan > Asia Regional Contest 2009 in Tokyo B번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호