문제
KSAAC 운영진은 모두 KSA를 사랑하기 때문에 다음과 같은 조건을 만족하는 문자열을 좋아한다.
문자열의 길이를 N이라고 할 때, 1 <= i <= N인 모든 i에 대하여
- i를 3으로 나눈 나머지가 1이면 i번째 문자는 K이다.
- i를 3으로 나눈 나머지가 2이면 i번째 문자는 S이다.
- i를 3으로 나눈 나머지가 0이면 i번째 문자는 A이다.
문자열에는 다음과 같은 시행을 0회 이상 수행할 수 있다.
- 존재하는 아무 문자를 한 개 제거한다.
- 맨 앞에 아무 문자를 한 개 추가한다.
- 맨 뒤에 아무 문자를 한 개 추가한다.
주어진 문자열 X에 적절한 시행을 하여 X를 X와 길이가 같으면서 KSAAC 운영진이 좋아하는 문자열로 바꾸려고 한다. 이때 필요한 시행의 최소 횟수를 구하여라.
입력
첫 번째 줄에 문자열 X가 주어진다.
출력
문자열 X를 X와 길이가 같으면서 KSAAC 운영진이 좋아하는 문자열로 바꾸기 위한 최소 시행 횟수를 출력한다.
풀이
핵심은 결국 KSA가 반복되는 패턴 중 어떤 시작 위치에 가장 길게 맞출 수 있는지를 보는 것이다. 시작 패턴은 KSA, SAK, AKS 세 가지뿐이다.
코드의 findString()은 원본 문자열을 앞에서부터 훑으며 목표 패턴과 일치하는 문자를 최대 몇 개까지 subsequence 형태로 뽑아낼 수 있는지 센다. 세 시작 패턴 각각에 대해 최대 매칭 길이를 구한 뒤, 가장 긴 값을 기준으로 필요한 연산 수를 계산한다.
왜 세 가지 패턴만 보면 되느냐면, 반복 문자열 KSAKSA...는 시작 위치를 어디에 두느냐에 따라 결국 KSA, SAK, AKS 세 회전 중 하나로만 나타나기 때문이다. 각 경우에 대해 현재 문자열에서 순서를 지키며 최대 몇 글자를 살릴 수 있는지만 알면, 나머지 글자는 삽입과 삭제로 맞출 수 있다.
코드에서 sak, aks에 대해 길이를 한 번 더 제한하는 부분은, 시작 위치를 밀어 놓은 만큼 실제로 만들 수 있는 반복 문자열의 길이를 맞추기 위한 처리다. 최대로 남길 수 있는 글자 수를 구한 뒤 (원래 길이 - 남길 수 있는 길이) * 2로 필요한 연산 수를 계산한다.
코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String X = br.readLine();
System.out.println(solve(X));
}
static int solve(String X) {
int ksa = findString(X, "KSA");
int sak = Math.min(findString(X, "SAK"), X.length() - 1);
int aks = Math.min(findString(X, "AKS"), X.length() - 2);
int ans = Math.max(Math.max(ksa, sak), aks);
return (X.length() - ans) * 2;
}
static int findString(String a, String b) {
int cnt = 0;
for (char c : a.toCharArray())
if (c == b.charAt(cnt % 3)) cnt++;
return cnt;
}
}복잡도
- 시간 복잡도:
- 공간 복잡도:
마무리
패턴이 복잡해 보여도 시작 위치는 세 가지뿐이다. 결국 가장 길게 맞출 수 있는 반복 subsequence를 찾는 문자열 그리디 문제로 볼 수 있다.
