글 읽기 - [C++] 두 코드 차이점

cysdh01 3년 전 0

위쪽이 제 코드이고 밑에 있는 코드는 다른 분의 코드입니다. 문제를 해결하려고 방법을 찾다가 계수 정렬에 대해 보게 되어서 계수 정렬을 이용해서 문제를 해결하기는 했습니다.

그런데 다른 분의 코드를 보니 마지막에 출력할 때 누적합을 이용해서 하셨는데 이 부분이 잘 이해가 가지 않아서 일단 제가 이해되는 범위에서 누적합을 사용

하지 않고 cntarr의 값만큼 반복해서 출력하도록 했는데 문제는 맞았습니다.

혹시 이 부분에서 제가 이용한 방식의 문제점이 있거나 누적합을 이용하는 방식이 더 좋다거나 한 부분이 있는지 궁금합니다.

#include <iostream>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, temp;
	int cntarr[10001] = { 0, };

	cin >> n;
	
	for (int i = 0; i < n; i++)
	{
		cin >> temp;
		cntarr[temp]++;
	}

	for (int j=1; j<10001; j++)
	{
		int k = cntarr[j];

		while (k > 0)
		{
			cout << j << " ";
			k--;
		}
	}
}
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
#include <iostream>
using namespace std;
int main(void) {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int N, temp;
    int countArr[10001] = {0,};
    cin>>N;
    for(int i = 0; i < N; i++){
        cin>>temp;
        countArr[temp]++;
    }

    for(int j = 1; j < 10001; j++)
        countArr[j] += countArr[j-1];
    
    int k = 1;
    while(1){
        if(k > 10000)
            break;
        if(countArr[k] > countArr[k-1]){
            cout<<k<<'\n';
            countArr[k-1]++;
        }
        else
            k++;
    }
}

fbfbf1 3년 전 0

보통은 위의 방법으로 많이 푸니
딱히 문제점은 없습니다.

저도 위 방식으로 풀었습니다.

위의 방식이 counting sort에 더 맞아보이네요

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

문제

문제

출처

ICPC

[C++] 두 코드 차이점

cysdh01 3년 전 0

fbfbf1 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말