[C++] 백준 20291번 - 파일 정리

substring과 map을 활용한 문제

map은 자료를 저장할때 red-black tree 구조로 구현이 되어있기 때문에 자동 정렬이 된다.

이는 int형 뿐만 아니라 string 형태에서도 char에 따라서 정렬을 한다.

'ab' < 'b' 이기 때문에 iterator.begin()은 'ab'를 가리키고 있을 것이다.

이러한 점만 고려하면 쉽게 풀 수 있는 문제이다.

물론 pair를 사용해서 sort를 쓸 수도 있지만 map이라는 편리한 기능이 있으니 이를 사용하자

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int n;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n;
	vector<vector<int>> v;
	v.resize(n);

	vector<int> line_max;

	int m = -1;
	for (int i = 0; i < n; i++) {
		int x; cin >> x; v[i].push_back(x);
		m = max(m, x);
	}
	line_max.push_back(m);

	int ans = 0;
	for (int i = 1; i < n; i++) {
		int m = -1;
		for (int j = 0; j < n; j++) {
			int x; cin >> x;
			v[i].push_back(x);
			m = max(m, x);
		}
		line_max.push_back(m);
	}

	for (int i = 1; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (v[i][j] > line_max[i - 1]) {
				cout << v[i][j] << endl;
				return 0;
			}
		}
	}


	return 0;
}