[백준알고리즘] 2751번: 수 정렬하기 2 -C++

[백준알고리즘] 2751번: 수 정렬하기 2 -C++

2751번: 수 정렬하기 2 (acmicpc.net)

2751번: 수 정렬하기 2

와... 정말 많은 코드를 내서 겨우 통과했다... 그런데 알고 봤더니 로직은 다 맞았었다... 후... 오늘도 이렇게 삽질로 배웠다..!

 

그리고 특이한 점을 또 발견했다!!

 

우선, 예전에 파이썬으로 풀었던 풀이에 대한 링크다. 이때 역시 거만하군ㅋ 역시 간단하게 풀어놓기도 했다..

[백준알고리즘] 2751번: 수 정렬하기 2 -Python (tistory.com)

[백준알고리즘] 2751번: 수 정렬하기 2 -Python

 

---

이번 포스팅에서는 내가 시도했던 여러 방법들을 모두 보이도록 하겠다. 그리고 각각이 통과하지 못했던 이유와 마지막에 왜 통과된 건지 모르겠는 코드를 하나 같이 삽입했다. 각각의 경우에 대해 실패한 것과 성공한 것의 차이는 동일했다. (마지막 코드를 제외하고)

 

vector와 sort 사용 (배열과 sort를 사용)

먼저, 첫 번째 코드다. 이 경우 vector에 입력 값을 넣은 뒤, sort를 이용해 정렬해주었다. 아래의 코드는 vector를 사용해 해결한 코드만 넣었다. 하지만, \(n\)의 크기의 배열을 사용해서 푼 방식도 동일한 문제를 겪었고, 동일한 방식으로 풀었다.

 

여기서, 시간 초과가 발생했었는데, 출력문을 나중에 ostringstream으로 출력 스트림을 만든 뒤 한 번의 cout 호출로 출력함으로써 시간 초과 문제를 해결했다.

 

ostringstream을 사용하기 위해 <sstream> 헤더를, sort를 사용하기 위해 <algorithm> 헤더를, 값을 저장하기 위해 <vector> 헤더를 포함시켰다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>

int main() {
    int n, temp; 
    std::vector<int> sorted;
    std::cin >> n;
    for (int i = 0; i < n; i++) 
    {
        std::cin >> temp;
        sorted.push_back(temp);
    }

    std::sort(sorted.begin(), sorted.end());
    std::ostringstream oss;
    for (int i = 0; i < n; i++) 
        oss << sorted[i] << std::endl;
    std::cout << oss.str();
}

 

priority_queue를 사용

두 번째로 시도한 코드였다. 이 경우 \(Min Heap\)을 구현하고 싶었으나, C++에서 STL로 제공하는 priority_queue를 사용했다. 

priority_queue를 사용하면서 입력과 동시에 정렬을 해주었고, 마지막에 작은 값부터 pop하며 정렬된 값을 만들었다.

 

이 경우도 첫 번재와 마찬가지로  시간 초과가 발생했다. 이 코드 역시 마지막에 ostringstream을 통해 출력 스트림을 만들고 한 번의 cout을 호출함으로써 문제를 해결할 수 있었다.

 

priority_queue를 사용하기 위해 <queue> 헤더를, ostringstream을 사용하기 위해 <sstream> 헤더를 사용했다. 

priority_queue의 경우에는 세 개의 값을 템플릿으로 받게 되는데, 두 번째와 세 번째는 각각 std::vector<> , std::less<>로 default 처리되어 있다. 따라서 평소에는 첫 번째 원소의 타입만 결정해주면 되었다. 

하지만, 여기서는 std::less<>를 통한 내림차순 정렬이 아닌, 오름차순 정렬이 필요하기 때문에 세 번째 값으로 std::greater<>를 사용하기 위해 두 번째 값도 직접 적어주었다. C++에서는 중간의 값만 생략할 수 없기 때문에 직접 std::vector도 적어주었다.

#include <iostream>
#include <queue>
#include <sstream>

void solve(void);

int main(void)
{
	solve();
}

void solve(void)
{
	int n;
	std::cin >> n;

	std::priority_queue<int, std::vector<int>, std::greater<>> pq;
	for (int i = 0; i < n; i++)
	{
		int temp;
		std::cin >> temp;
		pq.push(temp);
	}
    
    std::ostringstream oss;
	while (pq.size())
	{
		oss << pq.top() << std::endl; 
		pq.pop();
	}
    std::cout << oss.str();
}

 

배열을 이용

정렬을 따로 할 필요가 없는 방법이다.

 

모든 수가 들어갈 수 있을 크기의 배열을 선언한 뒤, 입력들어오는 값을 표시한다. 이후 배열을 작은 값부터 순회하면서 입력 들어온 값이 있는지 확인하는 방법이다.

 

이 경우도 마찬가지로 시간 초과가 발생했다. 따라서 이 역시 위의 두 문제와 마찬가지로  ostringstream을 사용해 cout을 한 번만 호출하도록 수정하고 문제를 통과할 수 있었다.

#include <iostream>
#include <sstream>

int main(void)
{
	int n;
	std::cin >> n;

	bool num[2000001] = { 0, };
	for (int i = 0; i < n; i++)
	{
		int temp;
		std::cin >> temp;
		num[1000000 + temp] = true;
	}

    std::ostringstream oss;
	for (int i = 0; i <= 2000000; i++)
		if (num[i])
            oss << i-1000000 << std::endl;
    std::cout << oss.str();
}

 

---

마지막으로 이거는 왜 통과했는지 모르겠는 코드다.

 

이때는 ostringstream을 사용하지도 않았고, cout을 여러 번 호출했음에도 통과했다. 게다가 위에 vector를 사용한 방법과 동일하기까지 하다. 

 

다만, 한 가지 다른 점은 std::endl를 사용하지 않았다는 점이다. std::endl 대신 '\n' 문자를 직접 넣었다.

 

이후 알고보니, std::endl은 '\n'와 같이 평상시에는 줄 바꿈으로 동일하게 사용하는데, std::endl의 경우에는 출력 버퍼 기능까지 하는 flush 함수까지 겸해서 느리다고 한다.

 

속도 차이를 비교한 블로그가 있어서 여기 가져와봤다. 관심 있으면 아래에서 한 번 속도를 봐보도록 하자!

[C/C++] endl 와 \n의 속도차이 :: 코딩 공부 일지 (tistory.com)

 

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    int n, temp; 
    std::cin >> n;

    std::vector<int> num;
    for (int i = 0; i < n; i++) 
    {
        std::cin >> temp;
        num.push_back(temp);
    }

    std::sort(num.begin(), num.end());
    for (int i = 0; i < n; i++) 
        std::cout << num[i] << '\n';
}

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다