problem-solving
boj 13144: List of Unique Number
pikkaso
2021. 2. 7. 13:24
13144번: List of Unique Numbers
길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라.
www.acmicpc.net
전형적인 투 포인터, 슬라이딩 윈도우 문제인것 같다.
while(l<n)에 대하여 시행을 하도록 구현을 했는데, [l,r] 구간에 대하여 포함되는 모든 수들을 check를 해준다. 만약 다음 r+1칸을 계속 포함할 수 있으면 그냥 r++해주고 만약 그게 아니면 현재 구간 길이만큼 (1+2+3+...+(r-l+1)) 답에 더해주고 이전에 더해줬던 구간과 겹치는 구간의 길이만큼 답에 빼주면된다. 글고 r+1번째 숫자가 check제외해질때까지 l++해주면 되는데 (슬라이딩 윈도우) 이때
2 1 1 같이 같은수가 연속되는 경우에는 l > r 이 돼버리기 때문에 직전 r을 save 해주고 r과 l을 같은값으로 맞춰주면 된다.
글고 마지막으로 r = n-1인경우에는 그냥 해당 구간만큼 더해주고 겹치는구간 빼주면 된다.
