아주 단순하게 생각해서, 현재까지 송신은 했지만, 수신 시키지 못한 탑들을 Vector 로 유지, 관리하고
뒤에서부터 차례차례 앞으로 오면서 처리하면 최악의 경우 N 제곱이지만, 평균적으로는 N 제곱보다는 훨씬 빠르게 될것이다.
라고 기대하고 코딩을 시작하였다. 됬다면 해피엔딩 이었겠지만 N^2 은 타임 리밋 이었다.
#include <stdio.h>
#include <vector>
unsigned int height[5000001];
unsigned int result[5000001];
typedef std::pair<int, int> par;
std::vector<par> vec;
std::vector<par>::iterator chase;
// 높이 , 위치 - 1
int N;
void check(int height,int location);
int main() {
scanf("%d", &N);
int a;
for (a = 0; a < N; a++) {
scanf("%d", &height[a]);
}
vec.push_back(par(height[N - 1], N - 1));
for (a = N - 2; a >= 0; a--) {
check(height[a],a);
vec.push_back(par(height[a], a));
}
for (chase = vec.begin(); chase != vec.end(); chase++) {
result[chase->second] = 0;
}
for (a = 0; a < N; a++) {
printf("%d ", result[a]);
}
}
void check(int height, int location) {
for (chase = vec.begin(); chase != vec.end(); ) {
if (chase->first <= height) {
result[chase->second] = location+1;
chase = vec.erase(chase);
}
else
chase++;
}
}
타임 리밋이 걸리는 영 좋지 않은 코딩이었다....
생각을 뒤집어 보았다. 일단 기본적으로 입력을 쭉 받으면 여기서 이미 N 만큼의 시간을 소모하게 된다.
어차피 송신 수신이 일어나는 것은 자기자신과 그 앞에대해서 수행하는 것이다.
그렇다면 입력을 받으면서 처리를 할수 있을 것 같다. 라는 것까진 도달했다. 항상 여기까진 쉽게 도달하지
그런데 문제는 송신을하는 탑에서 가까운것부터 탐색을 해야하는데....이렇게 하면 또 N제곱인데 ?
그리고 이번 스터디 하던 주제를생각했다. 스택과 큐 이번경우 가장 최근 들어온것 ( 송신탑에서 가까운것) 부터 하나하나
체크하는 것이므로 스택을 써야겠구나. 라는 생각이 들고는 무릎을 탁 쳤다. 스택을 STL로 하니 코드길이는 절반으로 속도는 더욱 빠르게 되서 아슬아슬하게 0.2 MS 차이로 통과하였다. 자랑스럽다
#include <stdio.h>
#include <vector>
unsigned int height[5000001];
unsigned int result[5000001];
typedef std::pair<int, int> par;
std::vector<par> vec;
std::vector<par>::iterator chase;
// 높이 , 위치 - 1
int N;
void check(int height,int location);
int main() {
scanf("%d", &N);
int a;
for (a = 0; a < N; a++) {
scanf("%d", &height[a]);
}
vec.push_back(par(height[N - 1], N - 1));
for (a = N - 2; a >= 0; a--) {
check(height[a],a);
vec.push_back(par(height[a], a));
}
for (chase = vec.begin(); chase != vec.end(); chase++) {
result[chase->second] = 0;
}
for (a = 0; a < N; a++) {
printf("%d ", result[a]);
}
}
void check(int height, int location) {
for (chase = vec.begin(); chase != vec.end(); ) {
if (chase->first <= height) {
result[chase->second] = location+1;
chase = vec.erase(chase);
}
else
chase++;
}
}
