백준 1512: 주기문으로 바꾸기 [Kotlin 코틀린 / 문자열]

백준 1512: 주기문으로 바꾸기

😶‍🌫️ 문제 분석

문자열을 반복되는 형태로 바꾸어야 한다.
이때 반복되는 길이는 M 이하인데,
만약에 M = 3이라면,
0, 3, 6, 9, ... 인덱스에 존재하는 문자가
1, 4, 7, 10, ... 인덱스에 존재하는 문자가
2, 5, 8, 11, ... 인덱스에 존재하는 문자가 같도록 바꾸는 것이다.
그리고 바뀌는 문자의 개수를 최소로 만들어야 한다.

✅ 문제 풀이

문제에 실수할 만한 포인트가 꽤 있다.

첫번째로, 반복되는 형태가 무조건 문자열의 맨 앞에 존재하는 게 아니라는 것이다.
만약 ATCGCG라는 문자열이 있고, M=2라고 해보자.
이때는 맨 앞 문자열 AT에 맞춰서 다른 문자열을 바꿔야 될 게 아니라,
맨 앞 문자열 AT를 CG로 바꿔주는 게 정답이다.

둘째로, 붙어있는 문자열만이 답의 후보는 아니라는 것이다.
ATGCTCAGC라는 문자열이 있고, M=3라면,
ATCATCATC라는 문자열로 바꾸는 것이 최소화 하는 방법이다.
ATGATGATG, CTCCTCCTC, AGCAGCAGC는 정답이 아니다.

결국 문자열을 주기문으로 바꿀 때, 바꾸는 문자열의 개수를 최소화하는 법은
같은 주기에 존재하는 문자 중, 가장 많은 개수의 문자를 유지하는 것이다.

위 논리로 코드를 작성해보자.
우선 M 이하의 숫자는 모두 다 주기가 될 수 있기 때문에,
for문으로 모두 다 탐색한다.

for (l in 1..M) { // M 이하의 모든 숫자가 주기가 될 수 있다.
	...
}

이제 이 for문 내에서 같은 주기에 존재하는 문자들의 수를 세본다.
문자들의 수는 Map에 기록하겠다.

for (l in 1..M) {
	val counter = mutableMapOf<Char, Int>()
    
    ...
}

주기의 시작 인덱스들은 M 미만의 숫자이다.

for (l in 1..M) {
	val counter = mutableMapOf<Char, Int>()
    
    // M = 1 이라면, 주기의 시작지점은 0 인덱스다.
    // M = 2 이라면, 주기의 시작지점은 0, 1 인덱스다.
    // M = 3 이라면, 주기의 시작지점은 0, 1, 2 인덱스다.
    for (start in 0 until l) {
    	...
    }
}

각 주기에서 가장 수가 많은 문자를 구하면 된다.
주기가 1일 때, 2일 때, ... M일 때 최소로 필요한 개수를 구해보고,
그 중 최솟값을 선택하면 된다.

val M = readln().toInt()
val S = readln()
var answer = Int.MAX_VALUE

for (l in 1..M) {
	val counter = mutableMapOf<Char, Int>()
    var tempAnswer = 0
    
    for (start in 0 until l) {
    	var total = 0 // 이 주기에 존재하는 모든 문자의 개수 기록
    	for (j in start until S.length step l) {
        	counter[S[j]] = counter.getOrDefault(S[j], 0) + 1	
            total++
        }
        
        // 가장 많은 개수의 문자를 제외하고 다른 문자를 바꿔주어야 함.
        // 즉, 주기에 포함된 전체 문자 개수에서 가장 많은 문자를 제외한 개수
        tempAnswer += (total - counter.maxOf { it.value })
        counter.clear() // 자꾸 메모리 초과떠서 counter 변수를 재사용했습니다.
    }
    
    // 주기 M에서 문자열을 주기문으로 바꾸는 데에 필요한 최소 개수 갱신
    answer = minOf(answer, tempAnswer)
}

for문을 통해 갱신된 answer 값을 출력하면 정답이다.

...
print(answer)