[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ๊ตฌ๋ช…๋ณดํŠธ /ํŒŒ์ด์ฌ /python /ํƒ์š•๋ฒ•
Algorithm/Programmers

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ๊ตฌ๋ช…๋ณดํŠธ /ํŒŒ์ด์ฌ /python /ํƒ์š•๋ฒ•

728x90
๋ฐ˜์‘ํ˜•

๐Ÿ’กsolutions )

โœ… ์‚ฌ๋žŒ๋“ค์˜ ๋ฌด๊ฒŒ๋ฅผ ๋‹ด์€ people ๋ฆฌ์ŠคํŠธ๋ฅผ ๋ฌด๊ฒŒ๋ฅผ ๊ธฐ์ค€์œผ๋กœ ๋‚ด๋ฆผ์ฐจ์ˆœ ์ •๋ ฌํ•œ๋‹ค.

โœ… ์ฒ˜์Œ๊ณผ ๋์˜ ์ธ๋ฑ์Šค๋ฅผ start, end๋กœ ์žก์•„๋‘๊ณ  while ๋ฐ˜๋ณต๋ฌธ์„ ์‹คํ–‰ํ•œ๋‹ค.

โœ… ํƒˆ์ถœ์„ ์œ„ํ•œ ๊ตฌ๋ช…๋ณดํŠธ์˜ ์ด ๊ฐœ์ˆ˜๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” cnt์˜ ์ดˆ๊ธฐ๊ฐ’์€ ์ „์ฒด ์‚ฌ๋žŒ๋“ค์˜ ์ˆ˜๋กœ ์ตœ๋Œ€์น˜๋กœ ์žก์•„๋‘”๋‹ค.

โœ… ์ฒ˜์Œ๊ณผ ๋์— ์žˆ๋Š” ์‚ฌ๋žŒ๋“ค์˜ ๋ฌด๊ฒŒ, ๋‹ค์‹œ ๋งํ•˜๋ฉด ์ตœ์†Œํ•œ์˜ ๋ฌด๊ฒŒ๋กœ 2๋ช…์ด์„œ ํ•จ๊ป˜ ํƒˆ ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ์ธ๋ฐ, ์ด๋•Œ limit์„ ๋„˜์ง€ ์•Š์œผ๋ฉด ์ „์ฒด ๋ณดํŠธ์˜ ๊ฐœ์ˆ˜์—์„œ -1์”ฉ ๋นผ์ค€๋‹ค. limit์„ ๋„˜์œผ๋ฉด ํ˜ผ์ž ํƒ€๋Š” ๊ฒฝ์šฐ๋กœ start์˜ ์œ„์น˜๋งŒ ์—…๋ฐ์ดํŠธ.

 

๐ŸŽซcode )

def solution(people, limit):
    people.sort(reverse=True)
    start, end = 0, len(people)-1
    cnt = len(people) # ์ „์ฒด ์‚ฌ๋žŒ ์ˆ˜๋งŒํผ ๋ณดํŠธ์˜ ๊ฐœ์ˆ˜๋ฅผ ์žก๊ณ , ๋‘๋ช…์”ฉ ํƒ€๋Š” ๊ฒฝ์šฐ๊ฐ€ ์ƒ๊ธฐ๋ฉด -1์”ฉ ๋นผ์ค€๋‹ค
    while start < end: # while๋ฌธ ์ข…๋ฃŒ์กฐ๊ฑด, start์™€ end์˜ ์ธ๋ฑ์Šค๊ฐ€ ๊ฐ™์•„์ง€๋ฉด ๋ฌด๊ฒŒ๋ฅผ ๋น„๊ตํ•  ํ•„์š”๊ฐ€ ์—†๋‹ค
        if people[start] + people[end] <= limit:
            end -= 1 # ๋‘๋ช…์ด ๊ฐ™์ด ํƒ€๋Š” ๊ฒฝ์šฐ๊ฐ€ ์ƒ๊ธฐ๋ฉด end์˜ ์ธ๋ฑ์Šค๋ฅผ ํ•œ์นธ ์•ž์œผ๋กœ ๋ณ€๊ฒฝ
            cnt -= 1
        start+= 1
    return cnt

 

๐Ÿ“Œ description )

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

 

์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ๊ตฌ๋ช…๋ณดํŠธ

๋ฌด์ธ๋„์— ๊ฐ‡ํžŒ ์‚ฌ๋žŒ๋“ค์„ ๊ตฌ๋ช…๋ณดํŠธ๋ฅผ ์ด์šฉํ•˜์—ฌ ๊ตฌ์ถœํ•˜๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ๊ตฌ๋ช…๋ณดํŠธ๋Š” ์ž‘์•„์„œ ํ•œ ๋ฒˆ์— ์ตœ๋Œ€ 2๋ช…์”ฉ ๋ฐ–์— ํƒˆ ์ˆ˜ ์—†๊ณ , ๋ฌด๊ฒŒ ์ œํ•œ๋„ ์žˆ์Šต๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ์‚ฌ๋žŒ๋“ค์˜ ๋ชธ๋ฌด๊ฒŒ๊ฐ€ [70kg, 50kg, 80kg, 5

programmers.co.kr

 

๋ฌธ์ œ ์„ค๋ช…

๋ฌด์ธ๋„์— ๊ฐ‡ํžŒ ์‚ฌ๋žŒ๋“ค์„ ๊ตฌ๋ช…๋ณดํŠธ๋ฅผ ์ด์šฉํ•˜์—ฌ ๊ตฌ์ถœํ•˜๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ๊ตฌ๋ช…๋ณดํŠธ๋Š” ์ž‘์•„์„œ ํ•œ ๋ฒˆ์— ์ตœ๋Œ€ 2๋ช…์”ฉ ๋ฐ–์— ํƒˆ ์ˆ˜ ์—†๊ณ , ๋ฌด๊ฒŒ ์ œํ•œ๋„ ์žˆ์Šต๋‹ˆ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด, ์‚ฌ๋žŒ๋“ค์˜ ๋ชธ๋ฌด๊ฒŒ๊ฐ€ [70kg, 50kg, 80kg, 50kg]์ด๊ณ  ๊ตฌ๋ช…๋ณดํŠธ์˜ ๋ฌด๊ฒŒ ์ œํ•œ์ด 100kg์ด๋ผ๋ฉด 2๋ฒˆ์งธ ์‚ฌ๋žŒ๊ณผ 4๋ฒˆ์งธ ์‚ฌ๋žŒ์€ ๊ฐ™์ด ํƒˆ ์ˆ˜ ์žˆ์ง€๋งŒ 1๋ฒˆ์งธ ์‚ฌ๋žŒ๊ณผ 3๋ฒˆ์งธ ์‚ฌ๋žŒ์˜ ๋ฌด๊ฒŒ์˜ ํ•ฉ์€ 150kg์ด๋ฏ€๋กœ ๊ตฌ๋ช…๋ณดํŠธ์˜ ๋ฌด๊ฒŒ ์ œํ•œ์„ ์ดˆ๊ณผํ•˜์—ฌ ๊ฐ™์ด ํƒˆ ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค.

๊ตฌ๋ช…๋ณดํŠธ๋ฅผ ์ตœ๋Œ€ํ•œ ์ ๊ฒŒ ์‚ฌ์šฉํ•˜์—ฌ ๋ชจ๋“  ์‚ฌ๋žŒ์„ ๊ตฌ์ถœํ•˜๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค.

์‚ฌ๋žŒ๋“ค์˜ ๋ชธ๋ฌด๊ฒŒ๋ฅผ ๋‹ด์€ ๋ฐฐ์—ด people๊ณผ ๊ตฌ๋ช…๋ณดํŠธ์˜ ๋ฌด๊ฒŒ ์ œํ•œ limit๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ๋ชจ๋“  ์‚ฌ๋žŒ์„ ๊ตฌ์ถœํ•˜๊ธฐ ์œ„ํ•ด ํ•„์š”ํ•œ ๊ตฌ๋ช…๋ณดํŠธ ๊ฐœ์ˆ˜์˜ ์ตœ์†Ÿ๊ฐ’์„ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•ด์ฃผ์„ธ์š”.

์ œํ•œ์‚ฌํ•ญ

  • ๋ฌด์ธ๋„์— ๊ฐ‡ํžŒ ์‚ฌ๋žŒ์€ 1๋ช… ์ด์ƒ 50,000๋ช… ์ดํ•˜์ž…๋‹ˆ๋‹ค.
  • ๊ฐ ์‚ฌ๋žŒ์˜ ๋ชธ๋ฌด๊ฒŒ๋Š” 40kg ์ด์ƒ 240kg ์ดํ•˜์ž…๋‹ˆ๋‹ค.
  • ๊ตฌ๋ช…๋ณดํŠธ์˜ ๋ฌด๊ฒŒ ์ œํ•œ์€ 40kg ์ด์ƒ 240kg ์ดํ•˜์ž…๋‹ˆ๋‹ค.
  • ๊ตฌ๋ช…๋ณดํŠธ์˜ ๋ฌด๊ฒŒ ์ œํ•œ์€ ํ•ญ์ƒ ์‚ฌ๋žŒ๋“ค์˜ ๋ชธ๋ฌด๊ฒŒ ์ค‘ ์ตœ๋Œ“๊ฐ’๋ณด๋‹ค ํฌ๊ฒŒ ์ฃผ์–ด์ง€๋ฏ€๋กœ ์‚ฌ๋žŒ๋“ค์„ ๊ตฌ์ถœํ•  ์ˆ˜ ์—†๋Š” ๊ฒฝ์šฐ๋Š” ์—†์Šต๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ

people                                                    limit                                           return
[70, 50, 80, 50] 100 3
[70, 80, 50] 100 3
๋ฐ˜์‘ํ˜•