19. 분노유발자

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

 

 

입력예제 1

10
56 46 55 76 65 53 52 53 55 50

 

출력예제 1 

3

 

풀이 

처음 생각한 풀이법

 

56	46	55	76	65
i	j	j	j
	cnt = 1	cnt = 2	break

 

- i를 고정시키고 j로 for문을 돌면서 뒤의 숫자들과 비교

- 뒤의 모든 숫자들보다 i번째 숫자가 크다면 분노유발자

- cnt 변수를 사용해서 i가 j보다 클 시 cnt를 증가, cnt카운트가 뒤의 숫자의 갯수와 일치할 시 분노유발자

코드

#include <iostream>
using namespace std;

int main(){
    int n, height[101];
    int res = 0;
    int cnt = 0;
    
    cin >> n;
    
    for(int i = 0; i < n ; i++){
        cin >> height[i];
    }
    
    for(int i = 0 ; i < n - 1; i++){
        for(int j = i + 1; j < n; j++){
            if(height[i] > height[j]){
                cnt ++;
            }else{
                break;
            }
        }
        if(cnt == n-i-1) {
            res ++;
        }
        cnt = 0;
    }
    
    
    cout << res << endl;
    
}

 

 

인강을 통해 배운 풀이법

 

55	76	65
max > 55	max < 76	max
분노유발자 X	분노유발자 max = 76

 

- 뒤에서부터 max값을 설정 후 하나씩 앞으로 당기면서 비교

- 뒤에서 비교하기 때문에 max값 = 뒤의 어떤 값보다 가장 큰 값

 

코드

#include <iostream>
using namespace std;

int main(){
    int n, height[101];
    int res = 0;
    
    cin >> n;
    
    for(int i = 0; i < n ; i++){
        cin >> height[i];
    }
    
    int max = height[n-1];
    
    for(int i = n - 2 ; i >= 0; i--){
        if(max < height[i]){
            max = height[i];
            res++;
        }
    }
    
    cout << res<< endl;
    
}