[백준] 18870번: 좌표 압축

initial

THis question is asking to calculate ranks of elements in ascending order in a list with no duplicates.

So we needa remove duplicates via set, convert it to list and we can use bisect_left to find the index where this target number is in this sorted list.

solution

import sys,bisect
input = sys.stdin.readline

n=int(input())
lst=list(map(int,input().split()))
ans = list(sorted(set(lst)))
hola = []
for i in lst:
    hola.append(bisect.bisect_left(ans,i))
print(*hola)

complexity

Time Complexity:

Let's break down the time complexity of the code:

1. Input Parsing:

   • n = int(input()): Reading a single integer, which is O(1).
   • lst = list(map(int, input().split())): Reading n integers into a list, which is O(n).

2. Removing Duplicates and Sorting:

   • ans = list(sorted(set(lst))):
     • set(lst) removes duplicates, and this takes O(n).
     • sorted(set(lst)) sorts the unique elements, and sorting takes O(n log n).
       So, this step takes O(n log n).

3. Binary Search for Each Element in the List:

   • bisect.bisect_left(ans, i) is used to find the rank of each element in the list lst.
   • Since ans is a sorted list of unique elements, the binary search (bisect_left) for each element in lst takes O(log k), where k is the number of distinct elements in lst.
   • Since there are n elements in the list lst, the total time for this loop will be O(n log k).

4. Final Output:

   • print(*hola): This prints the list of results, which takes O(n).

Overall Time Complexity:

• The dominant terms are the sorting step and the binary search step.
• O(n log n) for sorting the unique elements.
• O(n log k) for performing binary search for each element in lst.

Thus, the overall time complexity is:

O(n log n + n log k)

Where:

• n is the number of elements in the input list lst.
• k is the number of distinct elements in lst.

Since k ≤ n, the time complexity can be simplified to:

O(n log n)

Space Complexity:

1. Space for lst:

   • lst = list(map(int, input().split())): This list takes O(n) space.

2. Space for ans:

   • ans = list(sorted(set(lst))): This list contains the distinct elements from lst, and it will take O(k) space, where k is the number of distinct elements in lst.

3. Space for hola:

   • hola = []: This list stores the compressed coordinates, which will take O(n) space.

4. Auxiliary space for the sorting and binary search:

   • The sorted(set(lst)) operation creates a new sorted list, so it takes O(k) space for the distinct elements.
   • The binary search operation bisect_left uses O(1) auxiliary space for each query.

Overall Space Complexity:

The total space complexity is:

O(n + k)

Where:

• n is the size of the input list lst.
• k is the number of distinct elements in lst.

Since k ≤ n, the space complexity can be simplified to:

O(n)

Summary:

• Time Complexity: O(n log n) (because sorting is the most expensive operation).
• Space Complexity: O(n) (for storing the input list, the sorted list of distinct elements, and the result list).

This solution is efficient for large inputs (n ≤ 1,000,000).