9236번 - 고급 레스토랑 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 128 MB | 75 | 13 | 11 | 22.449% |
문제
상근이는 고급 레스토랑을 하나 운영하고 있다. 후쿠시마 원자력 발전소 사고 이후로 국민들은 방사능에 큰 두려움을 가지게 되었다. 정부는 총 M종류의 재료에 포함된 방사능은 위험한 수준이라 판단했고, 이 재료는 요리에 조금도 사용하지 못하는 법을 제정했다.
모든 재료는 숫자(0-9)로만 이루어진 시리얼 번호를 가지고 있다. 상근이의 레스토랑에서는 만드는 음식의 개수는 하나이다. 상근이는 이 음식에 들어가는 모든 재료의 시리얼 번호를 알고 있다.
상근이는 각각의 재료가 방사능에 오염되었는지 판단해야 한다. 하지만, 상근이는 매우 게으른 아이이기 때문에, 요리에 들어가는 모든 재료의 시리얼 번호를 하나로 합쳐서 길이가 N인 문자열을 만든 다음 검사하려고 한다.
선영이가 운영하는 근처 음식점에서는 로봇을 이용해 자동으로 검사를 한다. 상근이는 선영이에게 부탁해 이 로봇을 빌려왔다.
로봇은 시리얼 번호 A에 시리얼 번호 B가 포함되었는지를 검사한다. 로봇은 아래와 같은 과정으로 검사를 수행한다. (B의 길이 = L)
- 먼저, A의 첫 번째 숫자부터 L번째 숫자까지 부분 문자열을 B의 숫자와 앞에서 부터 하나씩 비교한다. 서로 다른 숫자를 발견하거나, 마지막 숫자까지 비교했으면, 비교를 종료한다. 두 숫자가 같으면 성공 알림을 보여준 다음 검사를 종료한다.
- 위의 과정에서 검사가 종료되지 않았다면, 2번째 숫자부터 L+1번째 숫자를 비교한다. 그래도 같지 않다면, 3번째 부터 L+2번째, 4번째 부터 L+3번째, ... 와 같은 순서로 계속 검사를 수행한다.
- 검사를 해야 하는 부분 문자열의 길이가 L보다 작은 경우가 존재할 수도 있다. (A의 길이가 8일 때, 5번째 문자부터 검사를 시작하는 경우) 이런 경우에는 길이가 L이 될 때 까지 뒤에 '#'를 붙여 검사를 한다. 예를 들어, "563232"의 4번째 위치부터 10번째 위치까지 부분 문자열은 "232####"이 된다.
- 총 N개의 부분 문자열을 모두 검사했는데도 같은 부분을 찾지 못한 경우에는 실패 알림을 보여주고 검사를 종료한다.
상근이는 로봇이 두 숫자를 한 번 비교할 때마다 선영이에게 1원을 내야한다.
상근이가 지불해야 하는 돈은 얼마일까?
입력
첫째 줄에 음식에 포함되는 시리얼 번호를 길게 이어 붙인 문자열의 길이 N이 주어지고, 둘째 줄에 시리얼 번호가 주어진다. (1 ≤ N ≤ 100,000)
셋째 줄에는 금지된 재료의 수 M이 주어진다. (1 ≤ M ≤ 50,000) 다음 M개 줄에는 금지된 시리얼 번호가 하나씩 주어진다.
시리얼 번호는 총 0부터 9까지 숫자로만 이루어져 있고, 금지된 시리얼 번호의 길이는 100,000를 넘지 않는다. 또, 금지된 시리얼 번호의 길이의 총 합은 3,000,000을 넘지 않는다.
출력
각각의 재료를 검사할 때, 선영이에게 지불해야 하는 금액을 출력한다.
예제 입력 1
7 1090901 4 87650 0901 109 090
예제 출력 1
7 10 3 4
첫 번째 시리얼 번호는 모든 부분 문자열의 첫 번째 숫자에서 검사가 실패한다. 따라서, 비교 횟수는 총 7번이다.
두 번째 시리얼 번호의 경우에는 첫 번째 숫자에서 시작했을 때 비교 1번, 두 번째 숫자에서 시작했을 때, 비교 4번, 세 번째 숫자에서는 비교 1번, 네 번째 숫자에서는 비교 4번을 하게 된다. 네 번째 숫자에서 시작했을 때, 문자열이 일치하는 것을 발견하기 때문에 검사를 종료한다.
세 번째 시리얼 번호는 비교 3번, 네 번째 시리얼 번호는 비교 (1 + 3) 4번이다.
예제 입력 2
10 5821052680 4 210526 2105 582 105268
예제 출력 2
8 6 3 9
예제 입력 3
3 001 1 11
예제 출력 3
4
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호