NYPC 2022 Round 2-A | 사진작가

[문제]

 

N개의 구조물이 좌우로 배치되어 있다.

왼쪽에서 i번째 구조물의 색은 Ai​이다.

사진작가 배찌는 좌우로 연속한 구조물을 사진에 담으려고 한다.

다만, 배찌는 개성 있는 사진을 찍고 싶기 때문에 사진에 색이 같은 구조물이 여러 개 있으면 마음에 들어 하지 않고, 최대한 많은 구조물을 사진에 담고 싶어 한다.

구조물의 색 정보가 주어졌을 때, 한 사진에 담을 수 있는 구조물 수의 최댓값을 구하는 프로그램을 작성하시오.

 

 

[입력 형식]

 

첫 줄에 구조물의 수를 나타내는 정수 N이 주어진다. (1 ≤ N ≤ 200,000)

두 번째 줄에 N개의 정수 A1​, A2​, ⋯⋯, AN​이 공백으로 구분되어 주어진다. (1 ≤ Ai ​≤ 1,000,000)

 

 

[출력 형식]

 

첫 줄에 한 사진에 담을 수 있는 구조물 수의 최댓값을 출력한다.

 

 

[해설]

 

수열에서 각 수가 들어온 횟수를 배열에 저장합니다.

수열이 조건을 만족하기 위해서는 각 수가 한번 이하로 등장해야 하므로, 배열에 저장된 값이 1을 넘으면 안 됩니다.

이러한 방식으로 부분수열의 왼쪽 끝점을 고정했을 때, 가능한 오른쪽 끝점의 최댓값을 구할 수 있습니다.

한편 왼쪽 끝점이 점점 증가할 때 가능한 오른쪽 끝점의 최댓값 또한 점점 증가한다는 것을 알 수 있습니다.

그러므로 슬라이딩 윈도우를 활용해 O(N)에 문제를 해결하면 됩니다.

 

 

[C/C++ 코드]

 

#include <bits/stdc++.h>
using namespace std;
 
#define MAX 200001
int n,arr[MAX],result,mx,w;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>arr[i];
        mx=max(mx,arr[i]);
    }
    vector<int>brr(mx+1,-1);
    for(int i=0;i<n;i++){
        w=max(w,brr[arr[i]]+1);
        result=max(result,i-w+1);
        brr[arr[i]]=i;
    }
    cout<<result;
}