[백준 3015번] 오아시스 재결합 (java)

3015번: 오아시스 재결합

 

매번 느끼는거지만 스택을 이용한 문제는 개인적으로 너무 어렵다.. 보통 스택을 사용하는 문제의 경우, 스택 자체보다는 스택을 어떻게 사용해야할 지 생각해내는게 어려운 것 같다.

이번 문제도 역시 해결하는데 오랜 시간이 걸렸는데, 가장 어려웠던 것은 키가 같은 사람이 여러명일 경우에 어떻게 해야할지 고민을 오래 했다.

 

먼저, 이 문제는 특정 사람이 비교기준이 될 때, 스택안에 어떤 사람들이 들어가야 하는지 고민해야 한다.

 

2  4  3  2  1  2  2  5  1 순서대로 키를 가진 사람이 줄을 섰다고 하자.

키가 2인 5번째 사람(2  4  3  2  1  2  2  5  1)은 자신보다 앞에 줄을 선 사람들 중 누구를 볼 수 있을까?

5번째 사람이 볼 수 있는 자신보다 앞쪽의 사람들은 2번째, 3번째, 4번째 사람이 된다.

맨 앞에 있는 첫번째 사람은 2번째 사람에 의해서 시야가 가려지기 때문에 볼 수가 없다.

 

그렇다면 5번째 사람의 차례가 되었을 때 스택 안에는 2번째, 3번째, 4번째 사람의 정보가 들어있도록 로직을 세울 수 있다. 

즉, 새로 줄을 서게 된 사람이 그 사람들을 볼 수 있는지 없는지 확인을 거쳐야 하는 후보군들이 스택 안에 들어가야하는 것이다.

 

그러므로 스택 내에서는 키가 내림차순이 되도록 유지되어야 한다. 

중간에 키가 큰 사람이 존재하면 그 사람이 시야를 가려버리기 때문에 그 앞쪽에 있는 사람을 무조건 볼 수가 없다. 따라서 그 앞쪽의 사람은 애초에 볼 수 있는지 없는지 여부를 판단할 후보군에서 제외되어 버리기 때문이다. 

 

이제 해야할 일은 새로 줄을 선 사람의 키에 따라 로직을 다르게 세우는 것이다.

 

- 스택의 top에 있는 사람(새로 들어온 사람의 바로 앞쪽 사람)의 키가 새로 줄을 선 사람의 키보다 큰 경우,새로 들어온 사람이 스택 내에 새로 추가되어도 내림차순이 유지된다. 따라서 새로 줄을 선 사람의 키 정보를 스택에 push한다.

 

- top에 있는 사람의 키가 새로 줄을 선 사람의 키보다 작다면,

스택에서 하나씩 pop하면서 카운트를 증가시킨다.

자신보다 키가 작은 사람들을 모두 pop하고도 스택에 남아있는 사람이 있다면 한번 더 카운트를 증가시킨다. 그 사람도 볼 수 있기 때문이다. 

 

아래 그림에서는 키가 4인 사람이 자신보다 앞쪽에 있는 사람들 중 총 4명을 볼 수 있다.

그래서 총 카운트가 4번 증가하며, 이것은 자신보다 앞에 선 사람들 중 총 4명을 볼 수 있음을 의미한다.

그리고 마지막으로 자기 자신을 스택에 push한다.

 

 

 

여태까지 설명한 것을 소스코드로 나타내면 아래와 같다.

for (int i = 0; i < N; i++) {
		int n = Integer.parseInt(br.readLine());

       // 자신보다 키가 작은 경우 스택에서 pop
		while (!stack.empty() && stack.peek().height <= n) {
			stack.pop();
			cnt++;
		}

		if (!stack.empty())
			cnt++;

		stack.push(pair);
}

 

그런데 여기서 주의해야할 것이 있다.

문제에서는 키가 같은 사람이 여러번 등장할 수 있기 때문이다.

예를 들어, 아래와 같이 문제가 주어졌다고 할 때, 4번째 사람의 차례이고 현재 스택에는 2번째 사람의 키 정보와 3번째 사람의 키 정보가 들어있다고 하자.

 

초록색 막대의 사람이 스택에 들어있다는 의미이다.

 

 

스택의 top은 1이 있고, 새로 들어온 4번째 사람의 키도 1이다. 스택이 내림차순을 유지해야 하므로 스택에서 top에 있는 사람을 pop한다. 그리고 카운트를 하나 증가시킨다. 그 다음의 top에는 키가 4인 사람이 있으므로 자신보다 크기 때문에 더 이상 pop하지 않고, 카운트를 하나 더 증가시키고 자기 자신을 push한다.

따라서, 총 카운트는 2가 증가한다.

 

 

이제, 5번째 사람이 새로 줄을 섰다고 하자. 위와 마찬가지로 자기보다 작은 키를 가진 사람을 스택에서 pop하면 다음과 같이 되며, 이 때의 카운트는 2가 증가한다.

 

그런데 여기서 문제가 발생한다. 원래대로라면 5번째 사람의 앞에 있는 사람들 중 볼 수 있는 사람은 총 3명이다. 자신 앞에 키가 1인 사람이 둘이 있었기 때문이다. 하지만 이 직전에 스택에서 키가 1인 사람을 pop했기 때문에 카운트가 3이 아니라 2만 증가하게 되었다.

 

따라서 스택에 키 정보 외에, 같은 키의 사람이 몇 번 등장했는지를 카운트한 카운트 정보도 같이 넣어줘야 한다. 즉, 스택에 들어가는 자료형이 Integer이 아니라 height와 cnt 정보가 함께 들어있는 Pair객체가 들어가도록 해야한다.

		for (int i = 0; i < N; i++) {
			int n = Integer.parseInt(br.readLine());
			Pair pair = new Pair(n, 1);

			while (!stack.empty() && stack.peek().height <= n) {
				Pair pop = stack.pop();
				cnt += pop.cnt;
				if (pop.height == n)
					pair.cnt += pop.cnt;
			}

			if (!stack.empty())
				cnt++;

			stack.push(pair);
		}

	static class Pair {

		int height;
		int cnt;

		Pair(int height, int cnt) {
			this.height = height;
			this.cnt = cnt;
		}
	}

 

그래서 스택에서 pop할 때마다 자신의 키와 같은 키의 사람을 만나면 pair의 cnt를 하나씩 증가시킨다.

그리고 카운트를 증가시킬 때는 스택의 top에 있는 Pair객체의 cnt값만큼 더해주도록 한다.

 

 

전체코드 :