취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 14646번 문제인 욱제는 결정장애야!!이다.
문제는 아래 링크를 확인하자.

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

돌림판을 돌려 걸리는 수가 순서대로 주어지므로, 이를 이용해 돌림판에 붙어있을 수 있는 스티커의 상태를 직접 시뮬레이션해 문제를 해결하자.

각 메뉴는 정확히 두 번씩만 걸리므로 방문여부를 저장하는 배열을 선언해 방문한 적이 없는 칸이라면 스티커의 개수가 1 늘어나고 방문한 적이 있는 칸이라면 스티커의 개수가 1 감소하게 한다면 돌림판 시뮬레이션을 구현할 수 있다.

위 시뮬레이션 과정에서 나올 수 있는, 가장 스티커가 많이 붙어있는 순간을 저장해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

bool chk[100001];

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

	int cnt = 0, mx = 0;
	int N; cin >> N;
	N *= 2;
	while (N--) {
		int x; cin >> x;
		if (chk[x]) cnt--;
		else {
			chk[x] = 1;
			cnt++;
			mx = max(mx, cnt);
		}
	}

	cout << mx;
}