8020 : 플레이리스트
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
음악 플레이리스트에 $N$개의 노래가 순서대로 담겨 있습니다. 각 노래는 고유한 식별자(ID)로 표현됩니다.
연속된 노래들로 이루어진 부분 플레이리스트 중에서, 같은 노래가 두 번 이상 등장하지 않는 가장 긴 부분 플레이리스트의 길이를 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N \le 2 \times 10^5$
• $1 \le k_i \le 10^9$ (각 노래의 ID)
연속된 노래들로 이루어진 부분 플레이리스트 중에서, 같은 노래가 두 번 이상 등장하지 않는 가장 긴 부분 플레이리스트의 길이를 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N \le 2 \times 10^5$
• $1 \le k_i \le 10^9$ (각 노래의 ID)
입력 설명
첫째 줄에 정수 $N$이 주어집니다.
둘째 줄에 $N$개의 정수 $k_1, k_2, \ldots, k_N$이 공백으로 구분되어 주어집니다.
둘째 줄에 $N$개의 정수 $k_1, k_2, \ldots, k_N$이 공백으로 구분되어 주어집니다.
출력 설명
중복이 없는 가장 긴 연속 부분 플레이리스트의 길이를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
8
1 2 1 3 2 7 4 2
출력 예시
COPY
복사되었습니다!
복사되었습니다!
5도움
슬라이딩 윈도우(투 포인터)와 해시 맵(딕셔너리)을 사용합니다.
각 노래 ID가 가장 최근에 등장한 인덱스를 기록하며, 현재 노래가 윈도우 안에 이미 존재한다면 윈도우의 시작점($start$)을 해당 노래의 바로 다음 위치로 당겨주면서 최댓값을 갱신하면 $O(N)$ 시간에 해결할 수 있습니다.
각 노래 ID가 가장 최근에 등장한 인덱스를 기록하며, 현재 노래가 윈도우 안에 이미 존재한다면 윈도우의 시작점($start$)을 해당 노래의 바로 다음 위치로 당겨주면서 최댓값을 갱신하면 $O(N)$ 시간에 해결할 수 있습니다.