[Algorithm] 19. 분노 유발자

인트로

처음 이중 for문으로 문제를 해결했는데 단일 for문으로도 가능했다는 걸 알았다.

두 방법 모두 포스팅하려 한다.

분노 유발자

문제

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

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

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

입력

10
56 46 55 76 65 53 52 53 55 50

출력

3

※ 76, 65, 55 세명이 분노 유발자입니다.

코드 : 이중 for문

코드

이중 for문을 돌며 자신 뒤에 자기보다 크거나 같은 학생이 있는지 검사한다.

크거나 같은 학생이 있으면 break로 내부 for문을 탈출한다.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n, res = 0;
	bool flag;

	cin >> n;

	vector<int> vec(n);

	for (int i = 0; i < n; i++)
		cin >> vec[i];

	for (int i = 0; i < n - 1; i++)
	{
		flag = true;

		for (int j = i + 1; j < n; j++)
		{
			if (vec[j] >= vec[i])
			{
				flag = false;
				break;
			}
		}

		if (flag) res++;
	}

	cout << res;
}

코드 : 단일 for문

코드

뒤부터 검사하면 단일 for문으로 문제를 해결할 수 있다.

맨 뒤 학생은 분노 유발자가 될 수 없다.

문제를 예로 들면, 맨 뒤 학생(50)의 값을 max로 잡고 n-2부터 0까지 인덱스를 줄여가며 max보다 큰지 검사한다.

내 키가 max보다 크다는 의미는 지금까지 내 뒤에 나보다 큰 사람이 없었단 뜻이다.

따라서 분노 유발자라는 조건을 자연스럽게 만족한다. 

 

[1] 56 46 55 76 65 53 52 53 55 50(max)

[2] 56 46 55 76 65 53 52 53 55(max 갱신, 분노 유발자) 50

[3] 56 46 55 76 65(max 갱신, 분노 유발자) 53 52 53 55 50

[4] 56 46 55 76(max 갱신, 분노 유발자) 65 53 52 53 55 50

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n, max, res = 0;
	bool flag;

	cin >> n;

	vector<int> vec(n);

	for (int i = 0; i < n; i++)
		cin >> vec[i];

	max = vec[n - 1];
	for (int i = n - 2; i >= 0; i--)
	{
		if (vec[i] > max)
		{
			res++;
			max = vec[i];
		}
	}

	cout << res;
}