๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ ํ’€์ด/Greedy

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]์ฒด์œก๋ณต

by syLim___ 2023. 5. 24.
728x90

https://school.programmers.co.kr/learn/courses/30/lessons/42862

 

ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค

์ฝ”๋“œ ์ค‘์‹ฌ์˜ ๊ฐœ๋ฐœ์ž ์ฑ„์šฉ. ์Šคํƒ ๊ธฐ๋ฐ˜์˜ ํฌ์ง€์…˜ ๋งค์นญ. ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค์˜ ๊ฐœ๋ฐœ์ž ๋งž์ถคํ˜• ํ”„๋กœํ•„์„ ๋“ฑ๋กํ•˜๊ณ , ๋‚˜์™€ ๊ธฐ์ˆ  ๊ถํ•ฉ์ด ์ž˜ ๋งž๋Š” ๊ธฐ์—…๋“ค์„ ๋งค์นญ ๋ฐ›์œผ์„ธ์š”.

programmers.co.kr


๋ฌธ์ œ ์กฐ๊ฑด ์ค‘, ์ด ๋งˆ์ง€๋ง‰ ์กฐ๊ฑด๋งŒ ์ฃผ์˜ํ•˜๋ฉด ๋  ๊ฒƒ ๊ฐ™๋‹ค.

 

์—ฌ๋ฒŒ ์ฒด์œก๋ณต์„ ๊ฐ€์ ธ์˜จ ํ•™์ƒ์ด ์ฒด์œก๋ณต์„ ๋„๋‚œ๋‹นํ–ˆ์„ ๊ฒฝ์šฐ, ๋‹ค๋ฅธ ํ•™์ƒ์—๊ฒŒ ๋นŒ๋ ค์ค„ ์ˆ˜ ์—†๋‹ค.

 --> ํ•ด๋‹น ํ•™์ƒ๋“ค์„ ๋จผ์ € ์ฒ˜๋ฆฌํ•œ ๋‹ค์Œ, ๋‹ค๋ฅธ ๋„๋‚œ๋‹นํ•œ ํ•™์ƒ๋“ค์—๊ฒŒ ์ฒด์œก๋ณต์„ ๋นŒ๋ ค์ฃผ๋Š” ์ž‘์—…์„ ์ง„ํ–‰ํ•ด์•ผ ์ •๋‹ต ํŒ์ •์„ ๋ฐ›์„ ์ˆ˜ ์žˆ์—ˆ๋‹ค.


python

def solution(n, lost, reserve):
    students = [0]*(n+1) # ํ•™์ƒ ๋ฒˆํ˜ธ๋Š” 1๋ถ€ํ„ฐ ์‹œ์ž‘
    
    # ์žƒ์–ด๋ฒ„๋ฆฐ ํ•™์ƒ์ด ์—ฌ๋ฒŒ์ฒด์œก๋ณต ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ๊ฒฝ์šฐ
    for i in range(1,n+1):
        if i in lost and i in reserve:
            lost.remove(i)
            reserve.remove(i)
            
    for i in range(1,n+1):
        if i not in lost:
            students[i] = 1
        else:
            if i-1 in reserve: # ์ด์ „ ํ•™์ƒ
                reserve.remove(i-1)
                students[i] = 1
            elif i+1 in reserve: # ๋‹ค์Œ ๋ฒˆํ˜ธ ํ•™์ƒ
                reserve.remove(i+1)
                students[i] = 1
    answer = students.count(1)
    return answer
728x90