문제
국민대학교에서는 매 학기 시작 전 종합정보시스템에서 수강신청을 한다. 매 수강신청마다 아주 많은 학생들이 몰려 서버에 많은 부하가 가기 때문에, 국민대학교에서는 수강신청 부하 관리 시스템을 도입하기로 결정하였다. 새로운 관리 시스템은 다음과 같은 방식으로 동작한다.
- 수강신청 버튼이 활성화 된 후, 수강신청 버튼을 조금이라도 빨리 누른 학생이 대기목록에 먼저 들어간다.
- 이미 대기열에 들어가 있는 상태에서 다시 수강신청 버튼을 누를 경우 대기목록의 맨 뒤로 밀려난다.
- 잠시 후 수강신청 버튼이 비활성화 되면, 대기목록에서 가장 앞에 있는 학생부터 자동으로 수강신청이 완료되며, 수강 가능 인원이 꽉 찰 경우 나머지 대기목록은 무시하고 수강신청을 종료한다.
위의 표는 최대 수강 가능 인원이 3명인 알고리즘 수업에 대해 6명의 학생이 수강신청을 진행한 모습이다. 버튼이 비활성화 된 후, 먼저 규칙 1을 적용하여 클릭을 2번 이상 한 학생의 중복된 대기목록을 삭제한다. 중복된 목록을 제거한 후, 맨 앞에서부터 최대 수강 가능 인원인 3명을 선정한다. 표의 맨 오른쪽에는 그 최종결과를 나타낸 모습이다. 이와 같은 방법을 이용하여 최종적으로 수강신청에 성공한 인원을 출력하는 프로그램을 작성하시오.
입력
입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 과목의 수강 가능 인원 K(1 ≤ K ≤ 100,000)와 학생들이 버튼을 클릭한 순서를 기록한 대기목록의 길이 L(1 ≤ L ≤ 500,000)이 주어진다. 두 번째 줄부터 L개의 줄에는 수강신청을 버튼을 클릭한 학생의 학번이 클릭 순서대로 주어진다. 학번은 8자리의 숫자로 이루어져 있다.
출력
출력은 표준 출력을 사용한다. 입력받은 데이터에 대해, 수강신청 관리 시스템의 규칙을 적용한 후 수강신청에 성공한 인원의 학번을 한 줄에 1개씩 출력한다.
출처
University > 국민대학교 > 2016 국민대학교 교내 경시대회 B번
- 문제의 오타를 찾은 사람: jh05013
- 데이터를 추가한 사람: kimsy96
- 문제를 만든 사람: kookmin20103324
알고리즘 분류
이번 문제도 국민대학교에서 출시한 경시대회 문제입니다!
학교에서 알고리즘 경시대회를 연다는 것이 굉장히 색다른 것 같습니다.
제가 다니던 학교는 알고리즘 테스트에 대해 크게 비중을 두지 않았다고 할까요?
혹은 교수님들께서 이러한 이벤트에는 큰 관심이 없으셨던 것 같습니다.
한편으로는 굉장히 부럽네요.
이제 5년 전에 제가 어떤 실수를 했는지 보여드릴 차례입니다!
처음에는 java 로 시도하였다가 시간 초과 폭탄을 맞이하고
C언어로 바꿔서 시도를 하였네요.
하지만, 이에 굴하지 않고 여러번의 시간 초과를 맞고 심지어 틀리기도 하고 최종적으로는 성공하였습니다.
제출 시간도 확인할 수 있었다면 좋았을텐데, 그건 기록이 안 되었네요.
제 생각에는 java로 제출한 처음 시점에서 마지막 성공 제출까지 꽤나 많은 시간을 투자했을 것으로 보입니다.
이제 시간 초과 결과를 받은 java 로 제출했던 코드 먼저 보여드리겠습니다.
import java.util.Iterator;
import java.util.Scanner;
import java.util.Vector;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
Vector<String> v = new Vector<String>();
for (int i = 0; i < m; i++) {
String str = in.next();
v.remove(str);
v.add(str);
}
Iterator<String> a = v.iterator();
for(int i = 0 ; i < n ; i++){
System.out.println(a.next());
}
}
}중복 for문이 돌아간 것도 아니지만, 일차원 탐색에서 시간 초과를 맞았다는 것은
이분 탐색으로 접근을 했어야 했나? 라는 생각을 들게 합니다.
하지만 5년 전의 저는 그런생각을 못 하고 println() 함수를 print()로 바꿔서 제출을 했네요
import java.util.Scanner;
import java.util.Vector;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
Vector<String> v = new Vector<String>();
for (int i = 0; i < m; i++) {
String str = in.next();
v.remove(str);
v.add(str);
}
for(int i = 0 ; i < n ; i++){
System.out.print(v.elementAt(i) + "\n");
}
}
}java에서 println()과 print() 함수는 아주 미세하지만 동작 방식이 달라
소요되는 시간에 차이가 있습니다.
println() 이 조금 더 시간을 소모하며, 저는 시간을 줄이기 위해서 print()를 사용하고
개행을 추가해주었네요.
하지만 앞서 말한 것 처럼 이것은 정답이 아닙니다.
5년 전의 저는 에잇. java가 안 되잖아 하고 C언어로 바꿔서 제출을 한 것 같습니다.
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
int a,b,num;
vector<int> v;
cin >> a >> b;
while(--b){
cin >> num;
for(int i = 0 ; i < v.size(); i++){
if(v.at(i) == num){
v.erase(remove(v.begin(),v.end(),num));
break;
}
}
v.push_back(num);
}
for(int i = 0 ; i < a ; i++){
cout << v.at(i) << '\n';
}
}하지만 이 역시 java를 그대로 C로 바꿔놓은 수준이었기에
시간 초과의 늪에서는 빠져나올 수 없었습니다.
그리고 자료구조를 vector를 쓰고 있는 모습이 보이는데요.
이 문제는 hash를 사용했을 경우 더 간단히 해결했을 것입니다.
이제 대망의 정답 코드를 공개하겠습니다.
#include <stdio.h>
#include <vector>
#include <unordered_map>
using namespace std;
int main()
{
int n, k;
int cnt = 0;
scanf("%d%d", &n, &k);
unordered_map<int, int>m2;
vector<pair<int, int>> snum;
for (int i = 0; i < k; i++)
{
int num;
scanf("%d", &num);
auto ret = m2.insert(pair<int, int>(num, i));
snum.push_back(pair<int, bool>(num, true));
if (!ret.second)
{
snum[m2.find(num)->second].second = false;
m2[num] = i;
}
}
for (int i = 0; i < k; i++)
{
if (snum[i].second)
{
printf("%.8d\n", snum[i].first);
cnt++;
}
if (cnt == n) break;
}
return 0;
}문제에서는 수강 신청 인원을 골라내는 문제였기에 key value와 같은 개념이 있는 자료 구조를 사용했어야 합니다.
vector에서는 사용할 수는 있지만, 오히려 복잡한 방식이기도 합니다.
위 코드에서 사용된 unordered_map 은 해쉬 테이블을 이용한 방법이라고 할 수 있으며,
자료구조에 입력된 순서대로 기록되는 vector와 달리 map 구조의 경우
자료를 정렬해 기록하는 기능을 가졌습니다.
하지만, 위 문제는 입력된 순서를 중요시하는 형태이기 때문에
정렬이 발생하지 않는 unordered_map 구조를 사용하였습니다!
이상입니다!
