[백준 18870번] 좌표 압축 (C++ / Python)

아이디어

vector에 3개의 값을 유지한다. v(입력값, 기존 index, 정렬후 index).

1. 입력을 다 받고 입력값 기준으로 sort를 실시 한 뒤

2. 각 entry들이 몇번째 숫자인지 순서를 매긴 후 (정렬 후index)

3. 기존 index를 기준으로 원상 복구 시켜서 정렬 후 index를 출력한다.

 

C++ 풀이

#include <bits/stdc++.h>

using namespace std;
vector<pair<int,pair<int,int>>> v;
bool compare(pair<int,pair<int,int>>& a, pair<int,pair<int,int>>& b)
{
    return a.second.first < b.second.first;
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin>> N;
    for(int i = 0 ; i< N; i++)
    {
        int tmp;
        cin >> tmp;
        v.push_back({tmp,{i,0}}); //v(입력값, 기존 index, 정렬후 index)
    }
    sort(v.begin(), v.end());
    int prev = v[0].first;
    v[0].second.second =0;
    for(int i = 1; i< N; i++)
    {
        if(v[i].first != prev) // 다른게 나오면
        {
            v[i].second.second = v[i-1].second.second+1; //1을 증가시켜 넣고
        }else{ //같은게 나오면
            v[i].second.second = v[i-1].second.second; // 그대로 넣어라.
        }
        prev = v[i].first;
    }
    sort(v.begin(), v.end(), compare);

    for(int i = 0 ; i< N; i++)
    {
        cout << v[i].second.second << " " ;
    }

}

 

Python 풀이

흠.. C++과 같은 로직으로 풀긴했는데 시간이 너무 오래 걸리더라.

다른사람들 2000ms대로 풀이 하길레 봤더니, dictionary사용해서 나도 풀어봤다.

4840ms 짜리 풀이

import sys
input = sys.stdin.readline

N = int(input().rstrip())

sort_list = map(int,input().rstrip().split())
use_list = []
index_dp = [0]*(N+1)
for i, value in enumerate(sort_list): #인덱스 번호를 저장하기 위해서.
    use_list.append([value,i])

use_list.sort() #value순으로 오름차순 정렬
cnt = 0
prev = use_list[0][0]

#따로 기존 index대로 정렬 다시 하지 않고,
#다른 list에다가 저장.
for l in use_list:
    if prev != l[0]:
        cnt += 1
        index_dp[l[1]] = cnt
    else :
        index_dp[l[1]] = cnt
    prev = l[0]

for i in range(N):
    print(index_dp[i], end =" ") 

 

2000ms 짜리 풀이

import sys
input = sys.stdin.readline

N = int(input().rstrip())
l = list(map(int,input().rstrip().split()))

#set 해서 unique하게 만들고
uni = list(set(l))

#정렬하고
uni.sort()

d = {}
#index를 dictionary에 저장.
for i, value in enumerate(uni):
    d[value] = i

#dictionary에는 해당 숫자의 순서가 저장되어있음.
for v in l:
    print(d[v], end = " ")