수강신청
2017-01-09 15:03:24 | 조회수 1311
-
유형
문제 요약
-
스택, 해쉬수강신청을 한 학번이 주어질 때, 규칙을 적용하여 최종적으로 수강신청을 한 학번을 출력하세요.
※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.
이 문제는 여러가지 자료구조와 구현, 세세한 처리까지 요구한 다소 어려운 문제였습니다.
문제에 있는 수강신청 시스템의 그림을 다시 한 번 보겠습니다.
중복으로 신청한 인원의 학번은 맨 뒤로 밀려난다는 것은 무슨 의미일까요?
이 말은 "밑에서부터 반대 방향으로 학번을 검사했을 때, 학번이 처음 나온 위치가 최종 위치"가 된다는 의미입니다.
중복으로 신청하면 가장 아래로 밀려난다 했으니, 가장 아래부터 검사했을 때 나온 위치가 최종 위치겠죠.
그렇다면 여기서 중복으로 신청을 한 것은 어떻게 체크를 할까요? 우리는 여기서 <set>, <map> 같은 트리 형태의 자료구조를 사용할 수 있습니다. 이러한 자료구조의 특징은, 삽입, 삭제, 검색에 드는 시간복잡도가 O(logn) 이라는 점입니다.
결론적으로, 최초로 등장한 학번을 set, map 등의 자료에 넣어주고, 새로운 학번을 검사할 때 이미 들어가 있는 경우 무시하면 됩니다. 그렇게하면 중복이 제거된 최종 목록을 얻을 수 있습니다. 목록을 얻은 다음, 위에서부터 수강신청 정원만큼을 출력하면 됩니다.
이 때, 사소하게 조심해야 할 점은 학번이 0으로도 시작할 수 있기 때문에 int형으로 저장할 경우 잘못된 정답이 출력될 수 있음을 유의하세요.
클릭하여 소스코드 보기
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
using namespace std;
typedef long long ll;
int main()
{
int n, k, cnt = 0;
vector<string> v, v2;
set<string> s;
scanf("%d %d", &n, &k);
for (int i = 0; i < k; i++)
{
char tmp[9];
scanf("%s", &tmp);
v.push_back(string(tmp));
}
for (int i = v.size() - 1; i >= 0; i--)
{
if (!s.count(v[i]))
{
v2.push_back(v[i]);
s.insert(v[i]);
}
}
for (int i = v2.size() - 1, j = 0; i >= 0 && j < n; i--, j++)
cout << v2[i] << "\n";
}