[백준/Swift] 1305: 광고 문제 해석 | PS일지 :]

문제

간단한 문제 요약

전광판에는 같은 내용의 문구가 무한히 반복되어 나온다. 전광판의 크기 L은 전광판에서 한번에 보이는 최대 문자수를 나타낸다. 전광판의 크기가 L이라면 한번에 L개의 문자를 표시 할 수 있다.

 

광고업자는 길이가 N인 광고문구를 전광판에 붙이려 한다. 근데 돈을 많이 냈기에 N을 무수히 반복해서 전광판의 빈 곳 없이 L만큼의 길이로 채우려고 한다.

문제 풀이, 했갈렸던 점

예를들어

L: 6

N: 4

내가 광고하기 싶은 광고 문구: LOVE

 

전광판에는 6개의 글자를 넣을 수 있고 문제에서 광고업자는 광고 문구를 무수히 반복해서 L만큼 채워 넣으려고 합니다.

그렇다면 LOVELO 가 광고 문구의 첫 글자로 채워집니다.

 

문제를 정말 1시간?2시간 봤는데도 문제 이해하기 어려웠어요 ㅠㅠㅠ.. 전광판을 쳐다봤는데? 그때 쓰여있는 문자가 '입력'으로 주어졌을 때 가능한 광고 길이중 가장 짧은 것을 출력해라? (엥? 전광판에서 있는 문구는 결국 특정한 input에도 L 길이 만큼 반복(확장)되서 L개 한개인데.. 짧은거를 출력하라니)

 

LOVELO 에서 1초후 OVELOV   -(1초후)>  VELOVE  -(1초후)>   ELOVEL   -(1초후)>     LOVELO (엥?! 결국엔 6글자인데? 이게 아닌가?)

 

계속해서 생각을 했습니다.

 

 

 

어느 순간 전광판을 바라봤을 때!!! 전광판의 길이는 6입니다. 그리고 LOVELO라는 문구를 봤습니다. 그럼 이 문구를 본 순간 생각할 수 있습니다. "광고주는 몇 글자의 광고문구를 등록 했길래 저 전광판에서 글자를 볼 수 있을까?", "광고주는 광고문구를 1~6개의 문자를 전광판에 등록할 수 있는데 어떻게 LOVELO를 만들 수 있을까?"

 

그리고 문제에선 될 수 있는 광고 문구의 길이 중 가장 짧은 광고 문구 길이의 길이를 구하는게 이 문제의 핵심입니다.

 

 

"광고주는 어떤 광고문구를 등록 했을까? LOVELO 6글자를 전부 등록했을까?"

 

"단 한 글자만 걸었나? 멋있게 이니셜?"

L이라 생각한다면? 전광판에는 LLLLLL가 보일 것입니다.(왜냐? 광고문구길이 N = 1이고 전광판 길이 L: 6이기에 전광판 길이만큼 광고문구가 반복되서 채워지기 때문입니다.) 그렇다는 것은 어느 순간 전광판을 봤을 때 본 LOVELO라는 문구와 다릅니다.

 

LO라 생각한다면? 전광판에는 LOLOLO가 보일 것입니다. 역시 LOVELO랑 다릅니다.

LOV라 생각한다면? 전광판에는 LOVLOV가 보일 것입니다. 역시 LOVELO랑 다릅니다.

LOVE라 생각한다면? 전광판에는 LOVELO가 보일 것입니다. 어느 순간 전광판 쳐다봤을 때의 광고문구인 LOVELO와 같습니다.

LOVEL라 생각한다면? 전광판에는 LOVELL가 보일 것입니다. 전광판 광고 문구 LOVELO와 다릅니다.

LOVELO라 생각한다면? 전광판에는 LOVELO가 보일 것입니다. 전광판 광고 문구와 같습니다.

 

어느 순간 전광판을 쳐다봤을 때 광고 문구는 LOVELO이고 LOVELO를 만들 수 있는 광고 문구는 LOVE, LOVELO 두 개가 있습니다. 이 중에서 가장 짧은 길이는 LOVE입니다.

 

이번엔 전광판의 길이 L: 5이고. 어느 순간 전광판을 쳐다봤을 땐

babba 라는 문구를 봤다고 가정하겠습니다.

babba..?? 광고주는 어떤 광고문구를 등록 했길래 이렇게 나올 수있는거지?

 

b -> 전광판: bbbbb

ba -> 전광판: babab

bab -> 전광판: babba (오 얘는 전광판을 봤던 그 문구가 맞구나)

babb -> 전광판: babbb 

babba -> 전광판: babba (오 얘는 전광판을 봤던 그 문구가 맞구나)

 

광고주는 bab, babba 두 광고문자를 전광판에 등록했을 가능성이 있는데 이때 길이가 가장 짧은 것은 bab!이구나!!

 

한 두시간동안 짧은 문제를 여러번 보면서 드디어 문제에 대한 이해를 하게 되었습니다...

 

이제 어떻게 풀지 고민했고 prefix == suffix....가 가장 큰 길이를 뺀 경우가 광고문구의 최소길이라는 것을 알게되었습니다.. 

prefix == suffix 구하는 부분 일치 테이블의 개념을 알아야 합니다.

 

결국 전광판 text: babba에서 prefix == suffix가 최대인 suffix의 길이를 뺀 것이 광고문구 최소길이 값임을 알 수 있습니다. prefix==suffix를 어떻게 생각해 냈을까요(kmp알고리즘 분류의 문제를 골랐습니다..)흫 코딩테스트에서 이 문제를 봤다면 못 풀었을 것입니다.. 문제 이해하기가 정말 어렵네요.ㅠㅠ(분발해야겠습니다.)

코드

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

var n = Int(readLine()!)!
var text = readLine()!.map{String($0)}

/// 광고판에 부착된 광고문구
var ad = [String]()
_=(0..<n).map{ i in
	ad.append(text[i%text.count]
}
let pi = getPartialMatched(n: ad)
print(n-pi[n-1])

 

포스트 내용 중 틀린 내용이 있다면 댓글을 통해 알려주시면 정말 감사합니다 !!!!!