[코딩테스트] 백준 #10989 문제 풀이

이 문제는 풀이법이 두가지가 존재한다. 가장 먼저 떠오르는 풀이법은 알고리즘 sort()를 사용하는 것이고, 두번째는 새로운 배열을 하나 생성하여 출력하는 것이다. 하지만 sort()를 사용하게 된다면 메모리 초과가 뜬다. 100000을 입력값으로 넣어야 하기 때문이다. 결국은 두번째 방법을 사용해야 가능하다. 하지만 sort() 알고리즘에 대해 공부도 할 겸 배워보자.

sort()

sort() 함수는 기본적으로 오름차순으로 정렬을 수행한다. 배열을 입력 받았으면 배열의 시작점 주소와 마지막 주소+1 을 적어주면 된다.

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
	int a[10] = {2, 5, 3, 1, 9, 7, 3, 5, 7, 2};
    
    sort(a + 0, a + 10);
    
    for(int i=0; i < 10; i++)
    {
    	cout << a[i] << endl;
    }
}

compare()함수를 만들어서 사용하면 오름차순, 내림차순이 모두 구현이 가능하다.
sort()의 세번째 인자 값으로 compare을 넣어주면 해결이 된다.

#include <iostream>
#include <algorithm>

using namespace std;

bool compare(int a, int b)
{
	return a > b // a < b를 사용하면 오름차순
}

int main()
{
	int a[10] = {2, 5, 3, 1, 9, 7, 3, 5, 7, 2};
    
    sort(a + 0, a + 10);
    
    for(int i=0; i < 10; i++)
    {
    	cout << a[i] << endl;
    }
}

다른 방법(정답)

다른 방법은 배열을 하나 생성하고 cin으로는 숫자를 받는다. 그리고 그 숫자에 해당하는 메모리 칸에 그 숫자가 등장할 때마다 +1을 해주는 것이다. 그리고 이중 for문을 사용하여 해당 배열로 접근, 그리고 +1씩 해줬던 만큼의 그 수를 출력하는 것이다.

이렇게 코드를 작성하면 역시 시간초과가 뜨기 때문에 반드시 앞에 이 코드를 작성해줘야 한다.

#include <iostream>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int number;
    cin >> number;
    
    int Array[10001] = {0};
    
    for(int i=0; i < number; i++)
    {
        int th;
        cin >> th;
        Array[th]+=1;
    }
    
    for(int i=1; i < 10001; i++)
    {
        for(int j=0; j < Array[i]; j++)
        {
            cout << i << "\n";
        }
    }
}

배열을 쓰고 싶다? 그러면 int 말고 string으로 작성하여 str.length()와 배열 인덱싱을 사용해보는 것도 생각해보자~!