계수정렬(counting sort)1 > 문제은행



문제은행

3339 : 계수정렬(counting sort)1

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 37 회    시도횟수: 97 회   



N개의 정수를 입력받아 오름차순으로 정렬하고

Q개의 질의에 응답하는 프로그램을 작성하시오.

질의는 정렬된 결과에서 idx에 위치하는 값이 무엇인지에 응답하는 것이다.

 

아래 main 코드는 사용자의 코드작성을 돕기 위한것으로

실제 채점시에는 다른 방법으로 채점될 수 있다.​ 

 

사용자는 user.cpp파일만 완성하여 제출한다.

user.cpp에는 변수와 함수를 추가할 수 있으나, 헤더파일은 사용할 수 없다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/// *** user.cpp ***
 
void countingSort(int arraySize, int *arr){
 
}
 
int query(int idx){
 
    return 0;
}
 
/// *** main.cpp ***
#include <stdio.h>
#define MAX_SIZE (1000000)
 
static ​int N, Q, A[MAX_SIZE];
 
extern void countingSort(intint*);
extern int query(int);
 
static void input(){
    scanf("%d"&N);
    for(int i=0;i<N;++i){
        scanf("%d", A+i);
    }
    countingSort(N, A);
}
 
static void run(){
    int i, idx;
    scanf("%d"&Q);
    for(i=0;i<Q;++i){
        scanf("%d"&idx);
        int userAns = query(idx);
        printf("%d\n", userAns);
    }
}
 
int main(){
    //freopen("input.txt", "r", stdin);
    input();
    run();
    return 0;
}
 
 

 

 




첫 행에 N이 주어진다. ( 10,000 <= N <= 1,000,000)
다음 행에 N개의 정수 ai 가 공백을 구분하여 입력된다. (-32,768 <= ai <= 32,767)
다음 행에 질의 수 Q가 입력된다. ( 10,000 <= Q <= 1,000,000)
다음 행에 Q개의 idx가 공백으로 구분되어 주어진다. ( 0 <= idx < N)



Q개의 질의에 대한 결과를 행으로 구분하여 출력한다.


7
4 2 7 5 3 1 6
5
2 3 5 0 1
3
4
6
1
2


출처 : comkiwer




HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 031-388-0999 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.