[C++] 백준 11004번 K번째 수

1. 문제이해

https://www.acmicpc.net/problem/11004

11004번: K번째 수

 

숫자의 갯수 N개와 몇 번째 숫자를 출력할 것인지인 K를 입력받는다.

이후, 숫자를 정렬했을 때의 K번째 숫자를 출력하는 알고리즘을 구현하는 것이 목표이다.

 

 

 

2. 문제풀이

 

숫자를 입력받은 뒤, 이를 정렬하고 K번째의 숫자를 출력하면 되는 비교적 간단한 문제이다.

주의해야 할 부분은, 입력받는 숫자의 갯수인 N의 범위인데,

N의 범위가 0부터 5,000,000까지 이기때문에, 시간초과나 메모리 초과에 주의해 코드를 짜주었다.

 

 

 

3. 소스코드

#include <iostream>
#include <algorithm>

using namespace std;
long long int arr[5000000];

int main() {
	// 입출력 속도를 놓여주기 위함
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	// N은 입력받을 수의 갯수, K는 정렬했을때 몇 번째 수인지
	int N, K;	
	cin >> N >> K;

	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	sort(arr, arr + N);
	
	cout << arr[K - 1];

	return 0;
}

코드의 구성은 단순하다. N과 K를 입력받고, N의 갯수만큼 숫자들을 입력받아 배열에 저장한다.

이후 배열에 저장된 숫자들을 정렬해주고, (sort 함수를 사용해주었다.)

K번째에 있는 숫자를 출력해주었다. (배열은 0부터 시작이므로, K-1 번째출력)

문제는 위에서 이야기한 시간초과와 메모리 초과의 문제인데,

이를 해결하기 위해 나는 2가지 해결법을 적용했다.

 

첫번째는 배열로 인한 메모리 초과의 문제를 해결하기 위한 방법이다.

사실 이로 인해 계속 코드가 제대로 동작하지 않았는데,

디버깅을 통해 다음과 같은 오버플로우가 발생했음을 알 수 있었다.

test dword ptr [eax],eax ; probe page.

이러한 오류는 해당 프로젝트에서 설정해둔 스택 메모리 공간을 초과했기 때문에 발생하는 오류다.

 

해결방법은 2가지인데, 배열을 할당하는 이 부분을 long long int arr[5000000]; 전역변수로 설정하거나,

스택의 예약공간을 늘려주는 방법이 있다.

(프로젝트의 속성 > 링커 > 시스템 의 스택 예약 크기를 늘려 잡아주는 방법이다.)

나는 전자의 방법을 사용해, 지역변수가 사용되는 공간이 부족하므로, 배열을 전역변수로 빼주었다.

 

두번째는 시간초과 문제를 해결하기 위한 방법이다.

C++에서 cin과 cout을 사용하는 경우 상대적으로 처리가 느릴수 있다.

그럴때, 다음과 같은 구문을 추가해주면 속도를 높일 수 있다.

ios_base::sync_with_stdio(false);  cin.tie(NULL);

위와 같은 코드를 cin, cout 전에 추가해주면 알고리즘이 동작할때 시간이 단축되게 된다.

이를 통해, 코드를 실행했을때 시간초과가 발생하는 문제를 해결했다.

 

 

---

오늘은 어제 저녁 백신을 맞고 몸이 좋지 않아 느지막이 그나마 쉬운 문제로 골라 풀었다.

어느 문제를 풀지 고민하면서 항상 느끼는 거지만, 실버 5단계에는 정렬 문제가 참 많은 것 같다.

그리고, 정렬을 풀다보면.. 역시 C로 정렬을 하나하나 구현하기보다는

C++의 내장함수를 이용하는게 더 빠르고 간편한것 같긴 하다.😂

며칠 전에 내장함수는 되도록 쓰지 말아야지 해놓고..

내일 시간이 되면 C로도 내장함수를 쓰지 않고 구현해봐야겠다.