사용자 도구

사이트 도구


ps:problems:boj:13144

List of Unique Numbers

ps
링크acmicpc.net/…
출처BOJ
문제 번호13144
문제명List of Unique Numbers
레벨골드 3
분류

투 포인터

시간복잡도O(n)
인풋사이즈n<=100000
사용한 언어Python
제출기록41744KB / 136ms
최고기록136ms
해결날짜2021/12/07

풀이

  • 중복 원소를 포함하지 않는 부분배열의 갯수를 구하는 문제.
  • R로 끝나는 부분배열 A[i…R] 에 대해서 생각해보면. 중복 원소를 포함하지 않는 A[i…R]의 갯수는, 중복 원소를 포함하지 않는 A[i…R]중에서 가장 크기가 긴 것의 길이와 같다. 따라서, 각각의 R에 대해서 조건을 만족하는 가장 작은 i가 뭐인지만 구해주면 되고, 이것은 투 포인터를 이용해서 O(n)에 처리할 수 있다.
  • 투 포인터를 이용해서 구현하는 방법은, 먼저 l포인터와 r포인터를 만들고, A[l…r] 안에 포함된 원소들을 set에 유지시킨다. r포인터를 이동시키면서 갯수를 갱신해주면 되고, r포인터를 이동시켰을때 중복 원소가 생긴다면, 그 중복 원소가 없어질때까지 l포인터를 이동시키면 된다.

코드

"""Solution code for "BOJ 13144. List of Unique Numbers".

- Problem link: https://www.acmicpc.net/problem/13144
- Solution link: http://www.teferi.net/ps/problems/boj/13144

Tags: [Two Pointer]
"""


def main():
    N = int(input())  # pylint: disable=unused-variable
    nums = [int(x) for x in input().split()]

    l_iter, r_iter = iter(nums), iter(nums)
    left, right = next(l_iter), next(r_iter)
    subarr = set()
    answer = 0
    while right is not None:
        if right in subarr:
            subarr.remove(left)
            left = next(l_iter)
        else:
            subarr.add(right)
            answer += len(subarr)
            right = next(r_iter, None)

    print(answer)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
W I E᠎ P T
 
ps/problems/boj/13144.txt · 마지막으로 수정됨: 2021/12/08 02:22 저자 teferi