[백준(BOJ)] 17218 비밀번호 만들기 - 스위프트(Swift)

[Gold V] 비밀번호 만들기 - 17218

문제 링크

성능 요약

메모리: 69100 KB, 시간: 8 ms

분류

다이나믹 프로그래밍, 문자열

문제 설명

최근 들어 개인정보 유출에 대한 뉴스를 많이 본 수형이는 한 사이트의 비밀번호가 유출 되더라도 다른 사이트에서 똑같은 비밀번호로 접속할 수 없도록 사이트마다 비밀번호를 다르게 설정하기로 다짐했다. 많이 고민한 결과 수형이는 눈을 감고 키보드를 막 쳐서 나온 두 문자열에서 공통으로 존재하는 가장 긴 부분 문자열을 비밀번호로 하기로 하였다. 수형이가 눈을 감고 만든 두 문자열이 주어졌을 때 비밀번호를 만드는 프로그램을 만들어보자.

입력

첫째 줄과 둘째 줄에 수형이가 눈을 감고 만든 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 길이는 최대 40자이다. 빈 문자열은 주어지지 않는다. 가장 긴 부분 문자열은 반드시 하나만 존재한다.

출력

첫 번째 줄에 입력으로 주어진 두 문자열로 만든 비밀번호를 출력한다.

 

풀이

i)

해당 문제는 LCS를 알아야 풀 수 있는 문제였어서 공부를 한 뒤에 이를 적용해보았습니다.

/***
LCS 문제
*/

let first = readLine()!
let second = readLine()!

var firstArray = [Character]()
var secondArray = [Character]()
var ans = ""

for char in first {
    firstArray.append(char)
}

for char in second {
    secondArray.append(char)
}

var dp = Array(repeating: Array(repeating: 0, count: secondArray.count + 1), count: firstArray.count + 1)

//LCS
for i in 1...firstArray.count {
    for j in 1...secondArray.count {
        if firstArray[i - 1] == secondArray[j - 1] {
            dp[i][j] = dp[i-1][j-1] + 1
        } else {
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        }
    }
}

var (i, j) = (firstArray.count, secondArray.count)

//역순으로 문자열 찾기
while i > 0 && j > 0 {
    if firstArray[i - 1] == secondArray[j - 1] {    //같은 문자라면
        ans = String(firstArray[i - 1]) + ans
        i -= 1
        j -= 1
    } else if dp[i][j] == dp[i-1][j] {  //왼쪽이 같은 문자라면
        i -= 1
    } else {    //윗쪽이 같은 문자라면
        j -= 1
    }
}

print(ans)

 

LCS에 대해 참고한 블로그 주소와 정리해둔 사이트를 추가해놓겠습니다.

https://tae-rogrammer.tistory.com/6

[알고리즘] LCS

 

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence