https://www.acmicpc.net/problem/13414
input이 50만이기 때문에 일반적인 방법으로 해결할 수는 없습니다.
해결 알고리즘은! 해쉬!
문제 해결 절차는
1. 인풋을 다받는다!
왜 다받고 시작하느냐!!!!!이게 더빠릅니다.. 인풋이 크면클수록 더 빠릅니다.
내부캐쉬?? 정확히는 잘모르는데 그렇대요...
2. 해쉬테이블에 인풋 데이터가 존재하는지 검사한다.
3. 2에서 존재한다면 해쉬테이블에 있는 인덱스를 갱신하고 갱신 전의 인덱스를 리턴한다.(해쉬테이블<pair<int, int> > = 학번(문자열로도 가능)과 인덱스)
4. 3에서 리턴 받은 인덱스의 데이터를 -1(문자열이라면 "")으로 만들어준다.
5. 2에서 존재하지않으면 그냥 해쉬에 추가한다.
6. 1~5를 반복하고 끝나면 K만큼 출력한다.
cout.width(숫자) : 출력의 폭을 숫자로 하겠다.
cout.fill(문자 혹은 숫자) : 위에서 정한 폭이 안찼다면 문자 혹은 숫자로 가득 채우겠다.
아래는 코드입니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | #include <cstdio> #include <cstdlib> #include <cmath> #include <string.h> #include <queue> #include <iostream> #include <algorithm> #include <vector> #include <functional> #include <stack> #include <string> #define ll long long #define INF 0x7fffffff #define MOD 10000 #define MAX_SIZE 10000 #define mp make_pair #define pii pair<int, int> using namespace std; vector<pair<int, int> > myHash[MAX_SIZE]; int snum[500000]; int toNum(int a) { return a % MOD; } int f(int a, int idx) { int num = toNum(a); for (int i = 0; i < myHash[num].size(); i++) { if (myHash[num][i].first == a) { int tmp = myHash[num][i].second; myHash[num][i].second = idx; return tmp; } } myHash[num].push_back(mp(a, idx)); return -1; } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, k; cin >> n >> k; for (int j = 0; j < k; j++) { cin >> snum[j]; } for (int j = 0; j < k; j++) { int tmp = f(snum[j], j); if (tmp != -1) snum[tmp] = 0; } int cnt = 0; for (int j = 0; j < k; j++) { if (snum[j] != 0) { cout.width(8); cout.fill('0'); // 채움 문자는 '0' cout << snum[j] << '\n'; cnt++; if (cnt == n) break; } } return 0; } | cs |