코드

시간 초과

n = int(input())

coor = list(map(int, input().split()))

# 자기 자신보다 값이 작은 애들의 개수를 세라

set_coor = set(coor)

result = []

for c in coor:
    cnt = 0
    for i in set_coor:
        if c > i:
            cnt += 1
    result.append(cnt)
    
for x in result:    
    print(x, end = ' ')

dict로 시간 복잡도 성능 개선

n = int(input())

coor = list(map(int, input().split()))

# 자기 자신보다 값이 작은 애들의 개수를 세라

set_coor = list(sorted(set(coor)))

set_coor = {set_coor[x] : x for x in range(len(set_coor))}

# 새로 배운 출력법
print(*[set_coor[i] for i in coor])

문제 해설

문제를 이해하는 과정이 생각보다 헷갈렸다… 결국 요약하자면 해당 좌표값을 그 좌표값보다 작은 좌표값의 개수로 변환시켜주면 되는 문제이다.

문제에는 2가지 함정이 있다.

  1. 중복되는 좌표값에 대한 처리
    • 비교하고자 하는 좌표를 set()으로 선언하여 중복을 없애준다.
  2. 시간 초과가 발생
    • 1번 과정에서 선언한 set을 list로 바꾼 후, 다시 dictionary로 변환한다.
    • dict가 훨씬 시간 복잡도 차원에서 성능이 좋다.

나는 2번을 처음에 생각하지 않고 일단 풀어봤는데 시간 초과가 바로 떠서 dict으로 변환 후 다시 푸니 정답으로 인정됐다.

다른 분들이 어떻게 풀었나 참고하다가 결과를 출력하는 과정에서 Asterisk (*)를 사용하는 것을 보고 따라서 그렇게 구현해보았다

Asterisk 참고 블로그

댓글남기기

참고