백준14646 욱제는 결정장애야!!

작성일 | In

문제 링크

  • https://www.acmicpc.net/problem/14646

문제 출처

  • 제1회 천하제일 코딩대회 예선 B번

시간복잡도

  • O(n2)

풀이

n을 입력 받으면 2n개의 데이터가 주어집니다.

  1. n을 입력받습니다.
  2. 배열 하나를 생성합니다. 2.5. max값을 담을 변수 생성합니다.
  3. 데이터를 입력 받습니다.
  4. 입력받은 데이터가 2 에서 생성한 배열에 존재하지 않으면 배열에 삽입합니다.
  5. 존재하면 해당 데이터를 삭제합니다.
  6. max값을 담은 병수와 현재 배열의 길이 중 더 큰 값을 max 변수에 대입합니다.
  7. 3~6을 2n번 반복합니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;

int n;
int maxi = 0;
vector<int> arr;

vector<int>::iterator exist(int n){
	return find(arr.begin(), arr.end(), n);
}

int main(){
	cin>>n;
	for(int i=0; i<2*n; i++){
		int a;
		cin>>a;
		auto index=exist(a);
		if(index != arr.end()){
			arr.erase(index);
		}
		else{
			arr.push_back(a);
		}
		int len=arr.size();
		maxi=len>maxi?len:maxi;
	}
	printf("%d", maxi);
}