๐Ÿค–/๋ฐฑ์ค€

๋ฐฑ์ค€ 18870: ์ขŒํ‘œ ์••์ถ• (Python)

sssbin 2021. 9. 15. 01:15

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) **