[백준 1870] 좌표 압축

[BanApp]

import sys

n = int(sys.stdin.readline())

arr = list(map(int,sys.stdin.readline().split()))

t_arr = arr.copy() #기존 arr 복사
t_arr.sort() #오름 차순 정렬

tmp = []
k = t_arr[0]
cnt = 0
for i in t_arr:
    if i == k:
        tmp.append(cnt)
    else:
        k = i
        cnt = cnt+1
        tmp.append(cnt)

key = dict(zip(t_arr,tmp)) #리스트 두개 합쳐서 Dictionary로 만들기


for i in arr:
    print(key[i],end=' ')

좌표 압축을 보고 처음엔 뭔소리인지 싶었다.
쉽게 얘기해서 기존 좌표의 순서를 망가뜨리지 않고 이 좌표가 리스트안에서 몇번째로 작은 수 인가 알려주면 되는 것이다.
처음에는 약간 위치벡터 비슷한건가 싶었는데 아니였다.
여튼 나는 기존 리스트를 망가뜨리지 않을거라서 똑같은리스트를 하나 복사해주고 그것을 오름차순 정렬시켰다.
그리고 반복문으로 cnt를 이용해서 순서를 입력해주면 된다.
원래는 딕셔너리 안쓰고 인덱스를 이용해서 만들고 싶었는데 배열안에 같은 숫자가 중복해서 존재할경우 파이썬의 index 함수는
가장 먼저 만나는 원소만 인식을 하기때문에 쓰기가 곤란하다. 그래서 결국 효율이 떨어지더라도 딕셔너리로 오름 차순으로 정렬된 t_arr을 key값으로 해당 key값이 리스트 안에서 몇번째 원소인지를 value 값으로 두었다.
반복문을 사용해서 처음에 주어졌던 arr의 값을 key값으로 주면 그에 맞는 value 값이 출력되고 정답이다!
백준에 올라와 있는 pypy3 풀이도 딕셔너리를 이용했다 카더라..
다른 언어로는 어떻게 풀릴지 궁금합니다.

[ghdcksgml1]

// 5
// 2 4 -10 4 -9

  for(int i=1;i<=N;i++){
    cin>>arr[i];
    t.push_back({arr[i],i}); //(2,1) , (4,2) , (-10,3) , (4,4) , (-9,5) 값이 들어감 ( 값, 인덱스 )
  }

  sort(t.begin(),t.end()); // 값을 기준으로 오름차순 정렬  
  // (-10,3) , (-9,5) , (2,1) , (4,2) , (4,4) 

  int tmp_idx=-1;
  int prev = 10000000;
  for(auto x: t){
      if(prev != x.first){ // 이전 값과 값이 다르면
          tmp_idx++;
      }
      t_arr[x.second] = tmp_idx;
      prev = x.first;
  }

c++ 풀이입니다! C++에서는 pair<int,int> 를 쓰면 ( x , y ) 로 값을 받을 수 있고, x는 first, y는 second로 접근할 수 있습니다.

값을 받으면서 (값, 인덱스)로 값을 받아서 값을 기준으로 오름차순 한 뒤에, 아래 foreach 구문을 돌리면
t_arr의 [1,N] 구간에 좌표압축된 값이 들어갑니당

파이썬에서는 pair을 클래스로 구현할 수 있겠네요

[BanApp]

이런 방법도 있네요 점점 사고방식이 파이썬화 되가는중..

[ghdcksgml1]

key:value 값도 틀린건 아닌데 속도는 이게 좀 더 빨라요!