[C/C++] 코드업(codeup) 3130번 소들의 헤어스타일

▽문제 바로가기

https://codeup.kr/problem.php?id=3130

소들의 헤어스타일

---

입력

첫번째 줄에 소의 수 N이 입력된다.(1 <= N <= 80,000)

두 번째 줄 부터 N+1번째 줄까지 각 소들의 키가 입력된다. ( 1 <= hi <= 1,000,000,000 )

 

출력

각 소들이 헤어 스타일을 확인할 수 있는 소들의 수를 출력한다.

 

문제 풀이

 

자신과 키가 같거나 자신보다 키가 큰 소의 헤어스타일을 확인할 수 없습니다.

입력이 80000입니다. 이중 포문을 사용하여 완전 탐색을 하면 최악의 경우 10억이 넘는 탐색을 하게 되어 시간 초과가 발생합니다.

 

스택을 이용해서 이러한 문제를 해결 할 수 있습니다. 입력받은 수 보다 작은 값이면 pop 하여 앞에 있는 소들이 자신보다 키가 큰 소들만 남게 할 수 있습니다. 즉, 자신이 볼 수 있는 소가 몇 마리인지가 아닌 자신을 볼 수 있는 소가 몇 마리인지 파악하는 것으로 접근할 수 있습니다.

 

예를 들어 (10 3 7 4 12 2) 의 입력을 받았다고 해봅시다.

 

10 입력 : 스택에 아무것도 없으니 push / ( 10 )

10을 볼 수 있는 소는 없습니다. 0

 

3 입력 : top인 10이 입력된 3보다 크므로 push / ( 10 3 )

3을 볼 수 있는 소는 1마리입니다. 0 + 1

 

7 입력 : top인 3이 입력된 7보다 작으므로 pop / ( 10 ) -> top인 10이 입력된 7보다 크므로 push / ( 10 7 )

7을 볼 수 있는 소는 1마리입니다. 0 + 1 + 1

 

4 입력 : top인 7이 입력된 4보다 크므로 push / ( 10 7 4 )

4를 볼 수 있는 소는 2마리입니다. 0 + 1 + 1 + 2

 

12 입력 : top인 4가 입력된 12보다 작으므로 pop / ( 10 7 ) -> top인 7이 입력된 12보다 작으므로 pop / ( 10 ) -> top인 10이 입력된 12보다 작으므로 pop / ( ) -> 스택에 아무것도 없으니 push / ( 12 )

12를 볼 수 있는 소는 없습니다. 0 + 1 + 1 + 2 + 0

 

2 입력 : top인 12가 입력된 2보다 크므로 push / ( 12 2 )

2를 볼 수 있는 소는 1마리입니다. 0 + 1 + 1 + 2 + 0 + 1

 

합을 더하니 5입니다.

 

#include <iostream>

using namespace std;

int main(){
	
	int n;
	cin >> n;
	
	long long int arr[n];
	int top = -1;
	long long int sum = 0;
	for(int i=0;i<n;i++){
		scanf("%lld", &arr[i]);
		
		//스택에 쌓인값이 없다면 추가
		if(top==-1){
			top++;
			arr[top] = arr[i];
			continue;
		}
		
		//입력된 값이 top값보다 크다면 
		else if(arr[top]<=arr[i]){
			//top이 입력값보다 클 때까지 pop 
			while(top!=-1&&(arr[top]<=arr[i])){
				arr[top] = 0;
				top--;
			}
		}
		
		//push
		top++;
		arr[top] = arr[i];
		sum += top;	//입력값소의 헤어스타일을 볼 수 있는 소의 수 추가
		
	}
	
	cout << sum;
		
	
}