[백준] 13414번: 수강신청 C++로 풀어보기

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

13414번: 수강신청

 

13414번 설명

생각

'처음에는 단순히 벡터에 값들 집어넣고, 중복한 값 넣으면 제거하고, 차례대로 출력하면 되는 거 아닌가?'라는 생각을 했었는데, 바로 시간초과가 떴다.

 

그래서 해시를 사용하는 unordered_set을 사용할까 고민했지만 unordered_set은 입력 순서를 보장해주지 않고 랜덤으로 출력된다는 문제를 가지고 있었다.

 

어떻게 하면 입력 순서를 보장할까 생각하던 중에, 해시를 사용하는 unordered_map을 사용하고 입력 순서를 value에 저장하고, value를 기준으로 데이터를 정렬하면 되지 않을까라는 아이디어를 떠올렸다.

 

코드

#include <bits/stdc++.h>
using namespace std;
unordered_map<string, int> m; // 만약 <int, int>로 하면 0으로 시작하는 학번을 잘 인식하지 못하게 된다.

bool cmp(pair<string, int>& a, pair<string, int>& b) { // value를 서로 비교하게 해주는 함수
	return a.second < b.second;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int k, len;
	int cnt = 0;

	cin >> k >> len;

	while (len--) { // 입력
		cnt++;
		string x;
		cin >> x;
		if (m.find(x) != m.end()) { // 이미 대기열에 들어가 있다면
			m.erase(x); // 삭제한다
		}

		m[x] = cnt; // 입력


	}
	vector<pair<string, int>> v(m.begin(), m.end()); // m을 vector로 변경
	sort(v.begin(), v.end(), cmp); // value를 기준으로 오름차순 정렬

	int prcnt = 1; // prcnt가 k보다 커지면 출력을 멈춘다
	for (auto it = v.begin(); it != v.end(); it++) {
		if (prcnt <= k) {
			cout << it->first << "\n"; // 학번 출력
			prcnt++;
		}
		else {
			break;
		}
	}
}

처음에는 예제는 잘 맞게 출력되는데 자꾸 틀렸다고 떴다.

알고 봤더니 학번을 int로 입력받으면 0으로 시작하는 학번을 인식하지 못해서 오답이 된 것이었다.

그래서 string으로 바꿔줬더니 잘 작동하였다. 이 오류를 찾는데까지 시간이 꽤 걸렸다.

 

결과

13414번 결과

정석대로 풀면 시간초과가 뜨고, 학번을 string으로 입력해줘야 인식이 되는 문제가 있다보니 시행착오가 많았다.

정답률이 왜 25%였는지 여실히 느낄 수 있었다.