๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
Algorithm/๋ฐฑ์ค€(BOJ)

[ ํŒŒ์ด์ฌ(python) ] ๋ฐฑ์ค€ 1966 - ํ”„๋ฆฐํ„ฐ ํ

by YWTechIT 2021. 6. 24.
728x90

๐Ÿ“ ๋ฐฑ์ค€ 1966 - ํ”„๋ฆฐํ„ฐ ํ

๋ฐฑ์ค€ 1966 - ํ”„๋ฆฐํ„ฐ ํ


โšก๏ธ ๋‚˜์˜ ํ’€์ด

๋ฌธ์ œ๊ฐ€ ์ž˜ ์ดํ•ด๊ฐ€ ๋˜์ง€ ์•Š์•„ 4 ~ 5๋ฒˆ ์ •๋„ ๋‹ค์‹œ ๋ดค๋‹ค. ๊ฒฐ๋ก ์ ์œผ๋กœ ํ˜„์žฌ index์™€ ๋™์ผํ•œ ์šฐ์„ ์ˆœ์œ„๊ฐ’์ด ์ œ์ผ ํด ๋•Œ cnt+=1์„ ํ•ด์ฃผ๋ฉด ๋œ๋‹ค. ๋‹ค๋ฅธ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋Š” ๊ดœ์ฐฎ์•˜๋Š”๋ฐ ์ค‘๋ณต๋œ ์šฐ์„ ์ˆœ์œ„๊ฐ€ ์žˆ๋Š” ๋ฌธ์„œ๋ฅผ ์ฒ˜๋ฆฌํ•  ๋•Œ ๊ณ ๋ฏผ์„ ๋งŽ์ด ํ–ˆ๋‹ค. ์˜ˆ์ œ ์ž…๋ ฅ 1 - ํ…Œ์ŠคํŠธ์ผ€์ด์Šค ์ค‘ ์ œ์ผ ๋งˆ์ง€๋ง‰ 1, 1, 9, 1, 1, 1์„ ์˜ˆ๋กœ ๋“ค์–ด๋ณด์ž.  (๊ทธ๋ฆผ, ๊ธ€์”จ ์–‘ํ•ด ๋ถ€ํƒ๋“œ๋ฆฝ์๋‹ˆ๋‹ค.)

 

  1. ์ž์‹ ๋ณด๋‹ค ๋†’์€ ์šฐ์„ ์ˆœ์œ„๊ฐ€ ์—†์„ ๋•Œ๊นŒ์ง€ ํšŒ์ „ํ•œ๋‹ค.(์ด๋•Œ๋Š” cnt๊ฐ€ ์˜ฌ๋ผ๊ฐ€์ง€ ์•Š๋Š”๋‹ค. why? ์ธ์‡„๋ฅผ ํ•˜์ง€ ์•Š์•˜๊ธฐ ๋•Œ๋ฌธ)
  2. pop ํ•  ์œ„์น˜(๊ฐ€์žฅ ์ฒซ ๋ฒˆ์งธ index)์— ์œ„์น˜ํ–ˆ์„ ๋•Œ ํ•ด๋‹น ๊ฐ’์˜ ์šฐ์„ ์ˆœ์œ„๊ฐ€ ์ œ์ผ ๋†’๋‹ค๋ฉด pop์ฒ˜๋ฆฌํ•˜๊ณ  cnt+=1 ํ•ด์ค€๋‹ค.
  3. 2๋ฒˆ ๊ณผ์ •์—์„œ ๋งŒ์•ฝ, pop ๊ฐ’์ด ๋‚ด๊ฐ€ ์ฐพ๊ณ  ์žˆ๋Š” target์ด๋ฉด, ํ•ด๋‹น cnt๋ฅผ ์ถœ๋ ฅํ•˜๊ณ  ๋ฐ˜๋ณต๋ฌธ์„ ์ข…๋ฃŒ(break)ํ•œ๋‹ค.

 

์—ฌ๋‹ด์œผ๋กœ python - import PriorityQueue ๋ฐฉ๋ฒ•์œผ๋กœ ์ ‘๊ทผํ–ˆ๋Š”๋ฐ ํ’€์ง€ ๋ชปํ–ˆ๋Š”๋ฐ ์ด์œ ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

 

  1. PriorityQueue ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๋Š” ๊ฐ€์žฅ ๋‚ฎ์€ ๊ฐ’๋ถ€ํ„ฐ ์ถœ๋ ฅํ•œ๋‹ค. (์ด๋Š” ์šฐ์„ ์ˆœ์œ„ * -1์œผ๋กœ ํ•ด๊ฒฐํ–ˆ๋‹ค.)
  2. PriorityQueue ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๋Š” ์šฐ์„ ์ˆœ์œ„๊ฐ€ ๋™์ผํ•  ๋•Œ ์‚ฝ์ž… ์ˆœ์„œ์— ๋”ฐ๋ผ ์š”์†Œ๊ฐ€ ๋ฐ˜ํ™˜๋œ๋‹ค.(์ด ๋ถ€๋ถ„์„ ํ•ด๊ฒฐํ•˜์ง€ ๋ชปํ–ˆ๋Š”๋ฐ, ํ”„๋ฆฐํ„ฐ ํ ๋ฌธ์ œ๋Š” index๊ฐ€ ๋™์ผํ•  ๋•Œ ์‚ฝ์ž…์ˆœ์„œ๊ฐ€ ์•„๋‹Œ ํ˜„์žฌ queue ์— ๋“ค์–ด์žˆ๋Š” ๊ฐ’ ๊ทธ๋Œ€๋กœ ์ถœ๋ ฅ์„ ํ•ด์•ผ ํ•œ๋‹ค. ์—ฌ๊ธฐ์„œ ๋” ์ข‹์€ ์ ‘๊ทผ๋ฒ•์ด ์žˆ๋‹ค๋ฉด ๋Œ“๊ธ€๋กœ ์•Œ๋ ค์ฃผ์‹œ๋ฉด ๊ฐ์‚ฌํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. ๐Ÿ˜€ ๐Ÿ˜€)
T = int(input())

for _ in range(T):
    n, m = map(int, input().split())
    priority = list(map(int, input().split()))
    index = [i for i in range(n)]
    index[m] = 'target'    # ๋‚ด๊ฐ€ ์ฐพ๊ณ  ์‹ถ์€ index
    cnt = 0

    while priority:
        if priority[0] == max(priority):    # ๋‚˜๋จธ์ง€ ๋ฌธ์„œ๋“ค๋ณด๋‹ค ์ค‘์š”๋„๊ฐ€ ๋” ๋†’์€ ๋ฌธ์„œ๊ฐ€ ์—†๋‹ค๋ฉด
            cnt += 1
            if index[0] == 'target':
                print(cnt)
                break
            priority.pop(0)
            index.pop(0)
        else:
            priority.append(priority.pop(0))
            index.append(index.pop(0))
๋ฐ˜์‘ํ˜•

๋Œ“๊ธ€