백준 18870번 python 풀이

 

문제를 처음 봤을때 '어렵지 않겠는데?' 하는 생각으로

각각의 수보다 작은 수를 찾는 무지성 반복문을 돌렸다

 

시간초과 오류가 뜰것같은 불안함이 있었는데 역시나... 시간초과

 

<초기코드>

import sys

n = int(input())

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

s = set(l)

r = [0 for i in range(n)]

for i in s:
  for j in s:
    if i > j:
      if i in l:
        r[l.index(i)] += 1

for i in range(n):
  for j in range(i+1, n):
    if l[i] == l[j]:
      r[j] = r[i]
      
print(*r)

 

글을 쓰면서 코드를 다시봤는데 생각해보니 어차피 작은 수를 찾을거면 왜 집합을 만들었나 싶다

 

시간초과 관련 내용을 찾아봤는데 저 l.index(i) 부분에서 시간복잡도가 엄청나다는 거다...

나는 원래 l과 모양이 똑같은 리스트인 r을 만들고

l의 인덱스와 같은 r의 인덱스에 작은 수의 개수를 카운트 한 값을 넣어주려고 했는데

서칭을 하다보니 너무 비효율적인 알고리즘을 짰던 것 같다...

 

서칭하다가 이해가 잘 되면서 효율적인 알고리즘 코드를 찾았다

출처: https://velog.io/@zinu/%EB%B0%B1%EC%A4%80-18870-%EC%A2%8C%ED%91%9C-%EC%95%95%EC%B6%95%ED%8C%8C%EC%9D%B4%EC%8D%AC

백준 18870 - 좌표 압축(파이썬)

 

딕셔너리를 만들어서 중복을 제거하고 오름차순으로 정렬한 리스트의 값을 넣어준 후,

리스트 만큼 반복하면서 해당 리스트의 값이 있는 딕셔너리의 인덱스를 출력하는 것이다

 

파이썬 딕셔너리는 인덱스로 접근하는 방식이 아니라 고유의 키로 접근할 수 있기에

{ '1' : a, '2' : b } 또는 { 'a' : 1, 'b' : 2} 와 같은 형태의 딕셔너리에서

각각 d[1] 또는 d[a]를 호출한다면 a 또는 1과 같은 값을 얻어낼 수 있는 것이다

 

따라서 키에는 중복제거정렬한 집합 s의 값을 넣어주고, 값에는 중복제거정렬한 집합 s의 인덱스를 넣어줌으로써

(i는 0부터 시작하기때문에 len(s)만큼 반복하면 i와 s의 인덱스 값이 일치함)

메인 리스트에서 호출할때마다 인덱스(자신보다 작은 수의 개수)가 출력되는 것이다

 

<최종코드>

import sys

n = int(input())

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

s = sorted(set(l))

d = {s[i]: i for i in range(len(s))}

for i in l:
  print(d[i], end=' ')

 

어렵다 어려워,,,, 성공!!