[Swift] 백준 비슷한 단어 2179

https://www.acmicpc.net/problem/2179

 

 

1. 문제이해

• N개의 영단어들이 주어질 때, 가장 비슷한 두 단어를 출력하기
• 비슷한 정도는 두 단어의 접두사의 길이로 따진다.
• 접두사란 두 단어의 앞부분에서 공통적으로 나타나는 부분문자열을 말한다.
• "AHEHHEH", "AHAHEH"의 접두사는 "AH"가 되고, "AB", "CD"의 접두사는 ""(길이가 0)이 된다.
• 접두사의 길이가 최대인 경우의 두 단어를 출력하라
• 접두사의 길이가 최대일 경우 단어가 입력된 순서대로 2개(S, T) 출력
• 접두사의 길이가 동일한 경우가 있을 경우 그 중에서 단어 입력 순서가 제일 빠른 단어의 접두사를 기준으로 하여 입력 순서대로 2개의 단어를 출력

2. 접근방법

• N의 최대는 20000, 단어들을 2중 반복문으로 접두사의 길이를 계산할 경우 시간 초과
• 입력 받은 단어들을 문자열 오름차순 정렬 → 최악의 경우 N의 최대 20000 * 단어 최대 길이 100

3. 코드

import Foundation

struct Word{
    let str: [String] // 단어를 배열로 저장
    let index: Int // 단어의 입력 순서
}

func solution(){
    let N = Int(readLine()!)!
    var words = [Word]()
    
    var M = 0 // 접두사의 최대 길이
    var strM = "" // 최대 길이를 가지는 접두사
    
    var S: Word?
    var T: Word?
    
    // 입력 부분
    for i in 0..<N{
        let word = Word(str: readLine()!.map{String($0)}, index: i)
        words.append(word)
    }
    
    // 단어들을 오름차순으로 정렬
    words.sort(by: { $0.str.joined() < $1.str.joined() })
    
    for i in 0..<N-1{
        compare(a: words[i], b: words[i+1])
    }
        
    func compare(a: Word, b: Word) {
        // 첫 글자부터 동일한 인덱스에 같은 글자가 몇번 있는지 체크
        var equalCount = 0
        for i in 0..<min(a.str.count, b.str.count){
            if a.str[i] == b.str[i]{
                equalCount += 1
            }else{
                if equalCount > 0, M <= equalCount{ // 공통 접두사의 길이가 0보다 크고 최대 접두사의 길이와 같거나 클 때
                    updateM(a: a, b: b, equalStr: a.str[0..<equalCount].joined()) // 비교했던 두 단어와 공통 접두사를 인자로 하여...
                }
                return
            }
        }
        if equalCount > 0, M <= equalCount{ updateM(a: a, b: b, equalStr: a.str[0..<equalCount].joined())}
    }
    
    func updateM(a: Word, b: Word, equalStr: String){
        if M < equalStr.count{ // 접두사의 최대 길이보다 클 때
            if a.index < b.index{ // S와 T에 단어 입력 순으로 저장
                S = a
                T = b
            }else{
                S = b
                T = a
            }
            strM = equalStr
        }else{ // 접두사의 최대 길이와 같을 때
            // S, T와 현재 비교하고 있는 두 단어를 입력 순으로 정렬
            let temp = [S!, T!, a, b].sorted(by: {$0.index < $1.index})
            strM = temp[0].str[0..<M].joined() // 최대 길이의 접두사 저장
        }
        M = equalStr.count // 최대 접두사의 길이 업데이트
    }
    
    var printCount = 0
    for word in words.sorted(by: {$0.index < $1.index}) { // 단어 저장 배열을 다시 입력 순서대로 정렬
        if M > word.str.count{ continue }
        if word.str[0..<M].joined() == strM{ // 최대 길이의 접두사가 포함 되어 있다면
            print(word.str.joined()) // 출력
            printCount += 1
        }
        if printCount == 2 { return } // 2번만 출력
    }
}
solution()