26. 말아톤

이 문제의 저작권은 인프런 강의 "it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비" 에 있습니다.

 

 

 

 

문제 25

 

KSEA 장거리 달리기 대회가 진행되어 모든 선수가 반환점을 넘었다. 각 선수의 입장에서 자 기보다 앞에 달리고 있는 선수들 중 평소 실력이 자기보다 좋은 선수를 남은 거리 동안 앞지 르는 것은 불가능하다. 반대로, 평소 실력이 자기보다 좋지 않은 선수가 앞에 달리고 있으면 남은 거리 동안 앞지르는 것이 가능하다. 이러한 가정 하에서 각 선수는 자신이 앞으로 얻을 수 있는 최선의 등수를 알 수 있다. 각 선수의 평소 실력은 정수로 주어지는데 더 큰 값이 더 좋은 실력을 의미한다. 현재 달리고 있는 선수를 앞에서 부터 표시했을 때 평소 실력이 각각 2, 8, 10, 7, 1, 9, 4, 15라고 하면 각 선수가 얻을 수 있는 최선의 등수는 (같은 순서로) 각각 1, 1, 1, 3, 5, 2, 5, 1이 된다. 예 를 들어, 4번째로 달리고 있는 평소 실력이 7인 선수는 그 앞에서 달리고 있는 선수들 중 평 소 실력이 2인 선수만 앞지르는 것이 가능하고 평소실력이 8과 10인 선수들은 앞지르는 것이 불가능하므로, 최선의 등수는 3등이 된다. 선수들의 평소 실력을 현재 달리고 있는 순서대로 입력 받아서 각 선수의 최선의 등수를 계산 하는 프로그램을 작성하시오.

 

 

입력설명

 

첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 N개의 정수가 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 선수 부터 제시한 것이다. 각 정수는 1 이상 100,000 이하이다. 참가한 선수의 평소실력은 같을 수 있습니다. 그리고 실력이 같다면 앞에 달리는 선수를 앞지를 수 없습니다

 

 

 

입력예제

 

8

2 8 10 7 1 9 4 15

 

 

출력예제

 

1 1 1 3 5 2 5 1

 

 

 

---

 

뭔가 자료구조를 살짝 맛만이라도 보니까 어? 이거 중첩 반복문이네.. 그럼 시간복잡도가 O(n^2) 가 걸리지 않을까?

라고 생각했던 것 같다. 그래서 어떻게든 중첩 반복문을 피할려고 애써봤는데 아이디어는 잘 생각나는 것 같았으나 맘처럼 구현이 잘 안됐다ㅜㅜ 그래서 어쩔 수 없이 포기하고 바로 선생님의 영상을 봤다(아쉽아쉽... 하지만 내가 생각한게 컴퓨터로 푸는 방식으로는 안될 수 있으니까.. 아닌가? 모르겠다! 너무 어렵다 알고리즘..)

역시 선생님도 n^2 을 언급하셨다. 이 문제는 n이 10000 이하로 제한되어 있어서 N^2 로 풀어도 통과가 된다고 했다. 그리고 병합정렬에 대해서는 나중에 가르쳐주신다고 하셨다. 얼른 진도 나가야겠다.

 

 

 

 

 

<선생님의 아이디어를 얻고 내가 써본 코드>

 

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
	//freopen("input.txt", "rt", stdin);
	int i, n, j, cnt;
	
	scanf("%d", &n);
	vector<int> a(n);
	vector<int> b(n);
	
	for(i=0; i<n; i++){
		scanf("%d", &a[i]);
	}
	
	for(i=n-1; i>=0; i--){
		cnt=0;
		for(j=i; j>=0; j--){
			if(a[j]>=a[i]) cnt++;
		}
		b[i]=cnt;
	}
	
	for(i=0; i<n; i++){
		printf("%d ", b[i]);
	}
	return 0;
}

 

일단 for문 감소문으로 작성하려면 저런 식으로 작성해야된다. 가운데식을 부등호로 써야 하는거 잊지 말자!

(참고로 가운데 식을 부등호로 안쓰고 =으로 쓰니까 실행 결과가 다 0이 나오더라..)

그리고 i가 기준이 되고 j가 i부터 0까지 돌게 하려면 중첩 반복문을 저렇게 써야 하는 지식도 습득했다. 

마지막으로 새로운 배열을 써서 거기다가 카운트한 숫자를 써주었다!

 

 

 

 

선생님의 아이디어를 얻고 코드 작성해서 그런지 선생님의 코드랑 살짝 비슷해서 머리에 각인만 해두고 코드를 올리진 않겠다. 다만 병합정렬에 대해서 짧게 말씀하셨는데, 어떤 숫자의 왼쪽에 대해서 자신보다 큰 숫자를 nlogn 으로 발견할 수 있는 방법이 있다고 하셨다. 어차피 나중에 배울 것 같아서 일단 넘어가본다. 병합정렬을 배우고 여기로 다시 와서 봐도 괜찮을 것 같다.