2022. 7. 19. 22:29ㆍ2022 땅울림 썸머코딩
입력: N
출력: N*N개의 숫자중에서 N번째로 큰 숫자를 출력하기
문제 접근방법
처음엔 표의 숫자들이 자신의 밑에있는 숫자보다 바로위에있는 숫자가 더 크다는말에 어떤 수학적 규칙이 있는지 계속 봤던 것 같다. 백준의 시간제한이나 메모리 제한에 대한 개념이 잡혀있지않아서 당연히 정렬하면 틀리겠지라고 생각하고 손도 못대고 고민만 하다가. 그냥 N*N개의 숫자를 하나하나 비교해서 N번째 숫자를 출력했다. 결과는 당연히 오답이였다. 그래서 벡터에 넣고 sort하면 퀵정렬로 해준다고하길래 무작정 벡터에 넣고 전체 sort를 해보았다. 그랬더니 메모리초과라고 나와서 이거 시간은 안넘나보네라고 생각했다. 그 다음시도했던게 자료구조 강의시간에 배운 heap정렬이였다. 하지만 이것도 메모리초과가나와서 N개를 저장하고 그 이상이 들어오면 heap의 가장 마지막 숫자를 삭제해야겠다고 생각했다.
void insert(int key) {
heapsize++;
put.push_back(key);
upheap(heapsize);
if (heapsize > maxsize) {
remove();
}
}하지만 문제는 나는 N+1개의 숫자중에 가장 작은숫자를 삭제해야 하는데 내가 구현한 heap정렬은 1~N번째까지 숫자가 완벽하게 오름차순으로 정렬이 되있지 않는것이였다. 그래서 결과가 나오지않았다.
void remove() {
put[rootindex] = put[heapsize];
sort(put.begin()+1, put.end(), greater<>());
put.pop_back();
heapsize--;
downheap(rootindex);
}그래서 각 삭제마다 정렬해서 빼보았는데 이번엔 시간초과가 나왔다. 포기할까 하던와중에 이렇게 할꺼면 그냥 벡터에 넣는거나 뭐가다를까 싶었다. 하지만 처음에 실패했었기때문에 벡터에 대해 조금 공부를 해보았는데. 벡터는 size를 초과하게 입력하면 알아서 크기를 늘린다고한다. 하지만 나는 입력값이 최대 1500*1500으로정해져있으므로 2250000크기의 벡터만 있으면 된다고 생각해서 벡터의 size를 미리 설정하고 해보면 될것같아서 해보았다.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int n;
cin >> n;
vector<int>po;
po.reserve(2250000);
for (int i = 0; i < (n * n); i++) {
int num;
cin >> num;
po.push_back(num);
}
sort(po.begin(), po.end(), greater<>());
cout << po[n - 1] << "\n";
}하지만 그래도 시간초과가 나와서 시간을 조금이라도 줄여보려고 cin.tie(NULL)과 ios_base::sync_with_stucio(false)를 붙였더니 정답이 나왔다.
느낀점: 문제를 바라볼때 한가지방면으로만 보지말고 열린생각으로 접근하면 좋을것같다고 생각했다. 그리고 너무 어렵게 생각하는것같다. stl에대해 아직 익숙하지않은데 더 익숙해져야할것같았다.
시간복잡도: 입력받을때 n*n만큼의 반복을 하므로 O(n^2)이다.