[백준 : 2866] 문자열 잘라내기(Kotlin)

👇🏻 문제 확인하기
백준:2866 - 문자열 잘라내기

문제

입출력

문제풀이

우선 문제를 이해하는데 시간이 많이 걸렸다.
행을 지우기 전이랑 후를 비교해서 중복값을 찾아내는건 줄 알고 헷갈렸었는데,
행을 지울때 마다 그 때의 세로문자열들 중에 중복값이 있느냐 물어보는 문제.

1️⃣ 첫번째 시도

1. 배열을 list로 바꿔서 첫번째 인덱스(행)을 지워간다.
   2. 세로 문자열을 만들어준다.
      3. 만든 문자열들을 set에 저장시킨다.
   3. set의 size가 열의 크기와 같다면 list의 첫번째 행을 지워준다. cnt++
   4. 같지 않다면 반복문을 종료한다.

fun main(){
    val (r,c) = readln().split(" ").map{it.toInt()}
    val strings = Array(r){readln()}.toMutableList()
    var count = 0

    while (strings.size != 0){
        val tempSet = mutableSetOf<String>()
        for (i in 0 until strings[0].length){
            val temp = strings.map{it[i]}.joinToString("")
            tempSet.add(temp)
        }
        if(tempSet.size == c) {
            strings.removeAt(0)
            count++
        }else break
    }
    println(count-1)
}

시간초과.... 가슴이 답답해진다,,,,..
코드를 보면 완전탐색도 아니고 이걸 이분탐색으로 바꾸기 위해서는 새로운 배열을 하나 더 만들어서 만든 문자열을 저장시켜주어야 하고
거기에서 이분탐색으로 모든 값들을 만날 수 없도록,,,, 해야 하는데 그것이 시간이 줄어들까 라는 의문이 들었다.

곱씹으면서 찾은 단서는!! 새로운 배열을 하나 더 만들어서 만든 문자열을 저장시켜주어야 하고 이부분!!

2️⃣ 두번째 시도 (성공)

1. 입력받은 값들을 처음부터 세로로 잘라서 새로운 배열을 생성한다.
2. 행의 갯수( 문자열의 최대 길이) 만큼 반복한다.
   3. 배열을 돌면서 문자열을 앞에서부터 잘라준다. 예) abcd -> bcd -> cd -> d
      4. set에 잘라준 문자열들을 저장시킨다.
   4. set의 크기가 열의 갯수와 같다면 count++ 같지 않다면 반복문 종료

fun main(){
    val (r,c) = readln().split(" ").map{it.toInt()}
    val strings = MutableList(r){readln()}
    var count = 0
    val setList = mutableListOf<String>()

    for (i in 0 until strings[0].length){
        val temp = strings.map{it[i]}.joinToString("")
        setList.add(temp)
    }

    for (i in 1 ..r){
        val tempSet = mutableSetOf<String>()
        setList.forEach {
            val temp = it.substring(i-1,r)
            tempSet.add(temp)
        }
        if(tempSet.size == c) {count++} else break
    }
    println(count-1)
}

한줄평

반복문을 최소화하는게 시간복잡도가 작아진다고 생각해서 반복문을 최대한 안쓰고 코틀린 함수들을 이용해서 필요한 값들을 뽑아올려고 했는데 아니었다..
알고리즘 능력을 안키우고 kotlin 언어 능력을 키워서 문제를 풀려고 하니까 난관에 부딪히고 답답한 점들이 많아지는 것 같다. 코딩력과 알고력을 모두 갖춘 사람이 되장~ 코딩력과 알고력... 언제였지..? 코테에서 본 단어다.