25. 석차 구하기

    25번 문제   

 

    내가 풀이한 답   

  문제도 짧고 흔할 것 같이 생긴 문제였다. 당장 생각나는 것은 입력받은 값들을 순회(for)를 돌면서 그 순회 속에 순회(for)를 돌아서 전것들과 비교하면서 하는 것이였다. 하지만, 요즘 Time Limit을 신경쓰고 있어서 그런지 이중 순회(for)를 안쓰려고 했다. 

 

 그래서 생각해낸 방법은 입력 받은 수들을 배열(a)에 저장하고 그 값들을 또 새로운 배열(b)에 저장한다. 배열 a를 다시 sort 함수를 이용해 오름차순으로 정렬하고 다음 값과 같지 않으면 전체 인원 - 인덱스를 빼준다. 이러면, 다음 값이 같은 값이여도 등수문제를 해결할 수 있다.

 

 이중 순회(for)를 안써서 시간상으로는 조금 더 빠르겠지만 메모리를 많이 잡아먹는 다는 단점과 라이브러리를 많이 사용한다는 단점이 있다. 

 

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

int c[101];
int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);

	int n, i;
	scanf("%d", &n);
	
	int *a = (int *)malloc(sizeof(int) * (n+1));
	int *b = (int *)malloc(sizeof(int) * (n+1));
	
	for(i=0; i<n; i++){
		scanf("%d", &a[i]);	
	}
	
	memcpy(b, a, sizeof(int)*(n+1));
	sort(a, a+n);
	
	for(i=0; i<n; i++){
		if(a[i] != a[i+1]){
			c[a[i]] = n-i;
		}
	}
	
	for(i=0; i<n; i++){
		printf("%d ", c[b[i]]);
	}
	
	free(a);
	free(b);	
	return 0;
}

 

 결과는 통과하였다.

 

 

    사이트의 답안   

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

 

  사이트의 답은 맨 처음 생각했던 방식이 나왔다. 입력 값의 범위가 크지 않으므로 이중 순회(for)를 돌아도 문제가 없었다.