๐Ÿ‘จโ€๐Ÿ‘จโ€๐Ÿ‘งโ€๐Ÿ‘ง[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ์ตœ๊ณ ์˜ ์ง‘ํ•ฉ

Chobbyยท2022๋…„ 3์›” 20์ผ
0

Programmers

๋ชฉ๋ก ๋ณด๊ธฐ
21/344

๋ฌธ์ œ ์„ค๋ช…

์ž์—ฐ์ˆ˜ n ๊ฐœ๋กœ ์ด๋ฃจ์–ด์ง„ ์ค‘๋ณต ์ง‘ํ•ฉ(multi set, ํŽธ์˜์ƒ ์ดํ›„์—๋Š” "์ง‘ํ•ฉ"์œผ๋กœ ํ†ต์นญ) ์ค‘์— ๋‹ค์Œ ๋‘ ์กฐ๊ฑด์„ ๋งŒ์กฑํ•˜๋Š” ์ง‘ํ•ฉ์„ ์ตœ๊ณ ์˜ ์ง‘ํ•ฉ์ด๋ผ๊ณ  ํ•ฉ๋‹ˆ๋‹ค.

  1. ๊ฐ ์›์†Œ์˜ ํ•ฉ์ด S๊ฐ€ ๋˜๋Š” ์ˆ˜์˜ ์ง‘ํ•ฉ

  2. ์œ„ ์กฐ๊ฑด์„ ๋งŒ์กฑํ•˜๋ฉด์„œ ๊ฐ ์›์†Œ์˜ ๊ณฑ ์ด ์ตœ๋Œ€๊ฐ€ ๋˜๋Š” ์ง‘ํ•ฉ

์˜ˆ๋ฅผ ๋“ค์–ด์„œ ์ž์—ฐ์ˆ˜ 2๊ฐœ๋กœ ์ด๋ฃจ์–ด์ง„ ์ง‘ํ•ฉ ์ค‘ ํ•ฉ์ด 9๊ฐ€ ๋˜๋Š” ์ง‘ํ•ฉ์€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด 4๊ฐœ๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค.

{ 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 }
๊ทธ์ค‘ ๊ฐ ์›์†Œ์˜ ๊ณฑ์ด ์ตœ๋Œ€์ธ { 4, 5 }๊ฐ€ ์ตœ๊ณ ์˜ ์ง‘ํ•ฉ์ž…๋‹ˆ๋‹ค.

์ง‘ํ•ฉ์˜ ์›์†Œ์˜ ๊ฐœ์ˆ˜ n๊ณผ ๋ชจ๋“  ์›์†Œ๋“ค์˜ ํ•ฉ s๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ์ตœ๊ณ ์˜ ์ง‘ํ•ฉ์„ return ํ•˜๋Š” solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด์ฃผ์„ธ์š”.

์ œํ•œ์‚ฌํ•ญ

  • ์ตœ๊ณ ์˜ ์ง‘ํ•ฉ์€ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌ๋œ 1์ฐจ์› ๋ฐฐ์—ด(list, vector) ๋กœ return ํ•ด์ฃผ์„ธ์š”.

  • ๋งŒ์•ฝ ์ตœ๊ณ ์˜ ์ง‘ํ•ฉ์ด ์กด์žฌํ•˜์ง€ ์•Š๋Š” ๊ฒฝ์šฐ์— ํฌ๊ธฐ๊ฐ€ 1์ธ 1์ฐจ์› ๋ฐฐ์—ด(list, vector) ์— -1 ์„ ์ฑ„์›Œ์„œ return ํ•ด์ฃผ์„ธ์š”.

  • ์ž์—ฐ์ˆ˜์˜ ๊ฐœ์ˆ˜ n์€ 1 ์ด์ƒ 10,000 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ž…๋‹ˆ๋‹ค.

  • ๋ชจ๋“  ์›์†Œ๋“ค์˜ ํ•ฉ s๋Š” 1 ์ด์ƒ, 100,000,000 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ž…๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ

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

์ž…์ถœ๋ ฅ ์˜ˆ#1
๋ฌธ์ œ์˜ ์˜ˆ์‹œ์™€ ๊ฐ™์Šต๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ#2
์ž์—ฐ์ˆ˜ 2๊ฐœ๋ฅผ ๊ฐ€์ง€๊ณ ๋Š” ํ•ฉ์ด 1์ธ ์ง‘ํ•ฉ์„ ๋งŒ๋“ค ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ -1์ด ๋“ค์–ด์žˆ๋Š” ๋ฐฐ์—ด์„ ๋ฐ˜ํ™˜ํ•ฉ๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ#3
์ž์—ฐ์ˆ˜ 2๊ฐœ๋กœ ์ด๋ฃจ์–ด์ง„ ์ง‘ํ•ฉ ์ค‘ ์›์†Œ์˜ ํ•ฉ์ด 8์ธ ์ง‘ํ•ฉ์€ ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.

{ 1, 7 }, { 2, 6 }, { 3, 5 }, { 4, 4 }

๊ทธ์ค‘ ๊ฐ ์›์†Œ์˜ ๊ณฑ์ด ์ตœ๋Œ€์ธ { 4, 4 }๊ฐ€ ์ตœ๊ณ ์˜ ์ง‘ํ•ฉ์ž…๋‹ˆ๋‹ค.

ํ’€์ด ์‹œ์ž‘

function solution(n, s) {
    // n์ด s๋ณด๋‹ค ํฌ๋‹ค๋ฉด [1,1,1] ๋„ ๋งŒ์กฑํ•˜์ง€ ๋ชปํ•˜๋ฏ€๋กœ ๋ถˆ๊ฐ€๋Šฅ
    if(n > s) return [-1]
    // s/n ์€ ๊ฐ€์žฅ ๊ณ ๋ฅธ ๋ฐฐ์—ด์„ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋Š” ๊ฐ’์ด๋ฏ€๋กœ n์˜ ๊ธธ์ด๋ฅผ ๊ฐ€์ง„ ๋ฐฐ์—ด์„ s/n์œผ๋กœ ์ฑ„์›€
    const arr = Array(n).fill(Math.floor(s/n))
    // ๋‚˜๋ˆˆ ํ›„ ๋‚˜๋จธ์ง€ ๊ฐ’์€ ์˜ค๋ฆ„์ฐจ ์ˆœ ๋ฐฐ์—ด์˜ ์กฐ๊ฑด์„ ๋งŒ์กฑ์‹œํ‚ค๊ธฐ ์œ„ํ•ด ๋ฐฐ์—ด์˜ ๋’ค์—์„œ ๋ถ€ํ„ฐ +1 ํ•˜๋ฉฐ ์ฑ„์›Œ์คŒ
    if(s%n) {
        for(let i = n-1, more = s%n ; more > 0 ; i --,more--) {
            arr[i] = arr[i]+1    
        }
    }
    return arr
}
profile
๋‚ด ์ง€์‹์„ ๊ณต์œ ํ•  ์ˆ˜ ์žˆ๋Š” ๋Œ€๋‹ดํ•จ

0๊ฐœ์˜ ๋Œ“๊ธ€