<백준> List of Unique Numbers(Gold 4)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/13144 List of Unique Numbers at main · heesoo-park/ForCodeKata

제출 결과

---

저녁 밥 아주 배터지게 먹고 바로 풀려고 했던 문제였다.

투 포인터를 써야한다는 건 알겠는데 코드로 풀어지지가 않았다.

아마 속이 좀 여유가 있는 상황이었으면 괜찮았을텐데 아니여서 집중이 잘 되지 않았다.

 

그래서 참고를 좀 해서 해결했는데 좀 달랐던 건 왼쪽 경계값을 특정 조건에 의해 올리는 게 아니라 반복문을 통해 올렸다는 것과 우측을 while문을 사용해서 일단 쭉 가게 했다는 것이었다.

후자는 좀 봤던 유형인데 생각을 '투포인터는 무조건 한개씩 가야해' 라고 해서 알아차리지 못했고 전자는 익숙하지 않은 패턴이었다.

물론 일반적으로 사용하는 것도 쓸 수는 있을 텐데 이게 훨씬 이 문제에서는 편리해보인다.

 

이제는 뭔가 O(N^2) 일 거 같은 문제에서 숫자가 너무 크거나 순회문제다 싶으면 가장 먼저 투 포인터와 슬라이딩 윈도우가 생각날 거 같다.

 

해당 방법으로 작성한 코드는 다음과 같다.

import java.io.*
import java.util.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    
    val n = br.readLine().toInt()
    val numbers = br.readLine().split(' ').map { it.toInt() }
    
    val visited = BooleanArray(100001)
    
    var right = 0
    var cnt = 0L
    for (left in 0 until n) {
        while (right < n) {
            if (visited[numbers[right]]) break
            visited[numbers[right]] = true
            right++
        }
        
        cnt += (right - left)
        visited[numbers[left]] = false
    }
    
    println(cnt)
}

 

참고)

https://chanho0912.tistory.com/45