CSES 2. Playlist (1141)

출처: https://cses.fi/problemset/task/1141

---

문제 설명

You are given a playlist of a radio station since its establishment. The playlist has a total of n songs.

What is the longest sequence of successive songs where each song is unique?

입력

The first input line contains an integer n: the number of songs.

The next line has n integers k)1,k_2,…,k_n: the id number of each song.

출력 

Print the length of the longest sequence of unique songs.

입력 예

8
1 2 1 3 2 7 4 2

출력 예

5

제약조건

• 1 <= n <= 2x10^5
• 1 <= k_i <= 10^9

---

문제 풀이 내용

입력받은 노래 목록을 set에 저장하며 중복목록을 확인한다. 중복목록이 나오면, 중복목록이 나오기 전에 있는 목록들을 지운다. 

노래 목록이 끝나면, set의 크기를 출력한다.

프로그램 내용

...
    long num_array[nSong] = {0};

    for (int idx = 0; idx < nSong; idx++)
        cin >> num_array[idx];

    set <int> slist;

    int id=0, idx=0;
    int sCount=0;

    while (idx < nSong)
        if ( slist.count(num_array[idx]))
            sCount = max(sCount, idx-id);
            while( num_array[id] != num_array[idx])
                slist.erase(num_array[id]);
                id++;
            id++;
        else
            slist.insert(num_array[idx]);
        idx++;

        sCount = max(sCount, idx-id);
...

 

Sorting and Searching ( link )