🤔 문제 분석
총 N개의 동전이 H와 T 문자열로 표현된다. (N <= 3000)
이때, 서로 다른 K개의 동전을 매번 뒤집을 수 있다.
즉, H와 T가 어디에 존재하든 순서는 상관없다.
적절하게 뒤집어서 최소 횟수로 N개의 동전이 모두 T가 되도록 만들어야 한다.
✅ 문제 풀이
처음엔 문제 조건을 대충 읽어서 쓸데없이 고민을 많이 했다.
HHHHH에서 K개를 뒤집었다 했을 때,
TTTHH도 가능하고, HTTTH도 가능하고, HHTTT.. 등등이 가능하기 때문이었다.
이런 경우의 수를 하나 하나 따지기엔 시간 초과가 날 것이 뻔하다.
여기서 서로 K개의 동전을 위치에 상관없이 뒤집을 수 있다는 것에 주목해야 한다.
순서에 상관없이 뒤집을 수 있다면 TTTHH 든, HTTTH 든 문자 순서가 다른 것은 중요하지 않게 된다.
H의 개수와 T의 개수가 중요한 것이다.
H의 개수를 0으로 만드는 경우만 찾아내면 된다.
그래서 첫 문자열의 H 개수와 T 개수로 시작하여,
H나 T를 뒤집는 여러 경우를 누적해나가며 답을 찾아보겠다.
중복되는 경우는 방문처리를 통해 제거할 것이다.
우선 입력을 받자.
val (N, K) = readLine().split(" ").map(String::toInt)
val S = readLine()S에 포함된 H와 T의 개수를 추출하자.
val hCnt = S.count { it == 'H' }
val tCnt = N - hCnt방문 처리로는 여러 방법이 있겠지만 필자는 그냥 편하게 MutableSet을 활용하겠다. (오버헤드는 감안하자..)
H와 T의 개수를 저장하는 data class를 선언하여 함께 쓴다.
data class Memo(
val h: Int,
val t: Int,
val cnt: Int = 0,
)
...
val checked = mutableSetOf<Memo>()이제 첫 데이터부터 시작해서 여러 경우를 탐색해나가자.
H의 개수가 0이 되는 경우를 만나면 답을 출력하고 바로 종료할 것이다.
그리고 H를 a개 뒤집고, T를 b개 뒤집는다고 하면,
a+b = K이고, a <= H 개수, b <= T 개수 이다.
이것 또한 조건으로 걸어주고,
H의 개수에 (-a+b)만큼 더해지고, T의 개수에 (-b+a)만큼 더해진 새 경우를 이어서 탐색한다.
방문처리는 앞서 언급한 대로 Set에 기록한다.
...
checked.add(Memo(hCnt, tCnt))
val q = ArrayDeque<Memo>().apply { add(Memo(hCnt, tCnt)) }
while (q.isNotEmpty()) {
val (h, t, cnt) = q.removeFirst()
if (h == 0) {
print(cnt)
return
}
for (a in 0..K) { // h 뒤집기 개수
val b = K - a // k 뒤집기 개수
if (h - a >= 0 && t - b >= 0) {
val diff = (a - b)
if (Memo(h - diff, t + diff) !in checked) {
checked.add(Memo(h - diff, t + diff))
q.add(Memo(h - diff, t + diff, cnt + 1))
}
}
}
}
print(-1)H의 개수가 0이 되는 경우를 만나서 횟수를 출력하거나,
그 경우를 못 만나서 while 문을 벗어난 후 -1을 출력하면 정답이다.
문제 조건을 잘 파악하는 것이 더 중요했던 문제인 것 같다.
