백준 [20437] kotlin

https://www.acmicpc.net/problem/20437

20437번: 문자열 게임 2

[풀이]

투 포인터로 풀었다.

풀이 과정은 다음과 같다.

 

<과정1>

입력 받은 문자열의 각 자리별 인덱스 위치를 저장해두는 배열을 만든다.

예를 들어 abbc라는 문자열을 받는다면,

[[0],[1,2],[3]]과 같이 인덱스를 저장하는 배열을 만든다.

 

문자열을 W라고 표현하고 저장하는 배열을 abcIndex라고 한다면 아래와 같다.

var W = br.readLine().toString()

var abcIndex = Array(26,{ arrayListOf<Int>() })
repeat(W.length)
{
    i ->
    abcIndex[W[i] - 'a'].add(i)
}

 

<과정2 - 투 포인터>

알파벳은 26개이므로 26번 아래의 과정을 반복한다.

이 때 각 알파벳 배열에 인덱스가 K개 보다 적다면 굳이 할 필요가 없으므로 스킵한다.

 

투 포인터로

left = 0, right = K-1로 초기값을 설정을 하고

right가 해당 알파벳의 사이즈보다 작을 경우에, 각 값을 최신화를 해주면 끝이다.

var answer1 = Int.MAX_VALUE
var answer2 = Int.MIN_VALUE
for(i in 0 until 26)
{
    if(abcIndex[i].size < K) continue
    var left = 0
    var right = K - 1
    while(right < abcIndex[i].size)
    {
        answer1 = min(answer1, abcIndex[i][right] - abcIndex[i][left])
        answer2 = max(answer2, abcIndex[i][right++] - abcIndex[i][left++])
    }
}

 

[전체 코드]

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import kotlin.math.max
import kotlin.math.min

fun main()
{
    var br = BufferedReader(InputStreamReader(System.`in`))
    var bw = BufferedWriter(OutputStreamWriter(System.`out`))

    var N = br.readLine().toInt()
    repeat(N)
    {
        var W = br.readLine().toString()
        var K = br.readLine().toInt()

        var abcIndex = Array(26,{ arrayListOf<Int>() })
        repeat(W.length)
        {
            i ->
            abcIndex[W[i] - 'a'].add(i)
        }
        var answer1 = Int.MAX_VALUE
        var answer2 = Int.MIN_VALUE
        for(i in 0 until 26)
        {
            if(abcIndex[i].size < K) continue
            var left = 0
            var right = K - 1
            while(right < abcIndex[i].size)
            {
                answer1 = min(answer1, abcIndex[i][right] - abcIndex[i][left])
                answer2 = max(answer2, abcIndex[i][right++] - abcIndex[i][left++])
            }
        }
        if(answer1 == Int.MAX_VALUE) bw.write("-1\n")
        else{
            answer1++
            answer2++
            bw.write("$answer1 $answer2\n")
        }
    }

    bw.flush()
    bw.close()
}