[백준(BOJ)] 20922 겹치는 건 싫어 - 스위프트(Swift)

[Silver I] 겹치는 건 싫어 - 20922

문제 링크

성능 요약

메모리: 84644 KB, 시간: 88 ms

분류

두 포인터

문제 설명

홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 K개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다.

100,000 이하의 양의 정수로 이루어진 길이가 N인 수열이 주어진다. 이 수열에서 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자.

입력

첫째 줄에 정수 N(1≤N≤200,000)과 K(1≤K≤100)가 주어진다.

둘째 줄에는 a1,a2,...an{a_1, a_2, ... a_n}이 주어진다 (1≤ai≤100,000)

출력

조건을 만족하는 최장 연속 부분 수열의 길이를 출력한다.

 

풀이

투 포인터를 통해 문제를 해결할 수 있는데, left, right를 설정하고,

left는 k값이 현재 범위 안에 있는 개수보다 많을 때 이동하기 위한 포인터이고,

right는 k값이 현재 범위 안에 있는 개수보다 적을 때 이동하기 위한 포인터입니다.

 

만약 현재 값의 개수가 k보다 적게 있으면 해당 값이 추가되도 조건을 성립하기 때문에 right를 이동시킵니다.

만약 k보다 많이 있다면 해당 값을 줄여야하기 때문에 left를 이동시킵니다.

 

이동 후 길이의 최대값을 계속해서 갱신해준 뒤, 출력해줍니다.

 

코드로 보면 다음과 같습니다.

let nk = readLine()!.split(separator: " ").map { Int($0)! }
let (n, k) = (nk[0], nk[1])
let sequence = readLine()!.split(separator: " ").map { Int($0)! }
var (left, right, ans) = (0, 0, 0)
var countSequence = Array(repeating: 0, count: sequence.max()! + 1) // 최대값 + 1 만큼의 길이로 설정 (특정 값이 인덱스 값)

while right < n {   // 배열의 범위를 벗어나기 전까지 반복
    if countSequence[sequence[right]] < k { // 현재 값의 개수가 k보다 적을 때
        countSequence[sequence[right]] += 1
        right += 1
    } else {    // k보다 클 때
        countSequence[sequence[left]] -= 1  // left를 한 칸 옮겨주고 해당 값을 빼준다.
        left += 1
    }
    
    ans = max(ans, right - left)    // 계속해서 최대값 갱신
}
print(ans)