[BOJ] #13414 수강신청

시간 제한	메모리 제한	정답 비율
1초	256MB	19.578%

 

13414번: 수강신청

 

문제

 

시행착오

처음에 접근을 잘못해서 열라 많이 틀림. 런타임에러도 났었고 런타임에러 잡으니 시간초과 떠서 완전 멘붕..

입력으로 들어온 학번들을 다른 배열에 저장하지 않고 단순 map으로만 풀 수 있지 않을까 싶어서 map에 {학번, 순서}를 저장했고 그 후에, key가 아닌 value로 정렬하고 싶어서 vector로 복사하고, cmp함수 사용해서 정렬하고, 출력하는 방식으로 했었다.

그런데 시간초과가 안날 것 같았는데 복사하는데 오래걸린건지.. 도대체 왜 시간초과 났는지 아직도 잘 모르겠지만 결국 전부 지우고 다시풀었는데, map을 value값으로 정렬하는 것보다 입력받았을 때 입력받은 학번들을 배열에 저장해서 배열을 이용해서 풀 수 있었다.

그리고 또 하나 어려웠던 점은 string을 쓰지 않고 int형으로 입력을 받다보니 0000000 이런 값은 0으로 인식되어서 8자리를 맞추기 위하여 출력형식을 "%08d" 이렇게 썼다. 의미는 8자리 왼쪽정렬이며 빈 공간은 0으로 채우겠다는 의미이다. %08d 형식지정자를 씀으로써 string을 입출력을 위해 사용해야하는 아래 문장들을 안써도 돼서 참 좋았다.

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

 

참고 링크 1. vector 정렬: vector cmp 함수 관련

How do I sort a vector of pairs based on the second element of the pair?

참고 링크 2. 언어별 input method 비교: cin, cout 쓸 때 위의 문장을 써야하는 이유

algospot.com :: 자유게시판: 각 언어별 input method 비교

코드 일부

bool cmp(const p& a, const p& b) {
	return a.second < b.second;
}


// 메인함수
map<int, int> m;
...
// map 복사
vector<p> v(m.begin(), m.end());
//sort(v.begin(), v.end(), cmp);

// c++14 에서는 auto를 활용하여 이렇게 정렬할 수도 있다.
sort(v.begin(), v.end(), [](auto& left, auto& right) {
		return left.second < right.second;
});

...

 

해결

key point, map을 활용해서 각 학생이 최종적으로 몇 번째로 들어왔는지 저장한다.

1. 학번을 key로, 들어온 순서를 value로 map을 구성한다.
2. 입력받은 학번은 또 다른 int배열에 순서대로 저장한다.
3. 1부터 마지막 순서까지 차례로 돌면서 i번째로 들어온 학생이 map에서 저장한 순서와 같은지 판단하여 같으면 출력하고 cnt를 증가시킨다.
4. cnt가 k와 같아지면 k명까지 모두 선정된 것이므로 반복문을 종료한다.

 

코드

메모리	시간
13312 KB	472 ms

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int k, l, arr[500005];
map<int, int> m;
int main() {
    scanf("%d %d", &k, &l);
    string s;
    for (int i = 0; i < l; i++) {
        scanf("%d", &arr[i]);
        m[arr[i]] = i;
    }
    int cnt = 0;
    for (int i = 0; i < l; i++) {
        if (cnt >= k)break;
        if (m[arr[i]] == i) {
            printf("%08d\n", arr[i]);
            cnt++;
        }
    }
    
    return 0;
}

 

후기

처음 접근을 잘못해서 큰 코 다친 문제.. 잊지 않겠어
그리고 이번 문제 또한 k대신 상수를 써서 많이 틀렸는데... 마지막 실수이길