백준 34115 (C++) 먼 카드

최초 업로드: 2025-08-12 13:57:54

최근 수정 시간: 2025-08-12 13:58:22

게시자: rlatjwls3333

카테고리: 백준

# [Bronze III] 먼 카드

[문제 링크](https://www.acmicpc.net/problem/34115)

## 문제 설명

자연수가 적힌 카드 $2N$장이 있다. 이 카드들은 일렬로 왼쪽에서 오른쪽으로 나열되어 있다.

각 카드에는 $1$ 이상 $N$ 이하의 자연수가 정확히 하나씩 적혀 있다. 왼쪽에서 $i$ ($1 ≤ i ≤ 2N$)번째에 놓인 카드에 적힌 자연수를 $X_i$ 라고 하자.

$1 ≤ k ≤ N$인 각 $k$에 대해, $k$가 적힌 카드는 정확히 두 장이다. 즉, $1$부터 $N$까지의 각 자연수는 정확히 두 장의 카드에 적혀 있다.

정올이는 자연수 $k$가 적힌 두 카드 사이에 놓인 카드의 개수를 "$k$ 사이 카드 수"라고 부르기로 했다.

예를 들어, 아래 그림과 같이 카드가 놓여있다고 생각해 보자. 아래 그림에서 $N = 4$이고, $X_1 = 1$, $X_2 = 2$, $X_3 = 2$, $X_4 = 4$, $X_5 = 3$, $X_6 = 1$, $X_7 = 3$, $X_8 = 4$이다.

위의 사례에서 "$k$ 사이 카드 수"들 중 가장 큰 것은 "$1$ 사이 카드 수"로, 그 값은 $4$이다.

정올이는 $1$부터 $N$까지의 모든 자연수 $k$에 대한 "$k$ 사이 카드 수" 중 가장 큰 값을 구하고 싶다.

카드가 나열된 순서대로 카드에 적힌 자연수가 주어질 때, 모든 "$k$ 사이 카드 수" 중 가장 큰 값을 구하는 프로그램을 작성하라.

## 입력

첫 번째 줄에 정수 $N$이 주어진다.

두 번째 줄에 $2N$개의 정수 $X_1 , X_2 , \cdots, X_{2N}$이 공백을 사이에 두고 주어진다.

## 출력

첫 번째 줄에 답을 출력한다.

## 풀이
#### 두 카드의 시작 인덱스와, 끝나는 인덱스를 기록해 풀면 된다.

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

int firstIdx[2001], lastIdx[2001];

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n; cin >> n;
 for(int i=1;i<=2*n;i++) {
 int val; cin >> val;
 if(!firstIdx[val]) firstIdx[val]=i;
 else lastIdx[val]=i;
 }

int maxDist=0;
 for(int i=1;i<=n;i++) {
 maxDist = max(maxDist, lastIdx[i]-firstIdx[i]-1);
 }
 cout << maxDist;
}
```