백준 알고리즘 No.18870 좌표 압축

in Study #Algorithm #Python

문제

수직선 위에 N개의 좌표 X1, X2, …, XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X’i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.

X1, X2, …, XN에 좌표 압축을 적용한 결과 X’1, X’2, …, X’N를 출력해보자.

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, …, XN이 주어진다.

출력

첫째 줄에 X’1, X’2, …, X’N을 공백 한 칸으로 구분해서 출력한다.



체감 난이도: ★★

문제를 푸는 것은 어렵지 않았지만 시간 초과의 원인을 찾아 해결하는 것이 어려웠다.

Code

n = int(input())
x_list = list(map(int, input().split()))
x_set = sorted(set(x_list))

dictionary = {x_set[i] : i for i in range(len(x_set))}

for key in x_list:
    print(dictionary[key], end = ' ')

Solution

  • 처음 시도했던 코드 (시간초과)
n = int(input())
x_list = list(map(int, input().split()))

def compress(num):
    return sum(1 for x in x_list if x < x_list[num])

compress_list = [compress(j) for j in range(n)]

print(*compress_list)
  • 리스트의 시간복잡도에 대한 고려를 하지 않아 시간초과가 났던 것 같다.
  • 그래서 딕셔너리를 사용하는 방식으로 코드를 수정하였다.
  • 또한 set()과 sorted()를 활용하여 중복 작업을 하지 않도록 수정하였다.

✔ List vs Dictionary

1️⃣ 목적
  • 리스트 (List)
    • 순서가 있는 데이터의 집합으로, 각 원소는 인덱스를 가지고 있음
    • 원소의 순서가 중요하며, 인덱스를 사용하여 각 원소에 접근
  • 딕셔너리 (Dictionary)
    • 키-값 쌍의 순서가 없는 데이터의 집합으로, 각 원소는 고유한 키(key)를 가지고 있음
    • 순서는 중요하지 않으며, 키를 사용하여 값을 저장하고 조회
2️⃣ 저장 방식
  • 리스트 (List)
    • 원소들이 인덱스를 가지고 선형적으로 저장
    • 연속된 메모리 공간에 저장되므로 인덱스를 사용하여 특정 위치의 원소에 접근 가능
  • 딕셔너리 (Dictionary)
    • 해시 테이블(hash table)이라는 구조 사용
    • 키를 해싱하여 해당 키의 위치를 계산하고, 이 위치에 값을 저장
3️⃣ 사용법
  • 리스트 (List)
    • 대괄호 [ ] 로 생성
    • append(), pop(), insert() 등의 메소드를 통해 원소 조작
  • 딕셔너리 (Dictionary)
    • 중괄호 { } 로 생성
    • keys(), values(), items() 등의 메소드를 통해 키나 값에 접근
4️⃣ 특징
  • 리스트 (List)
    • 중복된 값을 가질 수 있고, 순서가 있으므로 인덱스를 통한 순차적인 접근이 가능
    • 삽입, 삭제의 경우 모든 원소를 체크해야 하므로 딕셔너리보다 시간이 오래 걸림
    • 평균 시간 복잡도: O(n)
  • 딕셔너리 (Dictionary)
    • 키는 고유해야 하며, 키를 통해 값에 빠르게 접근 가능
    • 딕셔너리의 크기가 매우 클 때에도 키를 사용한 조회, 삽입, 삭제의 성능이 뛰어남
    • 평균 시간 복잡도: O(1)


혹시 더 좋은 알고리즘 풀이가 있다면 언제든 댓글로 알려주세요 😃