[Algorithm] 25. 석차 구하기 (Brute force 브루트 포스)

인트로

브루트 포스 알고리즘이 적용될 문제를 소개하려 한다.

 

브루트 포스 Brute force,

브루트 포스는 완전 탐색 알고리즘이다.
완전 탐색 알고리즘이란 모든 경우의 수를 조사하는 방법이다.
자료구조 내의 모든 데이터를 탐색해야 하기에 자료구조에 따른 적절한 탐색 방법이 필요하다.

탐색 기법의 예시를 소개하면
선형 자료구조를 탐색하는 순차 탐색과
트리와 그래프와 같은 비선형 자료구조를 탐색하는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있다.

석차 구하기

문제

N명의 학생의 수학 점수가 입력되면 각 학생의 석차를 입력된 순서대로 출력하는 프로그램을 작성하세요.

※ 입력설명
첫 줄에 N(1<=N<=100)이 입력되고, 두 번째 줄에 수학 점수를 의미하는 N개의 정수가 입력된다.

같은 점수가 입력될 경우 높은 석차로 동일 처리한다.
즉 가장 높은 점수가 92점인데 92점이 3명 존재하면 1등이 3명이고 그다음 학생은 4등이 된다. 점수는 100점 만점이다.

※ 출력설명
첫 줄에 입력된 순서대로 석차를 출력한다.

입력

5
90 85 92 95 90

출력

3 5 2 1 3

코드 설명

문제를 읽어보고 이중 for문으로 전수조사로 문제를 풀어야 하나 고민을 했다.

정렬해서 순위를 부여하는 방법도 존재하지만 순위를 관리하는 것도 까다로우며 어디까지나 모든 점수를 확인하고 비교해야 한다.  

무엇보다 입력되는 N의 값이 1~100 사이의 정수이므로 이중 for문을 돌며 전수조사하는 방법이 꽤나 합리적이라 생각했다.

 

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n;

	cin >> n;

	vector<int> scores(n);
	vector<int> ranks(n, 1);

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

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (scores[i] < scores[j])
				ranks[i]++;
		}
	}

	for (int i = 0; i < n; i++)
		cout << ranks[i] << " ";
}