Coding Test/Algorithm

Programmers] ๊ณผ์ผ ์žฅ์ˆ˜

littlezero48 2023. 2. 13. 17:54

๐Ÿ“Œ ํŒŒ์ด์ฌ ์œผ๋กœ ํ’€์ด

 

๐Ÿ“Œ ๋ฌธ์ œ ๋งํฌ 

 

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

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

programmers.co.kr

 

๐Ÿ“Œ ๋ฌธ์ œ ์„ค๋ช… :

๊ณผ์ผ ์žฅ์ˆ˜๊ฐ€ ์‚ฌ๊ณผ ์ƒ์ž๋ฅผ ํฌ์žฅํ•˜๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค. ์‚ฌ๊ณผ๋Š” ์ƒํƒœ์— ๋”ฐ๋ผ 1์ ๋ถ€ํ„ฐ k์ ๊นŒ์ง€์˜ ์ ์ˆ˜๋กœ ๋ถ„๋ฅ˜ํ•˜๋ฉฐ, k์ ์ด ์ตœ์ƒํ’ˆ์˜ ์‚ฌ๊ณผ์ด๊ณ  1์ ์ด ์ตœํ•˜ํ’ˆ์˜ ์‚ฌ๊ณผ์ž…๋‹ˆ๋‹ค. ์‚ฌ๊ณผ ํ•œ ์ƒ์ž์˜ ๊ฐ€๊ฒฉ์€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ๊ฒฐ์ •๋ฉ๋‹ˆ๋‹ค.

  • ํ•œ ์ƒ์ž์— ์‚ฌ๊ณผ๋ฅผ m๊ฐœ์”ฉ ๋‹ด์•„ ํฌ์žฅํ•ฉ๋‹ˆ๋‹ค.
  • ์ƒ์ž์— ๋‹ด๊ธด ์‚ฌ๊ณผ ์ค‘ ๊ฐ€์žฅ ๋‚ฎ์€ ์ ์ˆ˜๊ฐ€ p (1 ≤ p ≤ k)์ ์ธ ๊ฒฝ์šฐ, ์‚ฌ๊ณผ ํ•œ ์ƒ์ž์˜ ๊ฐ€๊ฒฉ์€ p * m ์ž…๋‹ˆ๋‹ค.

๊ณผ์ผ ์žฅ์ˆ˜๊ฐ€ ๊ฐ€๋Šฅํ•œ ๋งŽ์€ ์‚ฌ๊ณผ๋ฅผ ํŒ”์•˜์„ ๋•Œ, ์–ป์„ ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ€ ์ด์ต์„ ๊ณ„์‚ฐํ•˜๊ณ ์ž ํ•ฉ๋‹ˆ๋‹ค.(์‚ฌ๊ณผ๋Š” ์ƒ์ž ๋‹จ์œ„๋กœ๋งŒ ํŒ๋งคํ•˜๋ฉฐ, ๋‚จ๋Š” ์‚ฌ๊ณผ๋Š” ๋ฒ„๋ฆฝ๋‹ˆ๋‹ค)

์˜ˆ๋ฅผ ๋“ค์–ด, k = 3, m = 4, ์‚ฌ๊ณผ 7๊ฐœ์˜ ์ ์ˆ˜๊ฐ€ [1, 2, 3, 1, 2, 3, 1]์ด๋ผ๋ฉด, ๋‹ค์Œ๊ณผ ๊ฐ™์ด [2, 3, 2, 3]์œผ๋กœ ๊ตฌ์„ฑ๋œ ์‚ฌ๊ณผ ์ƒ์ž 1๊ฐœ๋ฅผ ๋งŒ๋“ค์–ด ํŒ๋งคํ•˜์—ฌ ์ตœ๋Œ€ ์ด์ต์„ ์–ป์„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

  • (์ตœ์ € ์‚ฌ๊ณผ ์ ์ˆ˜) x (ํ•œ ์ƒ์ž์— ๋‹ด๊ธด ์‚ฌ๊ณผ ๊ฐœ์ˆ˜) x (์ƒ์ž์˜ ๊ฐœ์ˆ˜) = 2 x 4 x 1 = 8

์‚ฌ๊ณผ์˜ ์ตœ๋Œ€ ์ ์ˆ˜ k, ํ•œ ์ƒ์ž์— ๋“ค์–ด๊ฐ€๋Š” ์‚ฌ๊ณผ์˜ ์ˆ˜ m, ์‚ฌ๊ณผ๋“ค์˜ ์ ์ˆ˜ score๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ๊ณผ์ผ ์žฅ์ˆ˜๊ฐ€ ์–ป์„ ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ€ ์ด์ต์„ returnํ•˜๋Š” solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด์ฃผ์„ธ์š”.

 

๐Ÿ“Œ ์ œํ•œ ์‚ฌํ•ญ

  • 3 ≤ k ≤ 9
  • 3 ≤ m ≤ 10
  • 7 ≤ score์˜ ๊ธธ์ด ≤ 1,000,000
    • 1 ≤ score[i] ≤ k
  • ์ด์ต์ด ๋ฐœ์ƒํ•˜์ง€ ์•Š๋Š” ๊ฒฝ์šฐ์—๋Š” 0์„ return ํ•ด์ฃผ์„ธ์š”.

 

๐Ÿ“Œ ์ž…์ถœ๋ ฅ ์˜ˆ


์ถ”์ธก) 

* ์ตœ๋Œ€ํ•œ ์ด์ต์„ ์œ„ํ•ด ์ƒ์ž์— ๋‹ด์ง€ ๋ชปํ•  ์‚ฌ๊ณผ๋Š” ํ•˜ํ’ˆ์˜ ์‚ฌ๊ณผ๋“ค๋กœ ํ•  ๊ฒƒ

- ์ƒ์ž๊ฐ€ ๋ช‡๊ฐœ (box) ๋‚˜์˜ค๊ณ , ๋ช‡๊ฐœ๊ฐ€ ๋ฒ„๋ ค์งˆ์ง€ ๋จผ์ € ๊ณ„์‚ฐ

- ์ „์ฒด์—์„œ ํ•˜ํ’ˆ๋“ค์„ ์–ด๋–ป๊ฒŒ ๊ณจ๋ผ๋‚ผ ๊ฒƒ์ธ๊ฐ€  > sortํ•ด์„œ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ฆฌํ•˜์—ฌ ๋ฒ„๋ ค์งˆ ๊ฐœ์ˆ˜๋ฅผ ์‚ญ์ œ

- ์‚ญ์ œํ•˜๊ณ  ๋‚˜์„œ์˜ ๊ฐ€์žฅ ๋ฐฐ์—ด 0๋ฒˆ์งธ๊ฐ€ ๊ฐ€์žฅ ๋‚ฎ์€ ์ ์ˆ˜ p์— ํ•ด๋‹น 

- m๊ฐœ์‹ ์ž˜๋ผ ์ƒ์ž์— ๋„ฃ๊ณ  ๋‹ค์Œ ์ƒ์ž์—์„œ ๊ฐ€์žฅ ์ฒซ ์ธ๋ฑ์Šค ๊ฐ’์„ ๋˜ ๋„ฃ์–ด p(๊ฐ€์žฅ ๋‚ฎ์€ ์ ์ˆ˜) x m(ํ•œ์ƒ์ž ์•ˆ์˜ ์‚ฌ๊ณผ์ˆ˜)  ๊ฒฐ๊ณผ ๊ฐ’์„ ๊ตฌํ•ด result์— ๊ณ„์† ๋”ํ•จ

- ๊ทธ๋ฆฌ๊ณ  result ๋ฐ˜ํ™˜

 

* ์ด์ต์ด ๋ฐœ์ƒํ•˜์ง€ ์•Š๋Š” ๊ฒฝ์šฐ? > ํ•œ์ƒ์ž๋ฅผ ์•„์˜ˆ ๋งŒ๋“ค์ง€ ๋ชปํ•˜๋Š” ๊ฒฝ์šฐ

* ์ตœ๋Œ€ ์ ์ˆ˜๋Š” ์™œ ์žˆ์ง€? ์ตœ๋Œ€ ์ ์ˆ˜๋ฅผ ๋„˜๋Š” ์‚ฌ๊ณผ๋„ ์žˆ๋‚˜?

 

์†Œ์Šค์ฝ”๋“œ) 

* 1์ฐจ) ์‹คํŒจ: 79.2 ( ์‹œ๊ฐ„์ดˆ๊ณผ  11 - 15 ์ผ€์ด์Šค)

def solution(k, m, score):
    remain = len(score) % m
    box = int(len(score)/m)
    if box == 0 :
        return 0

    score.sort()
    result = 0
    score = score[remain:]
    for i in range(0, box) :
        p = score.pop(0)
        result += p * m
        for i in range(0, m-1) :
            score.pop(0)

    return result

* 2์ฐจ) ์„ฑ๊ณต : ์Šคํƒ์œผ๋กœ ํ’€๊ธฐ

def solution(k, m, score):
    score.sort()
    result = 0

    while int(len(score) / m) > 0 :
        p = 0
        for x in range(0, m) :
            p = score.pop()

        result += p * m

    return result

 

๋ฆฌ๋ทฐ) 

๋˜ ์‹œ๊ฐ„ ์ดˆ๊ณผ๊ฐ€ ๋‚ฌ๊ธธ๋ž˜ ์Šคํƒ์ด๋‚˜ ํ๋ฅผ ์‚ฌ์šฉํ•ด๋ณผ๊นŒ ํ–ˆ๋Š”๋ฐ, ์—ญ์‹œ๋‚˜... ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ์ •๋ง ์—ด์‹ฌํžˆ ๊ณต๋ถ€ํ•ด์•ผ๊ฒ ๋‹ค. ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ์ž˜ ์•Œ๋ฉด ์‰ฝ๊ฒŒ ํ’€ ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ œ๋ฅผ ํ›จ์”ฌ ์ˆ˜์›”ํ•˜๊ณ  ํšจ์œจ์ ์œผ๋กœ ํ’€ ์ˆ˜ ์žˆ์Œ์„ ๋А๊ผˆ๋‹ค.  pop์ด๋‚˜ ํ‘ธ์‰ฌ๋Š” O(1) ์ด๋ผ ์‹œ๊ฐ„ ๋ณต์žก๋„ ์ธก๋ฉด์—์„œ ๊ต‰์žฅํžˆ ์ข‹๊ณ , ๋ญ”๊ฐ€ ์ฝ”๋“œ ์ž์ฒด๋„ ๊ฐ„๊ฒฐํ•ด์ ธ์„œ ๊ตณ! ๐Ÿ‘