글 읽기 - 이게 카운팅 정렬 맞나요.....?

onnelim7791 4년 전 0

처음에 저는 카운팅 정렬에 대해 배우지 않고 메모리 제한이 8MB이므로 모든 입력값을 저장해서 비교하는 식으로 진행할 수 없다고 판단해서, 고민 끝에 입력받은 값들 별로 등장횟수를 배열에 저장하여 풀었습니다.

그런데 풀고 나서 카운팅 정렬에 대해 알아보니 메모리 효율은 좋지 않지만 속도가 매우빠르다고 하더군요.

그런데 제 코드의 결과는 메모리 소모도 그다지 높지 않고, 속도도 그렇게 빠르지 않은 것같은데 제가 푼 건 카운팅 정렬이 아닌가요?

#include <stdio.h>
#include <stdlib.h>

#define size 10000

int main() {
	int n, input;
	scanf_s("%d", &n);

	int arr[size] = { 0 };
	for (int i = 0; i < n; i++) {
		scanf_s("%d", &input);
		arr[input - 1]++;
	}

	for (int i = 0; i < size; i++) {
		for (int k = 0; k < arr[i]; k++) {
			printf("%d\n", i + 1);
		}
	}
	return 0;
}

djm03178 4년 전 0

메모리 효율이 좋지 않다는 건 예를 들어 주어지는 수의 범위가 1에서 10억까지인데, 원소가 둘밖에 없다면 단 2개의 카운트를 하기 위해 배열을 10억 칸 잡아야 하니 비효율적이라는 것입니다. 이 문제에서는 범위가 겨우 1만까지로 제한되어 있기 때문에 충분히 효율적입니다.

onnelim7791 4년 전 0

아 그런건가요...

다른 사람들 코드를 보니 저보다 코드도 복잡하고 속도도 더 빨라서 제 코드가 잘못된 건가 헷갈렸습니다 ..ㅠㅠ

djm03178 4년 전 1

무슨 코드를 보셨는지는 모르겠지만, '맞은 사람' 탭에서 보신 거라면 태반은 다 빠른 입출력을 써서 빠른 것입니다.

onnelim7791 4년 전 0

답변 정말 감사드립니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이게 카운팅 정렬 맞나요.....?

onnelim7791 4년 전 0

djm03178 4년 전 0

onnelim7791 4년 전 0

djm03178 4년 전 1

onnelim7791 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말