[Python][leetcode 912. Sort an Array] Direct Address Table _ numbers

📕 문제 

https://leetcode.com/problems/sort-an-array/

Sort an Array - LeetCode

---

💡 문제 풀이

DIrect Address Table을 활용한 기본적인 문제이다. 

보통, 숫자를 bucket에 넣어서 정렬하거나 

문자를 아스키코드로 바꿔서 정렬을 하는데, 

이 문제는 숫자정렬에 해당한다. 

 

bucket 크기를 어떻게 할까 고민하다가 

처음에는 그냥 100000개로 할까 생각을 했었다. (그런데 그러면 너무 커서 시간초과가 생기니까)

list의 Max 값과 Min 값의 절댓값 중 큰 값으로 정했다

(파이썬에는 마이너스 인덱스가 존재하기 때문에 음수 버켓정렬이 가능하다)

 

음수 값을 고려 안하고 bucket을 하나로 만든 결과

 

그런데 bucket을 그냥 하나로 만들어서 돌리고 나니까 

- 1 이었던 인덱스 값이 +4 로 바뀌어서 출력되는 것을 볼 수 있다. 

이 문제를 해결하기 위해서 bucket_positive_num과 bucket_negative_num을 따로 만들었고,

bucket_negative_num에 있는 인덱스 값은 나중에 출력할때

전체 길이만큼 마이너스를 해주었다. ( i - len(bucket_negative_num))

그랬더니 문제가 잘 해결되었다.

# Bucket Sort
# 912. Sort an Array 

import math

# input 값이 정해져있음
# nums = [ 1 5 -300 -7 9 11 13 -2 ] 이런 느낌으로
# 입력 1 5 -300 -7 9 11 13 -2 등의 리스트로 받기
nums = list(map(int, input().split()))

# 파이썬은 - 인덱스도 있으므로 마이너스도 가능
# bucket의 범위를 정하는데, nums 중에서 절댓값이 가장 큰걸로 하기
Max1 = max(nums)
Min1 = min(nums)
sum1 = max(abs(Max1), abs(Min1)) + 1

# 양수 담을 그릇
bucket_positive_num = [0]*sum1
# 음수 담을 그릇
bucket_negative_num = [0]*sum1

for i in range(len(nums)):
    if nums[i] >= 0:
        num = nums[i]
        bucket_positive_num[num] += 1
    else:
        num = nums[i]
        bucket_negative_num[num] += 1
#print(bucket)

ans = []
# 먼저 음수 ans에 넣기
for i in range(len(bucket_negative_num)):
    if bucket_negative_num[i] != 0:
        for j in range(bucket_negative_num[i]):
            ans.append(i-len(bucket_negative_num))
# 양수 ans에 넣기
for i in range(len(bucket_positive_num)):
    if bucket_positive_num[i] != 0:
        for j in range(bucket_positive_num[i]):
            ans.append(i)
print(ans)

 

출력 결과

---

✔️ 느낀 점

내가 이전에 사용하던 백준, 프로그래머스, swea와 같은 플랫폼에서는 보통 input 값을 다 직접 입력 받았었다. 

그런데 leetcode에서는 처음에 이미 입력값이 들어있는 리스트 변수를 넘겨준다는 것이 다른 점이었다. 

물론 편하긴 하지만, 계속 안하다 버릇하면 인풋 입력받는 법을 까먹을까봐 걱정이 되어서 

처음에 테스트 할 때는 인풋 입력도 다 직접 받게 해서 테스트한 다음에 제출해야겠다고 생각했다. 

또, 블로그의 글도 영어로 작성하면 더 좋을 것 같다고 생각했다. 

---

💻 최종 정답

 

▷ 코드

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        # Bucket Sort
        # 912. Sort an Array 

        import math

        # input 값이 정해져있음
        # nums = [ 5, 2, 3, 1] 이런 느낌으로

        # 파이썬은 - 인덱스도 있으므로 마이너스도 가능
        # bucket의 범위를 정하는데, nums 중에서 절댓값이 가장 큰걸로 하기
        Max1 = max(nums)
        Min1 = min(nums)
        sum1 = max(abs(Max1), abs(Min1)) + 1

        # 양수 담을 그릇
        bucket_positive_num = [0]*sum1
        # 음수 담을 그릇
        bucket_negative_num = [0]*sum1

        for i in range(len(nums)):
            if nums[i] >= 0:
                num = nums[i]
                bucket_positive_num[num] += 1
            else:
                num = nums[i]
                bucket_negative_num[num] += 1
        #print(bucket)

        ans = []
        # 먼저 음수 ans에 넣기
        for i in range(len(bucket_negative_num)):
            if bucket_negative_num[i] != 0:
                for j in range(bucket_negative_num[i]):
                    ans.append(i-len(bucket_negative_num))
        # 양수 ans에 넣기
        for i in range(len(bucket_positive_num)):
            if bucket_positive_num[i] != 0:
                for j in range(bucket_positive_num[i]):
                    ans.append(i)
        return ans