분노유발자 / c / 제한시간 없음

▣ 문제

오늘은 수능이 끝난 다음날로 교장선생님은 1, 2학년 재학생들에게 강당에 모여 어벤져스 영 화를 보여준다고 하여 학생들이 강당에 모였습니다. 강당의 좌석은 영화관처럼 계단형이 아니라 평평한 바닥에 의자만 배치하고 학생들이 앉습니 다. 그런데 만약 앞자리에 앉은 키가 큰 학생이 앉으면 그 학생보다 앉은키가 작은 뒷자리 학 생은 스크린이 보이지 않습니다. 한 줄에 앉은키 정보가 주어지면 뒷사람 모두의 시야를 가려 영화 시청이 불가능하게 하는 분노유발자가 그 줄에 몇 명이 있는지 구하는 프로그램을 작성 하세요.

 

▣ 입력설명

- 첫 줄에 한 줄에 앉은 학생수 N(3<=N<=100)이 주어집니다. 두 번째 줄에 N명의 앉은 키 정보(45이상 100이하)가 앞 자리 학생부터 차례대로 주어집니다.

 

▣ 출력설명

- 자신의 뒷 사람 모두를 시청방해하는 학생수를 출력합니다.

 

▣ 입력 예시

10 56 46 55 76 65 53 52 53 55 50

 

▣ 출력 예시

3

 

<내 코드>

#pragma warning(disable:4996)
#include<stdio.h>

int main() {
	int n;
	int height[101];
	int cnt = 0;
	int res = 0;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &height[i]);
	}

	for (int i = 1; i < n; i++) {
		for (int j = i + 1; j <= n; j++) {
			if (height[i] > height[j]) cnt++;
			if (cnt == n - i)
				res++;
		}
		cnt = 0;
	}
	printf("%d\n", res);
	return 0;
}

 

<수정한 코드>

#pragma warning(disable:4996)
#include<stdio.h>

int main() {
	int n;
	int height[101];
	int cnt = 0;
	int max;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &height[i]);
	}
	max = height[n];
	for (int i = n - 1; i >= 1; i--) {
		if (height[i] > max) {
			max = height[i];
			cnt++;
		}
	}
	printf("%d\n", cnt);
	return 0;
}

먼저 맨뒷사람의 키를 max로 저장하고 그 앞에 있는 사람의 키를 비교하다가

max값이 바뀌는 지점에서 cnt++을 해준다.

1	2	3	4	5	6	7	8	9	10
56	46	55	76	65	53	52	53	55	50
			O	O				O

 

.

 

굳이 이중 for문으로 다 비교를 하지 않고 max값으로도 탐색이 가능하구먼