백준 2866 Kotlin 문자열 잘라내기 (이분 탐색)

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

2866번: 문자열 잘라내기

문제

R개의 행과 C개의 열로 이루어진 테이블이 입력으로 주어진다. 이 테이블의 원소는 알파벳 소문자이다.

각 테이블의 열을 위에서 아래로 읽어서 하나의 문자열을 만들 수 있다. 예제 입력에서

dobarz
adatak

이 주어지는 경우 "da", "od", "ba", "at", "ra", "zk"와 같이 6개의 문자열들이 만들어지게 된다.

만약 가장 위의 행을 지워도 테이블의 열을 읽어서 문자열이 중복되지 않는다면, 가장 위의 행을 지워주고, count의 개수를 1 증가시키는, 이 과정을 반복한다. 만약 동일한 문자열이 발견되는 경우, 반복을 멈추고 count의 개수를 출력 후 프로그램을 종료한다.

테이블이 주어질 경우 count의 값을 구해보자.

입력

첫 번째 줄에는 테이블의 행의 개수와 열의 개수인 R과 C가 주어진다. (2 ≤ R, C ≤ 1000)

이후 R줄에 걸쳐서 C개의 알파벳 소문자가 주어진다. 가장 처음에 주어지는 테이블에는 열을 읽어서 문자열을 만들 때, 동일한 문자열이 존재하지 않는 입력만 주어진다.

출력

문제의 설명과 같이 count의 값을 출력한다.

알고리즘 분류

• 자료 구조
• 문자열
• 정렬
• 이분 탐색
• 해시를 사용한 집합과 맵

풀이

1. 이분 탐색

2. 캐싱

3. 해시

4. StringBuilder

 

풀이 키워드는 위 3가지다.

우선 문제 해석에 시간을 많이 썼기 때문에 문제 해석부터 해보자.

예제 3번을 예로 들어보자.

mmmm, rraa,vvrt,iiie,cccj,aaaa

중복되는 문자열이 없다.

만약 두 번째 줄까지 제거한다면?

mm,aa,rt,ie,cj,aa 로 aa가 중복된다.

그럼 문제 조건에 따라 두 번째 줄은 제거할 수 없으므로 현재 count를 출력하고 종료하는데, 현재 count는 첫 번째 줄을 제거하였으니 1이다.

이걸 왜 그렇게 이해 못 했는지... 20분 동안 쳐다본 거 같다.

 

무튼 이제 풀어보자.

이 문제를 나이브하게 완탐한다면 1000개의 줄을 모두 제거해보고, 매번 뒤집어진 문자열을 추출하기 위해 1000*1000으로 총 O(1000*1000*1000)의 시간복잡도를 갖기 때문에 완탐으론 통과할 수 없다.

우리가 찾는 값 X는 0부터 R-1사이에 있는 값이다. (마지막 줄은 제거할 수 없기 때문)

그럼 이 X를 선형 탐색이 아닌 이분 탐색으로 최적화할 수 있다. O(1000) -> O(log1000)

만약 mid 줄을 잘랐을 때 조건에 부합하다면 mid를 늘려보고, 아니라면 mid를 줄이면 된다.

그럼 이제 총 시간 복잡도는 O(log1000 * 1000*1000)이다.

이것만으로 통과할 수 있지만, 우리는 mid줄을 잘랐을 때 조건에 부합한지 확인하려면 열을 위에서 아래로 읽은 문자열을 추출하기 위한 1000*1000의 동작이 필요하다. 

....매번 그럴 필요가 있을까?

행과 열을 뒤집은 배열을 처음에 하나 만들어 놓으면 이를 계속 사용할 수 있다. (캐싱)

그럼 이제 시간 복잡도는 O(logN) + O(1000*1000)이기 때문에 최종적으로 O(1000*1000)이다.

중복되는지 확인하는 방법은 자른 문자열을 set에 저장하고, set에 이미 해당 문자열이 있는지 확인하는 것으로 O(1)이다.

 

StringBuilder를 사용한 이유는 String vs StringBuffer vs StringBuilder의 차이를 서치해보면 알 수 있다.

문자열의 변화가 잦은 경우는 StringBuffer 혹은 StringBuilder를 사용하는데 StringBuffer는 동기화를 지원하는데 현재 싱글 스레드 환경이기 때문에 StringBuilder를 사용하는 것으로 최적화.

 

해당 문제는 위 풀이로만 통과되는 것은 아니다.

입력 크기가 널널해서 다음과 같은 풀이가 모두 통과한다.

1. 이분 탐색 + 캐싱 + 해시 O(1000*1000)

2. 선형 탐색 + 캐싱 + 해시 O(1000* 1000)

3. 이분 탐색 + 해시 O(log1000 * 1000*1000)

 

위 풀이 중에선 1번 풀이가 가장 최적화된 풀이이고 실제로 메모리, 시간에 차이가 꽤 나는 걸 볼 수 있다.

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }
fun getStr() = br.readLine().trim()
fun getInt() = br.readLine().trim().toInt()

lateinit var reversedInput: Array<String>
lateinit var input: Array<String>
fun main() = with(System.out.bufferedWriter()){
    //input
    val (r,c) = getIntList()
    input = Array(r){ getStr() }

    var s = 0
    var e = r-2
    var answer = 0

    //preset
    makeReversedInput(c,input)
    
    //solve
    while(s<=e){
        val mid = (s+e)/2
        if(canRemove(mid)){
            answer = mid+1
            s = mid+1
        }else{
            e = mid-1
        }
    }
    //output
    write("$answer")
    close()
}

fun makeReversedInput(n: Int, input: Array<String>){

    reversedInput = Array(n){ c->
        val sb = StringBuilder()
        for(r in input.indices){
            sb.append(input[r][c])
        }
        sb.toString()
    }
}

fun canRemove(c: Int): Boolean{
    val se = mutableSetOf<String>()
    for(str in reversedInput){
        val truncatedStr = str.substring(c+1)
        if(se.contains(truncatedStr)) return false
        se.add(truncatedStr)
    }
    return true
}