백준 18870 파이썬

😤  헤맸던 과정

이전에 백준 7568번 덩치를 풀었던 기억이 나서 이 문제 역시도 나보다 큰게 / 혹은 작은게 몇개인지만 알면 되겠구나! 라는 생각이 들었다. 여기까지는 잘 잡았는데 중복인 경우 (ex. 100, 99, 100) 인 경우에 어떻게 해야 할지 코드를 얼렁뚱땅 짠 느낌이 있었다. 

그래도 예시로는 정답이 떴는데 이중 for 문 때문인지 시간 초과가 떴다. 

result_arr = [0]*n

#나보다 작은게 몇개인지만 알면!
for i in range(len(arr)):
    cnt=0
    for j in range(len(arr)):
        if i==j:
            continue
        if arr[i]>arr[j]:
            cnt+=1
    result_arr[i] = cnt

set_result_arr = list(set(result_arr))
set_result_arr.sort()
num_dict = {}

cnt=0
for i in range(len(set_result_arr)):
    num_dict[set_result_arr[i]] = cnt
    cnt+=1

for i in range(len(result_arr)):
    num = num_dict.get(result_arr[i])
    result_arr[i] = num

for i in range(len(result_arr)):
    print(result_arr[i],end=' ')

 

 

👼🏻 구현한 코드

 

n = int(input())
arr = list(map(int,input().split()))
new_arr = [[0,0,0]]*n
#이전 값, 새로운 값, 이전 인덱스 값

for i in range(n):
    new_arr[i] = [arr[i],0,i]

new_arr.sort()

for i in range(1,n):
    old_value = new_arr[i][0]
    new_value= new_arr[i][1]
    origin_idx = new_arr[i][2]
    #이전값과 같을 경우
    if old_value == new_arr[i-1][0]:
        new_arr[i][1] = new_arr[i-1][1]
    else:
        new_arr[i][1] = new_arr[i-1][1]+1

result_arr = [0]*n

for i in range(len(new_arr)):
    result_arr[new_arr[i][2]] = new_arr[i][1]

for i in range(len(result_arr)):
    print(result_arr[i],end=' ')

새롭게 생각해낸 방법은, 위와 같이 이중 배열을 구현하는 것이었다.

각 인덱스에 이전 값, 새로운 값, 이전 인덱스를 저장했다. 이전값이 필요한 이유는 좌표를 압축할 때 이전값과 똑같다면 같은 값으로 압축해야 하기 때문이고, 새로운 값은 압축한 값을 넣기 위해서, 이전 인덱스가 필요한 이유는 해당 코드에서는 new_arr[i][0] 즉 이전 값으로 한번 정렬을 했기 때문에 나중에 답을 출력할 때 이전 인덱스의 위치로 다시 좌표를 압축한 값을 넣어줘야 했기 때문이다.

 

이전값과 같으면 같은 압축값을 넣어주고, 다르면 하나를 더한 값을 넣어준다

 

이렇게 하면 끝!

 

💬 🤓 생각한 부분

1. 풀면서 "아닌거같은데.." "너무 구현에 치중하는거같은데.." 싶으면 답이 틀리거나 시간초과가 무조건 난다 무조건!

2. 과감하게 지우고 새로운 방식을 찾아가는 것도 필요하다