[백준/Swift] 7575: 바이러스 | PS일지

문제

7575번: 바이러스

간단한 문제 요약

백신 프로그램 개발을 위해서는 바이러스 코드를 알아야 한다. 여러 프로그램에서 공통으로 존재하는 부분이 바이러스로 의심된다. 바이러스는 자신의 코드를 반대로 기입할 때도 있다( 공통으로 존재하는 의심 피하려고). 공통으로 나타나는 코드 길이 K인 경우에 바이러스 코드로 추정한다. 추정되는 바이러스 코드를 구하자!

문제 풀이

• 프로그램 1: 10 8 23 93 21 42 52 22 13 1 2 3 4
• 프로그램 2: 1 3 8 9 21 42 52 22 13 41 42
• 프로그램 3: 9 21 42 52 13 22 52 42 12 21

예제에서 주어진 프로그램 코드입니다. 문제에서 주어진 K개수의 특정 문자열(=pattern)이 공통으로 프로그램 1, 2, 3의 코드에 존재한다면 바이러스 코드로 추정되는 부분입니다. 여기서 주의해야 할 점은 바이러스가 심어질 때 바이러스로 추정되는 문자열의 반대로 심어질 수 있다는 점입니다.

한 프로그램에서 특정한 k의 개수 문자열을 바이러스로 추정하고 다른 프로그램의 코드에서 공통으로 있는지 여부를 파악해야 합니다. 프로그램 1을 기준으로 잡았습니다. k개의 문자열씩 뽑아내서 바이러스로 의심했을 때 프로그램2, 3에도 바이러스가 있는지 탐색 후 둘 다 일치하면 YES 만약 프로그램1의 마지막 suffix virus가 프로그램 2, 3에 없다면 NO를 출력했습니다.

바이러스 문자열이 다른 프로그램에도 있는지 비교할 때 KMP 알고리즘을 사용했습니다.(KMP 정리 글)
특정 문자열의 index부터 시작하는 substring을 얻어와야 하는데 그냥 dropFirst와 prefix를 사용했습니다.

느낀점

이번엔 map을 적극 활용하려 했는데, 중간이 일치하는 조건이 있을 때 더 이상 다음 루프 탐색 안하고 map을 빠져나갈 수 있는 키워드가 없어서 .. 아쉽게 많이 사용하지 못했습니다. 프로그램 1의 특정 substring을 바이러스로 가정 후 프로그램 2,3...n까지 차례대로 검사해가는데 2에서 바이러스가 전부 일치하지 않는다면 아예 특정 substring은 바이러스로 추정할 수 없음으로 프로그램1의 다음 suffix를 얻기 위해 함수를 많이 활용했습니다.

substring을 추출할 때 효율적인 코드가 뭐가있는지 보려고 다른 분들의 풀이를 보려 했는데 없었다는..ㅠㅠ

코드

//MARK: - Helpers
func getPartialMatch(pattern: [String]) -> [Int] {
    var pi = Array(repeating: 0, count: pattern.count)
    var begin = 1, matched = 0
    while begin + matched < pattern.count {
        if pattern[begin+matched] == pattern[matched] {
            matched += 1
            pi[begin+matched-1] = matched
        }else {
            if matched == 0 {
                begin += 1
            }else{
                begin += matched - pi[matched-1]
                matched = pi[matched-1]
            }
        }
    }
    return pi
}

func kmpSearch(text: [String], needle: [String]) -> Bool {
    let pi = getPartialMatch(pattern: needle)
    var begin = 0, matched = 0
    while begin <= text.count - needle.count {
        if matched < needle.count && text[begin+matched] == needle[matched] {
            matched += 1
            if matched == needle.count {
                return true
            }
        }else {
            if matched == 0 {
                begin += 1
            }else {
                begin += matched - pi[matched-1]
                matched = pi[matched-1]
            }
        }
    }
    return false
}

func checkVirusInSpecificText(text: [String],
                              needle: [String],
                              idx: Int) -> Bool {
    if kmpSearch(text: text, needle: needle) {
        return true
    }else {
        let reversed = text.reversed().map{String($0)}
        if kmpSearch(text: reversed, needle: needle) {
            return true
        }else {
            return false
        }
    }
}

func checkVirus(_ virus: [String]) -> Bool {
    for i in 1..<texts.count {
        if !checkVirusInSpecificText(text: texts[i],
                                     needle: virus,
                                     idx: i) {
            return false
        }
    }
    return true
}

func solution() {
    for i in 0..<texts[0].count-k + 1 {
        let virus = texts.first!.dropFirst(i).prefix(k).map{String($0)}
        if checkVirus(virus) {
            return print("YES")
        }
    }
    print("NO")
}

//MARK: - Properties
var nk = readLine()!.split{$0==" "}.map{Int(String($0))!}
let n = nk[0], k = nk[1]
var texts = Array(repeating: [String](), count: n)
var res = 0

_=(0..<n).map{
    _=readLine()
    texts[$0] = readLine()!.split{$0==" "}.map{String($0)}
}

solution()