[코드트리 챌린지] 6주차 Two Pointer - Two Pointer / 겹치는 숫자가 없는 최대 구간

 

 

https://www.codetree.ai/missions/8/problems/max-interval-without-overlapping-numbers/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

코드:

#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;

int n;
int arr[100005]; // 주어지는 숫자 저장
int visited[100005]; // 구간 내 각 숫자의 개수 저장

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    int j = -1; // j를 0부터 확인해야하므로 -1로 초기화
    int maxLen = INT_MIN; // 중복이 존재하지 않는 구간의 최대 길이


    for (int i = 0; i < n; i++) {

        // j + 1이 범위 내에 존재하거나
        // visited[arr[j+1]] != 1인 경우 while문 반복
        // arr[j+1]에 해당하는 수의 방문 횟수를 늘리고 j 증가
        while (j + 1 < n && !visited[arr[j + 1]]) {
            visited[arr[j + 1]]++;
            j++;
        }

        // 최대길이 갱신
        maxLen = max(maxLen, j - i + 1);
        // i를 1 증가시키므로 그 자리에 존재했던 숫자의 방문 횟수는 감소
        visited[arr[i]]--;
    }

    cout << maxLen;
}

n을 입력받아 주어진 수로 arr 배열을 초기화합니다.

for문을 통해 0~n-1 까지의 수를 시작점으로 잡고 그 위치로부터 j까지 범위를 설정하여
중복된 수가 존재하는지 조사하는 방법으로 범위를 구하도록 합니다.

j 또한 0부터 시작해야하므로 j를 -1로 초기화 해준뒤 for문을 시작합니다.

만약 j+1이 범위 내에 존재하거나 visited[arr[j+1]] != 1인 경우 즉, 이미 arr[j+1]이란 수가
주어지지 않았을 경우 while문을 반복하여 visited[arr[j+1]]을 증가시키고 j를 증가시키도록 합니다.

만약 중복된 수가 존재하는 경우 j의 증가를 멈추고 현재까지의 범위를 maxLen과 비교하여 중복이 없는
최대 길이를 갱신한 뒤 i를 1 증가시킵니다.

이때 원래 i 자리에 있던 수는 포함하지 않게 되므로 visited[arr[i]]의 수는 1 감소시켜줍니다.