[백준] Swift - 2179번: 비슷한 단어

👆문제풀러 가기👆

문제

N개의 영단어들이 주어졌을 때, 가장 비슷한 두 단어를 구해내는 프로그램을 작성하시오.

두 단어의 비슷한 정도는 두 단어의 접두사의 길이로 측정한다. 접두사란 두 단어의 앞부분에서 공통적으로 나타나는 부분문자열을 말한다. 즉, 두 단어의 앞에서부터 M개의 글자들이 같으면서 M이 최대인 경우를 구하는 것이다. "AHEHHEH", "AHAHEH"의 접두사는 "AH"가 되고, "AB", "CD"의 접두사는 ""(길이가 0)이 된다.

접두사의 길이가 최대인 경우가 여러 개일 때에는 입력되는 순서대로 제일 앞쪽에 있는 단어를 답으로 한다. 즉, 답으로 S라는 문자열과 T라는 문자열을 출력한다고 했을 때, 우선 S가 입력되는 순서대로 제일 앞쪽에 있는 단어인 경우를 출력하고, 그런 경우도 여러 개 있을 때에는 그 중에서 T가 입력되는 순서대로 제일 앞쪽에 있는 단어인 경우를 출력한다.

입력

첫째 줄에 N(2 ≤ N ≤ 20,000)이 주어진다. 다음 N개의 줄에 알파벳 소문자로만 이루어진 길이 100자 이하의 서로 다른 영단어가 주어진다.

출력

첫째 줄에 S를, 둘째 줄에 T를 출력한다. 단, 이 두 단어는 서로 달라야 한다. 즉, 가장 비슷한 두 단어를 구할 때 같은 단어는 제외하는 것이다.

알고리즘 분류

• 자료 구조
• 문자열
• 정렬
• 해시를 사용한 집합과 맵

---

풀이 목표

1. 전체 입력 문자열에 대해, 공통된 가장 긴 접두사를 가진 두 단어(S, T)를 찾아라.
2. 공통된 접두사를 가진 문자열 중, 가장 먼저 입력된 문자열이 S, 다음으로 입력된 문자열은 T이다.
3. S와 T는 같은 문자열이면 안 된다. ( 입력 조건으로 서로 다른 영단어가 주어져서 문제는 없음. )
4. 접두사의 길이가 같은 문자열(T)이 여러 개라면, 먼저 입력된 문자열을 출력해라.

 

풀이

struct Word {
    let word: String
    var index: Int
}

private func solution() {
    let n = Int(readLine()!)! // 입력 단어 갯수
    let words = savedWords(n) // n개의 word와 index 저장
    var lengths = Array(repeating: 0, count: n+1) // 원래 단어들이 입력된 순으로, count값 저장하기 위한 배열

    let sortedWords = words.sorted(by: {$0.word < $1.word}) // 비슷한 단어끼리 모아보기 위해 오름차순 정렬
    var maxCount = 0

    for i in 0..<n-1 {
        // 앞단어와 뒷단어의 같은 접두사 확인
        let left = sortedWords[i].word.map { String($0) }
        let right = sortedWords[i+1].word.map { String($0) }
        let count = countPrefixString(leftString: left, rightString: right) // 비교 문자열 간 같은 접두어 길이 재기

        maxCount = max(maxCount, count) // 같은 접두어를 가진 문자열 중, 가장 긴 접두어 확인
        lengths[sortedWords[i].index] = max(lengths[sortedWords[i].index], count)    // 입력 순으로 정렬된 배열에 왼쪽 단어의 가장 긴 접두어 길이 반영
        lengths[sortedWords[i+1].index] = max(lengths[sortedWords[i+1].index], count)// 입력 순으로 정렬된 배열에 오른쪽 단어의 가장 긴 접두어 길이 반영
    }

    var result = [String]()
    var firstIndex = -1

    for i in 0..<n where lengths[i] == maxCount { // 가장 긴 공통 접두어를 가진 배열만 봤을 때,
        result.append(words[i].word)

        if firstIndex == -1 {                     // 첫번째로 가장 긴 length 단어라면
            print(words[i].word)                  // 출력해주고
            firstIndex = words[i].index           // 해당 단어 (S)의 위치(index)를 저장해준다.
        }
    }

    // 입력된 순의 단어 중, 앞의 단어와 가장 먼저 일치하는 단어를 출력하기
    for i in 0..<result.count where result[i] != words[firstIndex].word {           // S와 T는 다른 단어여야 한다.
        if result[i].prefix(maxCount) == words[firstIndex].word.prefix(maxCount) {  // 가장 먼저 입력한 T 문자열 찾기
            print(result[i])
            break
        }
    }
}

func savedWords(_ n: Int) -> [Word] {
    var words = [Word]()

    for i in 0..<n { // 단어를 입력한 순서대로 저장
        guard let word = readLine() else { continue }
        words.append(Word(word: word, index: i))
    }
    return words
}

func countPrefixString(leftString: [String], rightString: [String]) -> Int {
    var count = 0

    for j in 0..<leftString.count where rightString.count > j {
        if leftString[j] != rightString[j] { break }  // 앞 단어와 뒷 단어의 글자가 다르면 종료
        count += 1                        // 앞 단어와 뒷 단어의 글자가 같으면 count + 1
    }
    return count
}

 

 

 

처음 이 문제를 봤을 때, 예제를 보고 '첫 단어와 같은 접두사를 가진 문자열 중, 가장 긴 문자열을 찾으면 되는 거구나'라고 착각했다. 그렇게 해도 예제는 잘 출력되었기 때문이다.

하지만 문제를 다시 읽어보면, 가장 긴 접두사의 길이 m이라고 할 뿐, 첫 단어와 같아야 한다는 말은 등장하지 않는다.

언제나 문제에 답이 있다..