๋กœ์ผ“๐Ÿพ
article thumbnail
[Python] collections ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ deque, Counter
... 2021. 2. 21. 21:22

ํŒŒ์ด์ฌ์˜ collections ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๋Š” ์œ ์šฉํ•œ ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ์ œ๊ณตํ•˜๋Š” ํ‘œ์ค€ ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ์ž…๋‹ˆ๋‹ค. ๊ทธ ์ค‘ ๋งŽ์ด ์‚ฌ์šฉ๋˜๋Š” deque์™€ Counter์— ๋Œ€ํ•ด ์•Œ์•„๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค. ํŒŒ์ด์ฌ์—์„œ ํ๋ฅผ ๊ตฌํ˜„ํ•˜๋Š”๋ฐ ์žˆ์–ด Queue๋ผ๋Š” ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๊ฐ€ ์žˆ์ง€๋งŒ ์ผ๋ฐ˜์ ์ธ ํ๋ฅผ ๊ตฌํ˜„ํ•˜๋Š” ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๋Š” ์•„๋‹™๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ deque๋ฅผ ์ด์šฉํ•˜์—ฌ ํ ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ๊ตฌํ˜„ํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ์ผ๋ฐ˜์ ์œผ๋กœ ๋ฆฌ์ŠคํŠธ ๊ฐ€์žฅ์•ž์— ์›์†Œ๋ฅผ ์‚ฝ์ž…ํ• ๋•Œ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” O(N)์ž…๋‹ˆ๋‹ค. ํ•˜์ง€๋งŒ deque์˜ appendleft()๋ฅผ ์‚ฌ์šฉํ•˜๋ฉด ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ O(1)๋กœ ์ค„์ผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋ฆฌ์ŠคํŠธ deque ๊ฐ€์žฅ ์•ž์ชฝ์— ์›์†Œ ์ถ”๊ฐ€(appendleft(x)) O(N) O(1) ๊ฐ€์žฅ ๋’ค์ชฝ์— ์›์†Œ ์ถ”๊ฐ€(append(x)) O(1) O(1) ๊ฐ€์žฅ ์•ž์ชฝ์— ์žˆ๋Š” ์›์†Œ ์ œ๊ฑฐ(leftpop()) O(N) ..

profile on loading

Loading...