Programmers] ๊ณผ์ผ ์ฅ์
๐ ํ์ด์ฌ ์ผ๋ก ํ์ด
๐ ๋ฌธ์ ๋งํฌ :
ํ๋ก๊ทธ๋๋จธ์ค
์ฝ๋ ์ค์ฌ์ ๊ฐ๋ฐ์ ์ฑ์ฉ. ์คํ ๊ธฐ๋ฐ์ ํฌ์ง์ ๋งค์นญ. ํ๋ก๊ทธ๋๋จธ์ค์ ๊ฐ๋ฐ์ ๋ง์ถคํ ํ๋กํ์ ๋ฑ๋กํ๊ณ , ๋์ ๊ธฐ์ ๊ถํฉ์ด ์ ๋ง๋ ๊ธฐ์ ๋ค์ ๋งค์นญ ๋ฐ์ผ์ธ์.
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) ์ด๋ผ ์๊ฐ ๋ณต์ก๋ ์ธก๋ฉด์์ ๊ต์ฅํ ์ข๊ณ , ๋ญ๊ฐ ์ฝ๋ ์์ฒด๋ ๊ฐ๊ฒฐํด์ ธ์ ๊ตณ! ๐