[백준/BaekJoon] 문자열 (kotlin/코틀린)

1. 문제 설명

 

문제

길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다.

두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다.

1. A의 앞에 아무 알파벳이나 추가한다.
2. A의 뒤에 아무 알파벳이나 추가한다.

이때, A와 B의 길이가 같으면서, A와 B의 차이를 최소로 하는 프로그램을 작성하시오.

입력

첫째 줄에 A와 B가 주어진다. A와 B의 길이는 최대 50이고, A의 길이는 B의 길이보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.

출력

A와 B의 길이가 같으면서, A와 B의 차이를 최소가 되도록 했을 때, 그 차이를 출력하시오.

 

 

2. 알고리즘 설명

 

 

문제의 예제입력4 를 참고로 예시를 들어보겠습니다.

 

abc , topabcoder 를 가지고 설명하겠습니다.

 

abc 앞,뒤에 아무 알파벳을 붙여서 두단어의 길이가 같을 때 알파벳의 차이를 최소로 하게 해야합니다.

 

그말인 즉슨, abc의 아무 알파벳을 붙일 때 무조건 뒤의 topabcoder 와 같은 알파벳을 붙여야 차이가 최소로 나옵니다.

 

그렇다면 아무 알파벳은 무조건 같은 알파벳이라는 전제하에 abc의 위치를 topabcoder 의 어느 위치에 두느냐가 최소가 되는 중요한 포인트가 됩니다.

 

topabcoder   topabcoder

abcxxxxxxx   xxxabcxxxx

 

위 두가지 경우를 봤을 때 왼쪽은 차이가 3이고 오른쪽은 0으로 오른쪽이 최소가 됩니다.

 

그렇다면 이제 방법이 나왔습니다.

 

     topabcoder   topabcoder  topabcoder  topabcoder

→ abc                  abc                  abc                 abc

 

위의 topabcoder 를 기준으로 abc 를 비교하면서 한칸씩 옮기면서 차이가 최소가 되는 경우를 찾습니다.

 

해당 루프는 topabcoder 의 길이 - abc 의 길이 만큼 돌면 됩니다.

 

코드 확인하겠습니다.

 

import java.io.BufferedReader
import java.io.InputStreamReader
import java.lang.Integer.min
import java.util.*

var totalCount = Integer.MAX_VALUE

fun main(args : Array<String>) {
    val bf = BufferedReader(InputStreamReader(System.`in`))
    val st = StringTokenizer(bf.readLine())
    val a = st.nextToken()
    val b = st.nextToken()

    if(a.length == b.length) {
        var count = 0
        for(i in a.indices) {
            if(a[i] != b[i]) count++
        }
        totalCount = min(totalCount,count)
    } else {
        for(i in 0..b.length - a.length) {
            var count = 0
            for(j in a.indices) {
                if(a[j] != b[j+i]) count++
            }
            totalCount = min(totalCount,count)
        }
    }
    print(totalCount)
}

 

물론 길이가 똑같다면 바로 비교해서 차이값을 리턴하면 됩니다.

b[j+i] 로 a의 문자를 b의 다음칸부터 비교하게끔 합니다.