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

문제

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

2075번: N번째 큰 수

 

문제이해

• 첫째 줄에 N(1 ≤ N ≤ 1,500)을 입력한다.
• 다음 줄부터 N x N의 표가 주어진다.
• 출력으로 N번째 큰 수를 출력한다.

표의 특징은 모든 열들이 오름차순으로 정렬된채로 입력된다는 것이다. 열을 기준으로는 이미 크기순으로 정렬이 되어있기 때문에 vector로 구현하면 가능할 것 같아서 2차원 vector로 구현하였다. 각각의 열을 기준으로 입력을 받고 열들의 마지막 행의 값이 제일 큰 열의 마지막 원소를 제거하는 방식으로 해결하면 된다.

 

위의 표를 이용해 예시를 들어보겠다.

1. 열은 5개가 있고 각 열들의 마지막 행의 값은 (52, 20, 32, 41, 49)이다.
2. 5개의 숫자중 최댓값인 52를 제거한다.
3. N = 5 이기때문에 앞으로 4번 더 똑같은 방식으로 원소를 제거한다.
4. 마지막으로 제거되는 원소가 출력으로써 원하는 값이 된다.

다음은 해당 방식대로 구현된 코드이다.

문제풀이

#include<iostream>
#include<vector>
#define MIN -1000000001
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int N;
	cin >> N;
	vector<vector<int>> table(N, vector<int>(N));
	for (int i{ 0 }; i < N; i++) {
		for (int a{ 0 }; a < N; a++) {
			cin >> table[a][i];
		}
	}
	int maximum = MIN;
	for (int t{ 0 }; t < N; t++) {
		maximum = MIN;
		int row1{ 0 };
		int rowN{ 0 };
		for (auto& row : table) {
			int elem = row[row.size() - 1];
			if (elem > maximum) {
				maximum = elem;
				rowN = row1;
			}
			row1++;
		}
		table[rowN].pop_back();
	}
	cout << maximum;
}

 

문제후기

표의 특징을 이용했더니 생각보다 어렵지 않은 문제였다.