[정올 1141] 불쾌한 날(Bad Hair Day)

http://jungol.co.kr/bbs/board.php?bo_table=pbank&code=1141&sca=99 

JUNGOL

#include <cstdio>
#include <iostream>
#include <stack>	// 스택 라이브러리 활용 
int N;
int cow[80000 + 10];
long long total;	// int 범위를 넘길 수 있다. 

std::stack<int> stk;

void input(void)
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &cow[i]);
	}
}

void bad_hair(void)
{
	stk = {};	// 스택 초기화 
	for (int i = 0; i < N; i++) {
		while (!stk.empty() && stk.top() <= cow[i]) { // 자신과 키가 같거나 작은 소는 자신을 볼 수 없다. 
			stk.pop();
		}
		total += stk.size();
		//printf("%d ", stk.size());
		stk.push(cow[i]);
	}
}


int main()
{
	input();
	bad_hair();
	printf("%lld", total);
	return 0;
}

C는 스택을 처음부터 끝까지 구현해야하지만, C++은 #include <stack> 라이브러리를 통해 스택 자료구조를 활용할 수 있다. 

가장 좋은 점은 push(), pop(), size() 등의 메서드들을 통해 원소를 제거하거나, 추가하고 스택의 사이즈를 얻기 쉽다는 것이다. 다만 사용시 한 가지 주의할 것은 파이썬에서는 pop()을 통해 스택의 가장 위의 원소를 확인하면서 이를 제거할 수 있지만, C++에서는 top() 메서드로 가장 위의 원소를 확인하고, pop()으로 꺼내야 한다는 점이다. 

 

 

이 문제도 짱구를 좀 굴려야한다. 

문제의 예시처럼 곧이 곧대로 (1번 소가 볼 수 있는 소들의 수 : 3), (2번 소가 볼 수 있는 소들의 수 : 0), (3번 소가 볼 수 있는 소들의 수 : 1), ... 이런식으로 생각하면 구현이 어렵다. 

따라서 " i 번째 소를 볼 수 있는 소들의 수"를 생각해야 한다. 

즉, 첫 번째 소는 가장 앞에 있으므로 아무도 보지 못한다. => 0

      두 번째 소는 1번째 소 보다 키가 작으므로 1번째 소가 볼 수 있다. => 1

      세 번째 소는 1번째 소 보다 키가 작으므로 1번째 소가 볼 수 있다. => 1

      네 번째 소는 1번째 소 보다 키가 작고, 3번째 소 보다 키가 작으므로 1, 3 번째 소가 볼 수 있다. => 2

      다섯 번째 소는 그 앞의 모든 소들보다 키가 크므로 아무도 볼 수 없다. => 0

      여섯 번째 소는 5번째 소 보다 키가 작으므로 5번째 소가 볼 수 있다. => 1

따라서 이 결과를 모두 더한 0 + 1 + 1 + 2 + 0 + 1 = 5 가 정답이다. 

 

 

// bad_hair() 함수

위의 로직을 바탕으로, 스택에 넣을 원소는 "i 번째 소를 볼 수 있는 소" 이다. 

만약 새로 확인하는 소(cow[i])가 스택의 가장 위에 있는 소(stk.top())보다 키가 크거나 같으면, 스택의 가장 위에 있는 소는 새로운 소의 머리를 보지 못하므로 stk.pop() 해준다. 

반면 새로 확인하는 소(cow[i])가 스택의 가장 위에있는 소(stk.pop())보다 작으면, 스택의 가장 위에있는 소는 새로운 소의 머리를 볼 수 있다. "i 번째 소"를 볼 수 있는 소들의 수는 기존에 스택에 있던 소들의 수(stk.size())이고, 이를  total에 더해준 후 i 번째 소를 스택에 쌓아준다. 

void bad_hair(void)
{
	stk = {};
	for (int i = 0; i < N; i++) {
		for (;;) {	// for 루프로도 물론 구현 가능하지만,, 개인적으로 while이 더 깔끔한 것 같다.
			if (!stk.empty() && stk.top() <= cow[i]) {
				stk.pop();
			}
			else break;
		}
		total += stk.size();
		//printf("%d ", stk.size());
		stk.push(cow[i]);
	}
}

 

 

// printf("%lld", total);

여기서 배열은 int 범위 내에서 해결 가능하지만, 가장 최악의 경우를 생각해봐야 한다. 

만약 80,000마리의 소가 있는데 키가 80,000부터 1까지 내림차순으로 정렬되어 있다면, total값은 (80,000) * (80,000 + 1) / 2 (등차수열의 합... ^^..) 이다. 이 경우 그 값이 약 3,200,000,000 이므로 lld로 처리해주어야 한다.