[백준/Swift] 16472번: 고냥이

 

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

16472번: 고냥이

 

 

알파벳 종류 최대 N개인 연속된 문자열을 선택하고 가장 긴 문자열의 길이를 구하는 문제로, 두 포인터를 사용하면 된다.

 

sort: 지금까지의 알파벳 종류

count: 알파벳 카운팅 배열 (인덱스 => 알파벳 순서대로)

 

왼쪽 포인터 L을 고정하고, R을 뒤로 이동시킨다.

1. R을 뒤로 이동시키면서 해당 위치의 알파벳을 추가한다.(add(x:) 메서드)

    -> 이때 문자열을 따로 두지 않고 count 배열에 해당 알파벳의 개수를 카운팅 한다. 

2. 알파벳 종류(sort)가 최대 종류(n) 보다 크다면 이때부터 선택한 알파벳 중 가장 앞 알파벳을 제거한다.(erase(x:) 메서드)

    L도 앞으로 이동  

    만약 선택한 알파벳 종류가 최대 종류보다 작다면 계속 더 선택해도 되므로 while 문은 넘긴다.

3. answer 업데이트 (최대 길이를 구하므로 max 함수를 사용해서 갱신시킨다)

 

add()와 erase()에서는 추가한 알파벳의 개수를 count 배열에 갱신시켜 주는데, 

이때 add의 경우 1이라면 sort + 1 -> 새롭게 추가된 알파벳 종류

erase의 경우 0이라면 sort - 1 -> 선택된 알파벳에 이 알파벳 종류가 빠졌기 때문

 

 

import Foundation

//input
let n = Int(readLine()!)!
var array = readLine()!.map{ String($0) }
var sort = 0
var count = [Int](repeating: 0, count: 26)

func add(x: String) {
    let index = Int(UnicodeScalar(x)!.value) - Int(UnicodeScalar("a").value)
    count[index] += 1
    if count[index] == 1 {
        sort += 1
    }
}

func erase(x: String) {
    let index = Int(UnicodeScalar(x)!.value) - Int(UnicodeScalar("a").value)
    count[index] -= 1
    if count[index] == 0 {
        sort -= 1
    }
}

func solution(){
    var answer = 0
    var l = 0
    for r in 0..<array.count {
        add(x: array[r])
        while sort > n { //알파벳 종류 n개를 넘은 경우
            erase(x: array[l])
            l += 1
        }
        answer = max(answer, r-l+1)
    }
    print(answer)
}
solution()