[C++] 백준 - 2075 : N번째 큰 수

문제 링크

 

풀이 )

  줄 개수만큼의 stack을 만든 후 새로 줄을 따라서 stack에 넣어줬다.

  st[0] = 12, 13, 21, 48, 52

  st[1] = 7, 8, 10, 14, 20

  st[2] = 9, 11, 26, 28, 32

  st[3] = 15, 19, 31, 35, 41

  st[4] = 5, 6, 16, 25, 49

 

  이후 각 stack의 top을 비교하여 총 n-1번에 거쳐 가장 큰 수를 제거한다.

  st[0] = 12, 13, 21

  st[1] = 7, 8, 10, 14, 20

  st[2] = 9, 11, 26, 28, 32

  st[3] = 15, 19, 31, 35

  st[4] = 5, 6, 16, 25

 

  마지막으로 각 stack의 top 중 가장 큰 값을 출력한다.

 

#include <iostream>
#include <stack>
#include <algorithm>

using namespace std;

int main(void){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;
	stack<int> st[n];
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < n; ++j){
			int tmp;
			cin >> tmp;
			st[j].push(tmp);
		}
	}
	for(int i = 0; i < n-1; ++i){
		int max_idx = 0;
		for(int j = 1; j < n; ++j){
			if(st[max_idx].top() < st[j].top()){
				max_idx = j;
			}
		}
		st[max_idx].pop();
	}

	int ans = st[0].top();
	for(int i = 1; i < n; ++i)
		ans = max(ans, st[i].top());
	cout << ans << endl;
	return 0;
}

 

주의 )

- cin을 사용하는 경우 std::ios::sync_with_stdio(false); std::cin.tie(nullptr);을 하지 않으면 시간초과가 난다.

- 단순히 모든 숫자를 정렬해서 n번째 수를 출력하려고 한다면 정렬하는데 최대 입력인 1500*1500에 대해서 nlogn의 시간이 소요되기 때문에 시간초과가 난다.