개발하는데 다 이유가 있겠지

[Silver II] 좌표 압축 - 18870

문제 링크

성능 요약

메모리: 143268 KB, 시간: 1768 ms

분류

값 / 좌표 압축, 정렬

제출 일자

2024년 2월 23일 12:03:12

문제 설명

수직선 위에 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을 공백 한 칸으로 구분해서 출력한다.

import sys
input = sys.stdin.readline


def solution():
    N = int(input())
    num_list = list(map(int, input().split()))
    set_list = sorted(list(set(num_list)))
    dic = {}

    # 오름차순으로 정렬 및 중복제거가 됐기 때문에 i는 자신보다 작은 수의 개수랑 같다.
    for i in range(0, len(set_list)):
        dic[set_list[i]] = i

    # nun_list에서 한개씩 key값으로 검색 후 출력
    for j in num_list:
        print(dic[j])

solution()

---

시간초과 코드

이중 반복문을 사용하여 시간 복잡도가 O(n^2) 매우 비효율적

import sys
input = sys.stdin.readline


def solution():
    N = int(input())
    num_list = list(map(int, input().split()))
    set_list = list(set(num_list))
    count_list = [0]*N

    for i in range(0, N):
        for j in range(0, len(set_list)):
            if num_list[i] > set_list[j]:
                count_list[i] += 1

    # 리스트 원소나 문자열 각각의 문자를 한 칸 씩 띄운 후(공백) 출력
    print(*count_list)


solution()

---

딕셔너리 자료형(Dictionary)

딕셔너리는 단어 그대로 ‘사전’이라는 뜻이다. 즉 "people"이라는 단어에 "사람", "baseball"이라는 단어에 "야구"라는 뜻이 부합되듯이 딕셔너리는 Key와 Value를 한 쌍으로 가지는 자료형이다.

딕셔너리는 리스트나 튜플처럼 순차적으로(sequential) 해당 요솟값을 구하지 않고 Key를 통해 Value를 얻는다. 이것이 바로 딕셔너리의 가장 큰 특징이다. baseball이라는 단어의 뜻을 찾기 위해 사전의 내용을 순차적으로 모두 검색하는 것이 아니라 baseball이라는 단어가 있는 곳만 펼쳐 보는 것이다.

사용 방법

다음은 딕셔너리의 기본 모습이다.

{Key1: Value1, Key2: Value2, Key3: Value3, ...}

Key와 Value의 쌍 여러 개가 {}로 둘러싸여 있다. 각각의 요소는 Key: Value 형태로 이루어져 있고 쉼표(,)로 구분되어 있다.

>>> dic = {'name': 'pey', 'phone': '010-9999-1234', 'birth': '1118'}

위에서 Key는 각각 'name', 'phone', 'birth', 각각의 Key에 해당하는 Value는 'pey', '010-9999-1234', '1118'이 된다.

---

딕셔너리 쌍 추가하기

>>> a = {1: 'a'}
>>> a[2] = 'b'
>>> a
{1: 'a', 2: 'b'}

 

{1: 'a'} 딕셔너리에 a[2] = 'b'와 같이 입력하면 딕셔너리 a에 Key와 Value가 각각 2와 'b'인 {2: 'b'} 딕셔너리 쌍이 추가된다.

>>> a['name'] = 'pey'
>>> a
{1: 'a', 2: 'b', 'name': 'pey'}

딕셔너리 a에 {'name': 'pey'} 쌍이 추가되었다.

>>> a[3] = [1, 2, 3]
>>> a
{1: 'a', 2: 'b', 'name': 'pey', 3: [1, 2, 3]}

Key는 3, Value는 [1, 2, 3]을 가지는 한 쌍이 또 추가되었다.

---

딕셔너리 요소 삭제하기

>>> del a[1]
>>> a
{2: 'b', 'name': 'pey', 3: [1, 2, 3]}

위 예제는 딕셔너리 요소를 지우는 방법을 보여 준다. del 함수를 사용해서 del a[key]를 입력하면 지정한 Key에 해당하는 {Key: Value} 쌍이 삭제된다.

---

딕셔너리 함수

• keys() : 딕셔너리의 key만 모아서 반환함 (리스트와 비슷하지만 append, insert, pop, remove, sort 함수는 수행할 수 없음)
• values() : 딕셔너리의 value만 모아서 반환함
• items() : key와 value의 쌍을 튜플로 묶은 값을 반환
• clear() : 딕셔너리의 모든 요소를 삭제
• get() : key에 대응되는 value를 반환함(없다면 None을 반환)

딕셔너리 자료형(Dictionary) - Python