Algorithm/BOJ
백준 1120 문자열
삼쓰 웅쓰
2020. 6. 8. 14:58
728x90
출처: 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)
감사합니다.