반응형
백준 1120번 문제입니다. (solved.ac) 기준 실버 4 문제입니다.
https://www.acmicpc.net/problem/1120
문제
문제 접근
문자열 a, b를 입력받고 두 문자열의 인덱스간 차이의 최소를 구하는 문제입니다.
길이가 같을 경우에는 단순 문자열들의 인덱스를 비교해서 차이를 구하면 되지만 문자열의 길이가 다를 경우에는 두 문자열의 길이를 맞춰주어야합니다.(단, 길이가 다를 경우 a의 길이가 무조건 b보다 작음)
길이가 다를 경우 길이를 맞추기 위하여 짧은 문자열의 앞, 뒤 중 자유롭게 문자를 집어넣을 수 있습니다. 문자열의 차이를 최소로 만들어야 하는 문제이므로, 절대 문자인 '*'를 추가하도록 하였습니다. 절대 문자는 무조건 대응하는 문자와 같다고 판단할 문자입니다. - ex) * == a, * == b
a와 b의 길이차를 구하고 해당 차이만큼 '*'를 앞뒤로 추가해 줄 수 있습니다. 문자열 a, b의 크기가 50이하 이므로 완전탐색을 통하여 모든 경우의 수를 구하여도 시간이 충분하다고 판단하여 완전탐색으로 구하였습니다.
완전탐색으로 *를 추가한 모든 newA(b와 길이가 같게된 a)를 구하여 그 중 차이가 최소가 될 수 있는 값을 구하도록 하였습니다.
예를 들어 a = 123, b = 412356일 경우, newA는 123***, *123**, **123*, ***123 이 될 수 있습니다.
정답 코드
fun main() {
val (a, b) = readln().split(" ")
var answer = 100
val lengthA = a.length
val lengthB = b.length
// 길이가 같을 때
if (lengthA == lengthB) {
answer = difCnt(a, b)
}
// 길이가 다를 때
else {
var toAddCnt = lengthB - lengthA
// 부족한 문자의 개수만큼 *을 끼워넣는 과정
for (index in 0..toAddCnt) {
var newA = ""
for (addFront in 0 until index) {
newA += "*"
}
newA += a
for (addBack in 0 until toAddCnt - index) {
newA += "*"
}
val difCnt = difCnt(newA, b)
if (difCnt < answer) answer = difCnt
}
}
println(answer)
}
// 두 문자열의 차이를 계산하는 과정
fun difCnt(a: String, b: String): Int {
var difCnt = 0
for (index in 0 until a.length) {
if (a[index] != b[index]
&& a[index] != '*'
) difCnt++
}
return difCnt
}
반응형
'알고리즘 문제풀이[Algorithm]' 카테고리의 다른 글
[백준] 싱기한 네자리 숫자[Kotlin - 코틀린] (0) | 2022.07.05 |
---|---|
[백준] 10211번 Maximum Subarray(브루트포스 - 완전탐색)[Kotlin - 코틀린] (0) | 2022.07.01 |
[백준] 1145번 적어도 대부분의 배수(브루트포스 - 완전탐색)[Kotlin - 코틀린] (0) | 2022.07.01 |
[백준] 18312 시각(브루트포스 - 완전탐색)[Kotlin - 코틀린] (0) | 2022.07.01 |
[백준] 1747 소수&팰린드롬(브루트포스 - 완전탐색)[Kotlin - 코틀린] (0) | 2022.06.30 |
최근댓글