백준 14243 출근 기록 2 Kotlin (많은 조건 분기)

문제 출처 : https://www.acmicpc.net/problem/14243

14243번: 출근 기록 2

문제

스타트링크에는 세명의 직원이 일을 하고 있다. 세 직원의 이름은 강호(A), 준규(B), 수빈(C) 이다.

이 회사의 직원은 특별한 룰을 가지고 있는데, 바로 하루에 한 명만 출근한다는 것이다. 3일간의 출근 기록이 "AAC"라는 것은 처음 이틀은 A가 출근했고, 셋째 날엔 C만 출근했다는 뜻이다.

A는 매일 매일 출근할 수 있다. B는 출근한 다음날은 반드시 쉬어야 한다. C는 출근한 다음날과 다다음날을 반드시 쉬어야 한다. 따라서, 모든 출근 기록이 올바른 것은 아니다. 예를 들어, B는 출근한 다음날 쉬어야 하기 때문에, "BB"는 절대로 나올 수 없는 출근 기록이다. 

출근 기록 S가 주어졌을 때, S의 모든 순열 중에서 올바른 출근 기록인 것 아무거나 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 출근 기록 S가 주어진다. S의 길이는 100,000을 넘지 않는다.

출력

S의 모든 순열 중에서 올바른 출근 기록인 것을 하나만 출력한다. 만약, 올바른 출근 기록이 없는 경우에는 -1을 출력한다.

알고리즘 분류

• 구성적
• 많은 조건 분기

풀이

2022.07.21 - [알고리즘 문제 풀이/백준] - 백준 14238 출근 기록 Kotlin (dp)

이전 14238 문제와 S 길이 조건 빼고 동일한 문제다.

이런 문제가 좋은 게 같은 문제에 조건을 다르게 줌으로써 같은 문제에 대해 여러 접근 방식을 생각할 수 있게 해 준다.

우선 이전 문제에선 dp로 풀었고 사실상 완전 탐색에 가까운 풀이다.

하지만 이 문제에선 답의 길이가 최대 100,000이기 때문에, dp 배열을 만드는 것부터 문제가 생긴다.

a가 3만개, b가 3만개, c가 3만개라고 해보자 그럼 배열은

dp[3만][3만][3만][4][4]로 크기가 너무 커서 만들 수 없다.

그럼 이전과는 다른 풀이가 필요하다는 건데, 문제를 다시 읽어보자.

S의 모든 순열 중에서 올바른 출근 기록인 것을 하나만 출력한다. 

위의 조건을 보면, S의 모든 알파벳을 사용해야 함을 알 수 있다.

따라서 우리는 index = [0 ~ S의 길이]에 들어갈 알파벳들을 정해주어야 하는데, 

이전 dp 풀이에선 해당 자리에 알파벳이 어떤 것이 들어가야 할지 확정 지을 수 없기 때문에 A,B(조건부),C(조건부)를 모두 넣어보고, 이미 같은 형태를 확인해 본 경우는 스킵해 주었다.

 

S의 모든 알파벳을 사용해야 함, 해당 인덱스에 A,B,C를 모두 넣어보는 것은 시간 초과인 것으로 우리는 해당 인덱스에 A,B,C중 어떠한 알파벳을 확정적으로 들어가야만 하는 경우가 있고, 그 조건을 이용해서 탐색을 줄이는 방법이 있을 것이라고 추측할 수 있다.

 

a = A의 개수
b = B의 개수
c = C의 개수

 

즉, 해당 인덱스에 A,B,C를 모두 넣어보는 것이 아닌, A,B,C 중 하나만 골라서 넣고 넘어가는 것이다.

우선 A는 문제에서 주어진 a가 1 이상이라면 모든 칸에 들어갈 수 있으니, B와 C가 해당 인덱스에 들어갈 수 없는 경우 A를 넣어주자.

(실제 풀이에선 꼭 B혹은 C를 넣어야 하는 상황이 아니면 A,B,C중 하나 골라서 넣는다. 아래 내용을 더 읽으면 이해할 수 있다.)

그럼 B와 C를 고르는 것만 남았다.

B가 무조건 해당 인덱스에 들어가야만 하는 경우가 뭘까

S = BBBCA 입력을 예로 들어보자

이 경우 B는 무조건 첫 번째 인덱스에 와야만 

BCBAB

BABCB

형태로 답이 나올 수 있다.

B의 조건은 이전 칸에 B가 오지 않는 경우에만 놓을 수 있었으니 B를 모두(처음 언급한 조건에서 S의 알파벳을 모두 사용해야 한다고 했다.) 사용하기 위해선 첫 번째 온 B를 제외한 나머지 2개의 B는 2개의 A혹은 C가 있어야 한다.

따라서 b-1 = a+c인 경우 무조건 B를 무조건 해당 인덱스에 놓아야만 하는 것이다.

 

C가 무조건 해당 인덱스에 들어가야만 하는 경우는 뭘까

S = CCCAABB 입력을 예로 들면,

CABCBAC

CABCABC

CBACBAC

CBACABC

형태로 답이 나올 수 있다.

C의 조건은 이전 칸, 전전 칸에 C가 오지 않는 경우에만 놓을 수 있었으니 C를 모두 사용하기 위해선 첫 번째 온 C를 제외한 나머지 2개의 C는 4개의 A혹은 B가 있어야 한다.

즉, c-1개를 사용하기 위해선 (a+b)/2가 필요하다.

이는 2*(c-1) = a+b인 경우 무조건 C를 해당 인덱스에 놓아야 한다고 표현할 수 있다.

 

이제 이 조건들을 이용해서 각 인덱스에 들어갈 알파벳을 분기 처리로 정해주면 된다.

1. B 혹은 C가 무조건 들어가야 하는지 검사

2. B 혹은 C가 무조건 들어가야하는 게 아니면 다시 B,C,A중 뭐를 넣을지 검사

3. 다시 B,C,A중에 뭐 넣을지 검사할 때 B,C,A의 순서는 상관없다. A,B,C 모두 넣을 수 없다면 S길이의 답을 만들 수 없으므로 -1을 출력하고 종료한다.

 

코드

val br = System.`in`.bufferedReader()
fun main() = with(System.out.bufferedWriter()) {
    //input
    val input = br.readLine()
    var a = 0
    var b = 0
    var c = 0
    val size = input.length
    var answer = CharArray(size)
    for (ch in input) {
        when (ch) {
            'A' -> a++
            'B' -> b++
            else -> c++
        }
    }
    //solve
    var prev = 0
    var pprev = 0
    for (i in 0 until size) {
        if (b - 1 == a + c && b > 0 && prev != 2) {
            pprev = prev.also { prev = 2 }
            answer[i] = 'B'
            b--
        } else if (2 * (c - 1) == a + b && c > 0 && prev != 3 && pprev != 3) {
            pprev = prev.also { prev = 3 }
            answer[i] = 'C'
            c--
        } else {
            if (b > 0 && prev != 2) {
                pprev = prev.also { prev = 2 }
                answer[i] = 'B'
                b--
            } else if (c > 0 && prev != 3 && pprev != 3) {
                pprev = prev.also { prev = 3 }
                answer[i] = 'C'
                c--
            } else if (a > 0) {
                pprev = prev.also { prev = 1 }
                answer[i] = 'A'
                a--
            } else {
                write("-1")
                close()
                return
            }
        }
    }
    //output
    for (i in 0 until size) {
        write("${answer[i]}")
    }
    close()
}