글 읽기 - 귀중한 시간 잠시 내어주시면 감사하겠습니다..

kwak2418 3년 전 0

어떤 컨셉으로 풀어나가야 할지 잘 모르겠습니다...

set도 이용해보고 map도 이용해보고 해봤는데 결국.. 마지막은 이중 반복문으로 비교를 할 수 밖에 없더라구요.. 모두 시간초과가 나왔습니다..

#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int result[1000001]={0}; //결과출력을 위한 배열

bool comp(const int &a, const int &b) //오름차순 정렬
{
    if(a<=b)
    {
      return true;
    }
   return false;
}

int main()
{
    int tc = 0;
    vector<int> v; //정렬 및 중복값 제거를 위한 벡터 
    vector<int> v1; //입력값을 기억할 벡터
    int temp=0;
    scanf("%d", &tc);
    for (int i = 0; i < tc; i++)
    {
        scanf("%d",&temp);
        v.push_back(temp);
        v1.push_back(temp);
    }
    sort(v.begin(), v.end(), comp);
    v.erase(unique(v.begin(), v.end()), v.end()); //vector 안 중복값 제거,반드시 정렬 한 뒤 사용해야함
                                                  //v.erase(a,b) -> [a,b) a이상 b 미만 원소 제거(a와 b는 vector iteraotr)
                                                  /*
unique(a,b) a와 b는 vector iterator 
vector 배열에서 중복되지 않는 원소들을 앞에서부터 채워나가는 함수이다.
algorithm 헤더에 존재한다.
중복되지 않는 원소들을 앞에서부터 채워나가는 역할을 하기때문에 남은 뒷부분은 그대로 vector 원소값이 존재한다.   
*/
  
  int count=v.size()-1;//정렬 및 중복제거를 한 벡터 길이 -1= 최솟값으로 부터 최대 거리 
  while(v.size()!=0) //정렬된 배열이 없을 때 까지 
    {
      for(int i=0;i<v1.size();i++)
      {        
          if(v.back()==v1[i]) //만약 현재 정렬된 벡터의 마지막 값과 현재카르키는 벡터의 값이 같으면
          {
            result[i]=count; // 결과 배열에 해당 위치에 count를 넣음(거리)
          }
      }
      v.pop_back(); // for문을 빠져 나오면 벡터를 뺌
      count--; //count도 감소(거리)
    } 
   for(int i=0; i<tc;i++) //출력 
     {
       printf("%d ",result[i]);
     }
    
}

nomatter2k 3년 전 1

정답인지는 모르겠는데, 저는 binary tree를 이용했습니다.

kwak2418 3년 전 0

감사합니다 참고 하겠습니다

seng1127 3년 전 0

이 코드에서는

vector v; //정렬 및 중복값 제거를 위한 벡터
vector v1; //입력값을 기억할 벡터

v에서 값을 하나 읽고 그걸 토대로 v1을 처음부터 끝까지 흝으면서 값이 같은 좌표를 압축된 좌표로 바꿔주는 방법을 사용하고 있는데요.

v1을 처음부터 끝까지 흝으면서 값이 같은지 검사하고 바꾸는 방법은 느립니다. 그래서 시간초과가 나옵니다.

반대로 생각해서, v1에서 값을 하나 읽고 그걸 토대로 v를 처음부터 끝까지 흝으면서 값이 같은것을 찾아 좌표를 바꿔주는 방법을 사용하면 어떻게 될까요?

앞의 방법과 똑같은 시간에 똑같이 느리겠죠. 하지만 v는 v1과 다르게 정렬이 되있습니다. 정렬이 되있는 데이터는 값을 찾기위해 처음부터 끝까지 흝을 필요가 없습니다.

이진탐색이라는 방법을 사용해서 값을 빠르게 찾을 수 있죠.

즉, 정렬된 데이터는 이진탐색을 통해서 값을 빠르게 찾을 수 있으므로 v1에서 값을 하나 읽고 그걸 토대로 v에서 같은 값을 찾아서 좌표를 바꿔주는 방법이 훨씬 빠릅니다.

(이진탐색은 c++ algorithm헤더에서 lower_bound 메서드를 사용하면 됩니다.)

댓글을 작성하려면 로그인해야 합니다.