[백준(BOJ)] 5525 IOIOI - 스위프트(Swift)

[Silver I] IOIOI - 5525

문제 링크

성능 요약

메모리: 69260 KB, 시간: 152 ms

분류

문자열

문제 설명

N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 P_N이라고 한다.

• P₁ IOI
• P₂ IOIOI
• P₃ IOIOIOI
• P_N IOIOI...OI (O가 N개)

I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 P_N이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다.

출력

S에 P_N이 몇 군데 포함되어 있는지 출력한다.

 

풀이

i)

n의 길이에 맞는 IOI 문자열 Pn을 생성한 뒤, 배열을 순회하면서 만약 해당 문자열과 값이 같다면 개수를 세어주는 방식으로 진행했습니다.

Pn 문자열의 길이는 (n * 3) - (n - 1)로 구하고, 짝수 인덱스에는 I, 홀수 인덱스에는 O를 대입해줍니다.

 

다음은 코드입니다.

let n = Int(readLine()!)!
let m = Int(readLine()!)!
let s = Array(readLine()!)
let (words, pLength) = (["I", "O"], (n * 3) - (n - 1))
var (p, count) = ("", 0)

for idx in 0..<pLength {  // pn 구하기
    p += words[idx % 2]
}

for idx in 0...m - pLength {
    if s[idx] == "O" {
        continue
    }
    else if String(s[idx..<idx + pLength]) == p {
        count += 1
    }
}

print(count)

→ 50점 (서브태스크2 시간 초과)

 

서브 태스크 2번에서 시간초과가 나타났습니다. 

Pn을 만드는 과정과 인덱스를 하나씩 접근하기 때문에 나타난 문제로 보입니다.

 

ii)

Pn을 직접생성하는 것이 아니라, IOI만을 기준으로 접근합니다.

Pn은 IOIOI의 반복이기 때문에, IOI가 나타났을 때 특정 행동을 해준 후, 인덱스를 이동시키는 방식으로 진행할 수 있습니다.

 

IOI가 나타났을 때에는 OI는 확인할 필요가 없기 때문에 인덱스를 2만큼 이동시켜줄 수 있습니다.

 

IOI가 연속으로 나타날 때 횟수를 세준 뒤, 만약 n값과 같다면 정답을 하나 증가시켜줍니다.

만약 IOI가 아닌 경우에는 다음 인덱스로 이동합니다.

 

다음은 코드입니다.

let n = Int(readLine()!)!
let m = Int(readLine()!)!
let s = Array(readLine()!)
var (count, i, ans) = (0, 0, 0)

while i < m - 2 {
    if String(s[i...i+2]) == "IOI" {
        count += 1
        i += 2
        if count == n { // IOI가 n번 나왔을 때 pn만큼 성립으로 정답 추가
            count -= 1  // 다음 순서의 IOI가 나올 수도 있기 때문에 개수 하나 줄이기
            ans += 1
        }
    } else {    // IOI가 아닌 경우 -> IOI 개수 초기화
        i += 1
        count = 0
    }
}
print(ans)