백준 1120 문자열

출처: www.acmicpc.net/problem/1120

분류: Greedy

---

접근방식

앞뒤로 아무 문자나 붙여서 길이를 같이 만들 때 차이가 가장 적은 경우를 찾는 문제입니다.

앞뒤로 아무 문자나 붙일 수 있으므로 현재 문자열과 비교할 문자열만 가지고 비교하면 나머지는 길이를 맞춰버릴 수 있습니다.

예제 케이스처럼 adaabc aababbc 를 보면, 

0번 인덱스부터 adaabc와 adaabc의 길이만큼인 aababb 와 비교해보면 다른 개수는 3개입니다.
나머지는 adaabc 뒤에 c를 붙여버리면 길이를 똑같이 만들 수 있겠죠

1번 인덱스부터 adaabc와 adaabc의 길이만큼인 ababbc 와 비교해보면 다른 개수는 2개입니다. 
마찬가지로 앞에 a를 붙여서 길이를 똑같이 만들 수 있겠죠

 

해결방법

스위프트는 문자열 다루기가 매우 귀찮습니다. 따라서 문자열도 일반 배열처럼 사용할 수 있도록 extension을 사용했습니다.

나머지 부분은 그냥 코드를 보시면 쉽게 이해가 가실거에요.

extension String {
    subscript(i: Int) -> Character {
        var offset = i
        while offset < 0 { offset += count }
        let index = self.index(startIndex, offsetBy: offset)
        return self[index]
    }
}

let inputs = readLine()!.split(separator: " ").map{ String($0)}
let str1 = inputs[0]
let str2 = inputs[1]

var result = Int.max
for k in 0...str2.count-str1.count {
    var diff = 0
    for i in 0..<str1.count {
        
        if str1[i] != str2[i+k] { diff += 1 }
    }
    result = min(result, diff)
}

print(result)

 

감사합니다.