💡[BOJ 20922 / 코틀린] 겹치는 건 싫어 - 투 포인터

백준 20922_겹치는 건 싫어 | 문제 링크

투 포인터 기법을 활용한 문제입니다.

 

문제 설명

N개의 자연수로 이루어진 수열에서, 같은 수가 K번 이하로 반복되는 최장 연속 부분 수열을 구하는 문제입니다.

N은 1~200,000 , K는 1~100 범위의 정수로 주어집니다.각 원소 ai는 1~100,000 범위의 정수로 주어집니다.

 

입력

첫째 줄에 정수 N과 K가 주어진다.

둘째 줄에는 a1,a2,...an이 주어진다.

입력 예

 

출력

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

 

출력예

 

Main 함수 (전체 코드)

import java.util.*

fun main() {
	var N:Int = 0
	var K:Int = 0
	readLine()!!.split(" ").let {
		N = it[0].toInt()
		K = it[1].toInt()
	}
	val a = readLine()!!.split(" ").map { it.toInt() }	// 1
	var maxLen = 0
	var length = 0
	var start = 0
	var end = 0
	val checked = Array(101010) {LinkedList<Int>()}	// 2
	while (end != N) {	// 3
		if (checked[a[end]].size < K) {
			checked[a[end]].add(end)
			length++
			end++
		} else {
			val new = checked[a[end]].poll() + 1
			if (new > start) {
				length -= (new - start)
				start = new
			}
		}
		maxLen = Math.max(maxLen, length)	// 4
	}
	println(maxLen)
}

1. a는 List<Int> 자료형으로, 콘솔로부터 수열을 입력받아 저장합니다.
   maxLen 은 정답으로 출력할 최장 부분 수열의 길이를 저장합니다.
   length 는 각 부분수열의 길이입니다.
   start/end 는 현재 조회하고 있는 부분수열 조각의 시작/끝 인덱스입니다.
   
   
2. checked 는 Array<LinkedList<Int>> 자료형으로, Queue의 배열입니다. Queue인터페이스는 LinkedList 자료형으로 구현하였으며, Array의 크기는 수열 원소의 최댓값인 100000이 넘게 부여했습니다.
   Array의 인덱스는 수열에서 원소의 위치를 의미합니다. Queue의 Value는 수열에서 해당 값의 인덱스입니다.
   
   즉, checked[50] = {2, 8, 25, 54} 이면, 수열 a에서 값 50이 a2, a8, a25, a54에 순서대로 등장했음을 의미합니다.
   단, 모든 Queue의 크기는 최장 길이 제한 K를 넘지 않게 합니다.
   즉, 위의 예에서 K가 4였고, 값 50이 a66에 또 등장하면 먼저 들어온 a2를 poll()하고 a66을 add합니다.
   
   
3. 최장 부분 수열의 길이를 구하기 위해 수열 a의 끝까지 탐색합니다.
   start 는 고정시켜두고, end 를 1씩 더하며 a[end] 를 조회합니다.
   a[end] 가 이전에 K번 미만으로 나왔다면 checked[a[end]]에 end(인덱스)를 add() 해두고, length를 1 증가시킵니다.
   
   이미 K번 나왔고 또 나와서 이번이 K+1번째라면, 먼저 add() 됐던 인덱스를 poll() 합니다.
   그 값이 start보다 앞이라면 무시해도 되지만, start보다 뒤라면 poll()한 인덱스보다 뒤에서부터 조회를 해야 합니다. 즉, start 를 옮깁니다.
   
   
4. 현재 검사하는 부분 수열의 길이 length가 maxLen보다 크다면 maxLen을 업데이트합니다.

a[end]와 같은 값(Q 맨 앞)이 나온지 오래돼서 start보다 작을 때를 고려해주지 못해서 헤맨 모습