Algorithm/Programmers

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ์ฒด์œก๋ณต /ํŒŒ์ด์ฌ /Python

728x90
๋ฐ˜์‘ํ˜•

๐Ÿ’กsolutions )

โœ… ์ฒด์œก๋ณต ํ˜„ํ™ฉ์„ ๋ณด์—ฌ์ฃผ๋Š” students ๋ฆฌ์ŠคํŠธ๋ฅผ ๋งŒ๋“ค์–ด ๋†“์Œ, ์ฒด์œก๋ณต ์žˆ๋Š” ๊ฒฝ์šฐ 1 ์—†๋Š” ๊ฒฝ์šฐ 0์œผ๋กœ ํ‘œ์‹œ

โœ… ์ฒด์œก๋ณต ์—ฌ๋ถ„์„ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ํ•™์ƒ์ด ์ฒด์œก๋ณต์„ ์žƒ์–ด ๋ฒ„๋ฆฐ ๊ฒฝ์šฐ -> lost, reserve ๋ฐฐ์—ด์—์„œ ๋ชจ๋‘ ์ œ๊ฑฐ (์ฆ‰, ์—ฌ๋ถ„์˜ ์ฒด์œก๋ณต ๋ณธ์ธ์ด ๊ฐ€์ง)

โœ… reserve ๋ฆฌ์ŠคํŠธ๋ฅผ ๋ฐ˜๋ณต๋ฌธ ๋Œ๋ฆฌ๋ฉฐ ์—ฌ๋ถ„์˜ ์ฒด์œก๋ณต์„ ๋‚˜๋ˆ ์คŒ

โœ… ์ธ๋ฑ์Šค ๋ฒ”์œ„๋ฅผ ๋„˜์–ด๊ฐ€๋Š” ์ง€ ํ™•์ธํ•˜๋Š”๋ฐ ์ค‘๋ณต ๋ฐฉ์ง€๋ฅผ ์œ„ํ•ด continue ๋‹ฌ์•„์ฃผ๊ธฐ

  - ์ธ๋ฑ์Šค 1์ธ ๊ฒฝ์šฐ์—๋Š” 2๋ฒˆ์งธ ํ•™์ƒ๋งŒ ์ฒดํฌ

  - ์ธ๋ฑ์Šค n์ธ ๊ฒฝ์šฐ(๋๊ฐ’) n-1๋ฒˆ์งธ ํ•™์ƒ๋งŒ ์ฒดํฌ

โœ… ๋ฒ”์œ„ ๋ฒ—์–ด๋‚˜์ง€ ์•Š์€ ๊ฒฝ์šฐ์—๋Š” i ๊ธฐ์ค€์œผ๋กœ ์•ž์˜ ํ•™์ƒ ๋จผ์ € ์ฒดํฌํ•œ ํ›„ -> ๋’ค์˜ ํ•™์ƒ ์ˆœ์œผ๋กœ ํ™•์ธํ•˜๊ธฐ. ์ค‘๋ณต ๋ฐฉ์ง€๋ฅผ ์œ„ํ•ด ์ˆœ์„œ๋Œ€๋กœ ์ฒดํฌํ•˜๊ณ  continue ์กฐ๊ฑด ๋„ฃ์–ด์ฃผ๊ธฐ

 

๐ŸŽซcode )

def solution(n, lost, reserve):
    students = [1] * (n + 1)
    students[0] = 0
    tmp = []

    for i in lost:
        students[i] = 0
        if i in reserve:
            students[i] = 1
            tmp.append(i)

    for i in tmp:
        lost.remove(i)
        reserve.remove(i)

    for i in reserve:
        if i - 1 == 0:
            if students[i + 1] == 0:
                students[i + 1] = 1
            continue
        if i + 1 == n + 1:
            if students[i - 1] == 0:
                students[i - 1] = 1
            continue
        if students[i - 1] == 0:
            students[i - 1] = 1
            continue
        if students[i + 1] == 0:
            students[i + 1] = 1
            continue
            
    return sum(students)

 

๐Ÿ“Œ description )

๋ฌธ์ œ์ถœ์ฒ˜ : https://programmers.co.kr/learn/courses/30/lessons/42862?language=python3

 

์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ์ฒด์œก๋ณต

์ ์‹ฌ์‹œ๊ฐ„์— ๋„๋‘‘์ด ๋“ค์–ด, ์ผ๋ถ€ ํ•™์ƒ์ด ์ฒด์œก๋ณต์„ ๋„๋‚œ๋‹นํ–ˆ์Šต๋‹ˆ๋‹ค. ๋‹คํ–‰ํžˆ ์—ฌ๋ฒŒ ์ฒด์œก๋ณต์ด ์žˆ๋Š” ํ•™์ƒ์ด ์ด๋“ค์—๊ฒŒ ์ฒด์œก๋ณต์„ ๋นŒ๋ ค์ฃผ๋ ค ํ•ฉ๋‹ˆ๋‹ค. ํ•™์ƒ๋“ค์˜ ๋ฒˆํ˜ธ๋Š” ์ฒด๊ฒฉ ์ˆœ์œผ๋กœ ๋งค๊ฒจ์ ธ ์žˆ์–ด, ๋ฐ”๋กœ ์•ž๋ฒˆ๏ฟฝ

programmers.co.kr

๋ฌธ์ œ ์„ค๋ช…

์ ์‹ฌ์‹œ๊ฐ„์— ๋„๋‘‘์ด ๋“ค์–ด, ์ผ๋ถ€ ํ•™์ƒ์ด ์ฒด์œก๋ณต์„ ๋„๋‚œ๋‹นํ–ˆ์Šต๋‹ˆ๋‹ค. ๋‹คํ–‰ํžˆ ์—ฌ๋ฒŒ ์ฒด์œก๋ณต์ด ์žˆ๋Š” ํ•™์ƒ์ด ์ด๋“ค์—๊ฒŒ ์ฒด์œก๋ณต์„ ๋นŒ๋ ค์ฃผ๋ ค ํ•ฉ๋‹ˆ๋‹ค. ํ•™์ƒ๋“ค์˜ ๋ฒˆํ˜ธ๋Š” ์ฒด๊ฒฉ ์ˆœ์œผ๋กœ ๋งค๊ฒจ์ ธ ์žˆ์–ด, ๋ฐ”๋กœ ์•ž๋ฒˆํ˜ธ์˜ ํ•™์ƒ์ด๋‚˜ ๋ฐ”๋กœ ๋’ท๋ฒˆํ˜ธ์˜ ํ•™์ƒ์—๊ฒŒ๋งŒ ์ฒด์œก๋ณต์„ ๋นŒ๋ ค์ค„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, 4๋ฒˆ ํ•™์ƒ์€ 3๋ฒˆ ํ•™์ƒ์ด๋‚˜ 5๋ฒˆ ํ•™์ƒ์—๊ฒŒ๋งŒ ์ฒด์œก๋ณต์„ ๋นŒ๋ ค์ค„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ฒด์œก๋ณต์ด ์—†์œผ๋ฉด ์ˆ˜์—…์„ ๋“ค์„ ์ˆ˜ ์—†๊ธฐ ๋•Œ๋ฌธ์— ์ฒด์œก๋ณต์„ ์ ์ ˆํžˆ ๋นŒ๋ ค ์ตœ๋Œ€ํ•œ ๋งŽ์€ ํ•™์ƒ์ด ์ฒด์œก์ˆ˜์—…์„ ๋“ค์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.

์ „์ฒด ํ•™์ƒ์˜ ์ˆ˜ n, ์ฒด์œก๋ณต์„ ๋„๋‚œ๋‹นํ•œ ํ•™์ƒ๋“ค์˜ ๋ฒˆํ˜ธ๊ฐ€ ๋‹ด๊ธด ๋ฐฐ์—ด lost, ์—ฌ๋ฒŒ์˜ ์ฒด์œก๋ณต์„ ๊ฐ€์ ธ์˜จ ํ•™์ƒ๋“ค์˜ ๋ฒˆํ˜ธ๊ฐ€ ๋‹ด๊ธด ๋ฐฐ์—ด reserve๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ์ฒด์œก์ˆ˜์—…์„ ๋“ค์„ ์ˆ˜ ์žˆ๋Š” ํ•™์ƒ์˜ ์ตœ๋Œ“๊ฐ’์„ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•ด์ฃผ์„ธ์š”.

์ œํ•œ์‚ฌํ•ญ

  • ์ „์ฒด ํ•™์ƒ์˜ ์ˆ˜๋Š” 2๋ช… ์ด์ƒ 30๋ช… ์ดํ•˜์ž…๋‹ˆ๋‹ค.
  • ์ฒด์œก๋ณต์„ ๋„๋‚œ๋‹นํ•œ ํ•™์ƒ์˜ ์ˆ˜๋Š” 1๋ช… ์ด์ƒ n๋ช… ์ดํ•˜์ด๊ณ  ์ค‘๋ณต๋˜๋Š” ๋ฒˆํ˜ธ๋Š” ์—†์Šต๋‹ˆ๋‹ค.
  • ์—ฌ๋ฒŒ์˜ ์ฒด์œก๋ณต์„ ๊ฐ€์ ธ์˜จ ํ•™์ƒ์˜ ์ˆ˜๋Š” 1๋ช… ์ด์ƒ n๋ช… ์ดํ•˜์ด๊ณ  ์ค‘๋ณต๋˜๋Š” ๋ฒˆํ˜ธ๋Š” ์—†์Šต๋‹ˆ๋‹ค.
  • ์—ฌ๋ฒŒ ์ฒด์œก๋ณต์ด ์žˆ๋Š” ํ•™์ƒ๋งŒ ๋‹ค๋ฅธ ํ•™์ƒ์—๊ฒŒ ์ฒด์œก๋ณต์„ ๋นŒ๋ ค์ค„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
  • ์—ฌ๋ฒŒ ์ฒด์œก๋ณต์„ ๊ฐ€์ ธ์˜จ ํ•™์ƒ์ด ์ฒด์œก๋ณต์„ ๋„๋‚œ๋‹นํ–ˆ์„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด๋•Œ ์ด ํ•™์ƒ์€ ์ฒด์œก๋ณต์„ ํ•˜๋‚˜๋งŒ ๋„๋‚œ๋‹นํ–ˆ๋‹ค๊ณ  ๊ฐ€์ •ํ•˜๋ฉฐ, ๋‚จ์€ ์ฒด์œก๋ณต์ด ํ•˜๋‚˜์ด๊ธฐ์— ๋‹ค๋ฅธ ํ•™์ƒ์—๊ฒŒ๋Š” ์ฒด์œก๋ณต์„ ๋นŒ๋ ค์ค„ ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ

์ž…์ถœ๋ ฅ ์˜ˆ ์„ค๋ช…

์˜ˆ์ œ #1
1๋ฒˆ ํ•™์ƒ์ด 2๋ฒˆ ํ•™์ƒ์—๊ฒŒ ์ฒด์œก๋ณต์„ ๋นŒ๋ ค์ฃผ๊ณ , 3๋ฒˆ ํ•™์ƒ์ด๋‚˜ 5๋ฒˆ ํ•™์ƒ์ด 4๋ฒˆ ํ•™์ƒ์—๊ฒŒ ์ฒด์œก๋ณต์„ ๋นŒ๋ ค์ฃผ๋ฉด ํ•™์ƒ 5๋ช…์ด ์ฒด์œก์ˆ˜์—…์„ ๋“ค์„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์˜ˆ์ œ #2
3๋ฒˆ ํ•™์ƒ์ด 2๋ฒˆ ํ•™์ƒ์ด๋‚˜ 4๋ฒˆ ํ•™์ƒ์—๊ฒŒ ์ฒด์œก๋ณต์„ ๋นŒ๋ ค์ฃผ๋ฉด ํ•™์ƒ 4๋ช…์ด ์ฒด์œก์ˆ˜์—…์„ ๋“ค์„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

 

๋ฐ˜์‘ํ˜•