https://www.acmicpc.net/problem/18870
18870๋ฒ: ์ขํ ์์ถ
์์ง์ ์์ N๊ฐ์ ์ขํ X1, X2, ..., XN์ด ์๋ค. ์ด ์ขํ์ ์ขํ ์์ถ์ ์ ์ฉํ๋ ค๊ณ ํ๋ค. Xi๋ฅผ ์ขํ ์์ถํ ๊ฒฐ๊ณผ X'i์ ๊ฐ์ Xi > Xj๋ฅผ ๋ง์กฑํ๋ ์๋ก ๋ค๋ฅธ ์ขํ์ ๊ฐ์์ ๊ฐ์์ผ ํ๋ค. X1, X2, ..., XN์ ์ข
www.acmicpc.net
import sys
n = int(sys.stdin.readline())
num = list(map(int, sys.stdin.readline().split()))
num_set = sorted(list(set(num)))
for i in num:
print(num_set.index(i), end=' ')
์ซ์๋ฅผ num์ผ๋ก ์ ๋ ฅ๋ฐ์ ๋ฆฌ์คํธ๋ก ๋ง๋ค๊ณ
์ค๋ณต์ ์ ๊ฑฐํ๊ณ ์ ๋ ฌํ ๋ฆฌ์คํธ๋ฅผ ํ๋ ๋ ๋ง๋ค์ด์ ๊ทธ ๋ฆฌ์คํธ์ ์ธ๋ฑ์ค๋ฅผ ์ถ๋ ฅํ๋๋ก ํ๋ค
๊ทผ๋ฐ ์๊ฐ ์ด๊ณผ๊ฐ ๋ด๋ค.... ์ธ๋ฑ์ค๋ฅผ ํ๋ํ๋ ์ฐพ๋๋ฐ ์๊ฐ์ด ์ค๋ ๊ฑธ๋ ค์ ๊ทธ๋ ๋ค๊ณ ํ๋ค
** ๋ฆฌ์คํธ.index(i) : ์๊ฐ ๋ณต์ก๋ O(n) **
import sys
n = int(sys.stdin.readline())
num = list(map(int, sys.stdin.readline().split()))
num_set = sorted(list(set(num)))
num_dic = {num_set[i] : i for i in range(len(num_set))}
for i in num:
print(num_dic[i], end=' ')
๊ทธ๋์ ๋์ ๋๋ฆฌ๋ฅผ ์ด์ฉํ๋ค
๋์ ๋๋ฆฌ๋ {key:value}๋ก ๊ฐ์ ์ ์ฅํ๋๋ฐ key๋ ์ค๋ณต ํ์ฉ X
๋์ ๋๋ฆฌ์ key๊ฐ์ num, value๊ฐ์ ๋ ์์ ์ซ์์ ๊ฐ์๋ก ๋ฃ์ด์ฃผ๊ณ num์ ๋๋ฉด์(key - num) ๊ฐ์ ์ถ๋ ฅํ๋ค!
** ๋์ ๋๋ฆฌ : ์๊ฐ ๋ณต์ก๋ O(1) **
'๐ค > ๋ฐฑ์ค' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
๋ฐฑ์ค 11047: ๋์ 0 (Python) (0) | 2021.09.25 |
---|---|
๋ฐฑ์ค 11399: ATM (Python) (0) | 2021.09.25 |
๋ฐฑ์ค 10814: ๋์ด์ ์ ๋ ฌ (Python) (0) | 2021.09.15 |
๋ฐฑ์ค 1181: ๋จ์ด ์ ๋ ฌ (Python) (0) | 2021.09.14 |
๋ฐฑ์ค 11651: ์ขํ ์ ๋ ฌํ๊ธฐ 2 (Python) (0) | 2021.09.13 |