문제 9
러브멜로디
정환이가 가장 좋아하는 음악에는 다음과 같은 멜로디가 등장한다.
AG.FE.D.정환이는 이 멜로디를 "러브멜로디"라고 부른다.
멜로디는 문자 A, B, C, D, E, F, G, .으로 이루어진 문자열이다.
정환이는 모든 음악에 러브멜로디가 등장하면 좋겠다고 생각하여, 멜로디의 음들을 재배치해 러브멜로디가 등장하도록 만들려고 한다.
.의 위치를 그대로 두고 나머지 문자들을 자유롭게 재배치할 수 있다.
주어진 멜로디를 재배치하여 러브멜로디가 연속해서 등장하도록 만들 수 있는지 판별하라.
입력
첫 번째 줄에 멜로디의 길이를 의미하는 정수 $N$이 주어진다. $(1 \le N \le 1\,000)$
두 번째 줄에 멜로디를 의미하는 문자열 $S$가 주어진다. $(\lvert S \rvert = N)$
출력
멜로디를 적절히 재배치해서 "러브멜로디"가 등장하도록 만들 수 있다면 Yes를, 그렇지 않다면 No를 출력한다.
예제 입력 1
8 AG.FE.D.
예제 출력 1
Yes
예제 입력 2
8 AGFED...
예제 출력 2
No
예제 입력 3
10 ABC.DE.F.G
예제 출력 3
Yes
공식 해설
.은 처음 위치에 고정되어 있고 나머지 문자만 자유롭게 움직일 수 있다. 따라서 필요한 문자의 개수와 점의 배치를 따로 확인한다.
AG.FE.D.를 만들려면 문자열 전체에 A, G, F, E, D가 각각 하나 이상 있어야 한다. 또한 길이 $8$인 구간 중 $3$, $6$, $8$번째만 .이고 나머지 다섯 자리는 모두 .이 아닌 구간이 있어야 한다.
두 조건이 모두 성립하면 그 구간의 점은 그대로 두고, 나머지 자리에 필요한 다섯 문자를 옮길 수 있다. 사용하지 않은 문자들은 남은 자리에 배치하면 된다. 반대로 문자나 점의 배치가 부족하면 재배치로 해결할 수 없다.
문자열의 길이를 $N$이라 하자. 문자 빈도를 센 뒤 모든 길이 $8$의 구간을 검사한다. $N<8$이면 가능한 구간이 없다. 시간복잡도는 $O(N)$, 문자열을 포함한 공간복잡도는 $O(N)$이다.
구현 · 언어별 풀이
C++ 구현
string과 문자 빈도 배열을 사용한다. 후보 시작점 $i$는 i + 8 <= N인 동안만 검사한다. 각 위치가 점인지 여부를 목표 문자열의 같은 위치와 비교하고, 필요한 다섯 문자의 빈도를 별도로 확인한다.
C 구현
문자열 전체에서 필요한 다섯 문자의 빈도를 센다. 길이 $8$의 창에서는 각 위치가 점인지 여부를 목표 문자열과 비교한다.
Python 구현
문자열 전체에서 필요한 다섯 문자의 빈도를 센다. 슬라이스나 인덱스로 길이 $8$의 창을 검사하여 각 위치가 점인지 여부를 목표 문자열과 비교한다.
Java 구현
String.charAt()으로 각 위치가 점인지 확인하고 int 빈도 배열로 필요한 문자의 개수를 센다.
Rust 구현
알파벳과 점만 나오므로 as_bytes()로 검사한다. 문자열 전체에서 필요한 다섯 문자의 빈도를 세고, 길이 $8$의 창에서는 각 위치가 점인지 여부를 목표 문자열과 비교한다. 길이가 $8$ 미만일 때 usize에서 8을 먼저 빼지 않는다.
JavaScript 구현
멜로디는 ASCII 문자이므로 s[i]로 한 음을 읽어도 된다. 문자열 전체에서 필요한 다섯 문자 각각의 존재를 확인하고, i + 8 <= s.length인 시작점에서 점의 위치를 검사한다.