백준 2668. 숫자 고르기

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

2668번: 숫자고르기

 

뿌요뿌요처럼 스택을 이용해 스택의 top과 다음으로 들어오는 숫자과 같다면 없애버리면 된다.

예를들어 입력이 예제와 같다면 다음과 같은데 

1	2	3	4	5	6	7
3	1	1	5	5	4	6

먼저 처음의 1을 넣으면 짝이 3이기 때문에, 위가 3인 곳을 찾아가서 짝을 스택에 삽입한다.

(1 3 3 1 )

이러면 가운데 3이 붙어있어서 사라지고 (1 1) 이 되어 또다시 사라져 스택에는 아무것도 남지 않는다.

이렇게 스택이 empty 상태가 되면 두 집합이 모두 같은 숫자를 보유하고 있기 때문에 해당 숫자들은 선택 할 수 있다.

선택한 숫자들은 기록해놓고 다시 선택하지 않도록 한다.

 

 

 

 

 

---

dfs로도 풀수있다.