[Swift] 백준 16139 : 인간-컴퓨터 상호작용

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

16139번: 인간-컴퓨터 상호작용

 

 

풀이 과정

누저합 원리만 알고 있다면 크게 어려움이 없는 문제이다. 단, 1) 질문의 수가 최대 200,000번이기 때문에 매번 반복되지 않도록 한번 누적합을 구한 알파벳의 누적합은 저장해놓고 사용하도록 하고 2) 물어보지 않을 특정 문자가 있을 수 있기 때문에 특정 문자가 등장하는지에 대한 누적합을 처음 물어볼 때에만 누적합을 구하도록 한다.

 

먼저, 문자열을 입력을 받고 a-z에 대한 누적합과 a-z에 대한 누적합을 구했는지에 대한 여부를 flag역할을 하는 배열을 선언한다.

let chaArr: [Character] = Array(readLine()!)
let q = Int(readLine()!)!

//이차 배열로 a~z까지에 대한 누적합 배열
var psum: [[Int]] =
    [[Int]](repeating: [Int](repeating: 0, count: chaArr.count+1), count: Int(UnicodeScalar("z").value)-Int(UnicodeScalar("a").value)+1)

// 특정 문자에 대해 누적합을 이미 계산했는지에 대한 여부
var psumCheck: [Bool] = [Bool](repeating: false, count: Int(UnicodeScalar("z").value)-Int(UnicodeScalar("a").value)+1)

 

특정 문자가 문자열에 등장하는 횟수에 대한 누적합을 구하는 함수를 만든다.

func calculatePsum (_ alphabet: String) {
    let index = Int(UnicodeScalar(alphabet)!.value)-Int(UnicodeScalar("a").value)
    for i in 1...chaArr.count {
        psum[index][i] = psum[index][i-1] + (chaArr[i-1] == Character(alphabet) ? 1 : 0)
    }
}

 

이제 q번을 반복하면서 특정 문자에 대한 누적합을 구한다. 그리고 처음 누적합을 구하는 것이라면 누적합을 구하는 함수를 호출한 뒤 flag를 true로 바꾼다.

for _ in 0..<q {
    let inputArr = readLine()!.split(separator: " ").map{String($0)}
    let charIndex = Int(UnicodeScalar(inputArr[0])!.value) - Int(UnicodeScalar("a").value)
    if !psumCheck[charIndex] {
        calculatePsum(inputArr[0])
        psumCheck[charIndex] = true
    }
    print( psum[charIndex][Int(inputArr[2])!+1] - psum[charIndex][Int(inputArr[1])!])
}