[백준 20542] - 받아쓰기(Kotlin)[골드3]

문제

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

20542번: 받아쓰기

 

문제 풀이

우선 문제가 굉장히 길고 비슷한 말이 많아서 문제에 대한 정확한 파악이 필요하다.

입력은 크게 답변과 정답이다. 이 두 가지를 구분하는 것이 굉장히 중요하다.

우리는 답변을 수정,삭제,변환을 통해서 정답과 같은 문자열을 만들어야 한다.

그리고 날려쓰기라는 정보가 등장한다. i를 날려썼다면 i, j, l  v를 나르였으면 v, w로 인식된다.

즉 우리가 적은 답변에서 i는 i,j,l로 인식되고, v는 v, w로 인식된다는 얘기이다.

해당 정보는 정답에서는 적용되지 않는다.

이제 문제에 대한 파악이 끝나고 접근 방법에 대해서 생각해보자.

나는 LCS와 비슷한 점이 많아서, LCS로 접근을 했다.

LCS와 다른 점은 LCS는 가장 길게 이어지는 부분을 구하는 것이고, 해당 문제는 얼마나 적게 수정, 변환, 삭제를 해야 하는가이다.

 

알고리즘의 흐름은 다음과 같다.

1. 배열을 선언 : 크기는 (n+1, m+1)
2. 배열 탐색 : 답변, 정답 
   • 답변의 글자와 정답의 글자가 같다면 비용은 0원이므로, dp [i-1][j-1]을 그대로 가져온다.
     • 만약 LCS라면 dp [i-1][j-1]+1을 가져왔을 것이다.
   • 답변의 글자와 정답의 글자가 휘날려 쓰기에 포함된다면 비용은 0원이므로, dp [i-1][j-1]을 그대로 가져온다.
   • 답변의 글자와 정답의 글자가 다르다면 dp [i][j-1], dp [i-1][j], dp [i-1][j-1] 중에서 가장 작은 값에 +1을 하고 가져온다.
3. dp [n][m]에 최종적으로 답변->정답으로 바꾸는 최소 비용이 들어있을 것이다.

 

 

전체 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.min

class `20542` {
    private val br = BufferedReader(InputStreamReader(System.`in`))
    private var n = 0
    private var m = 0
    private var answer="" //답변
    private var result="" //정답
    private lateinit var dp : Array<IntArray>
    private var alphaSet : HashSet<Pair<Char,Char>> = hashSetOf()
    init{
        setAlpha()
        input()
        dp()
    }
    private fun setAlpha(){ //휘날려쓸 수 있는 알파벳
        alphaSet.add(Pair('i','i'))
        alphaSet.add(Pair('i','j'))
        alphaSet.add(Pair('i','l'))
        alphaSet.add(Pair('v','w'))
        alphaSet.add(Pair('v','v'))
    }
    private fun input(){
        br.readLine().split(" ").forEachIndexed { index, s ->
            when(index){
                0-> n = s.toInt()
                1-> m=s.toInt()
            }
        }
        answer=br.readLine()
        result=br.readLine()
        dp = Array(n+1){IntArray(m+1,{0})}
    }
    private fun dp(){

        for(i in 1 until n+1)
            dp[i][0]=i
        for(i in 1 until m+1)
            dp[0][i]=i


        for(i in 1 until dp.size){
            for(j in 1  until dp[i].size){
                if(answer[i-1]==result[j-1]){ //두 글자가 같으면 비용이 0원
                    dp[i][j] = dp[i-1][j-1]
                }
                else if(alphaSet.contains(Pair(answer[i-1],result[j-1]))){ //휘날려 쓸 수 있는 경우비용이 0원
                    dp[i][j] = dp[i-1][j-1]
                }
                else { //아닌 경우
                    dp[i][j] = min(dp[i][j-1]+1,min(dp[i-1][j]+1,dp[i-1][j-1]+1))
                }
            }
        }
        print(dp[n][m])
    }
}


fun main(){
    val solution = `20542`()
}