๐Ÿคฌ[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ์•ผ๊ทผ ์ง€์ˆ˜

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

Programmers

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

ํ•ด๋‹น ๊ฒŒ์‹œ๋ฌผ์€ longroadhome๋‹˜์˜ ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค LV.3 ์•ผ๊ทผ ์ง€์ˆ˜ JS ๊ฒŒ์‹œ๋ฌผ์„ ์ฐธ๊ณ ํ•˜์—ฌ ์ œ์ž‘๋˜์—ˆ์Œ์„ ๋ฏธ๋ฆฌ ๋ฐํž™๋‹ˆ๋‹ค.

๋ฌธ์ œ ์„ค๋ช…

ํšŒ์‚ฌ์› Demi๋Š” ๊ฐ€๋”์€ ์•ผ๊ทผ์„ ํ•˜๋Š”๋ฐ์š”, ์•ผ๊ทผ์„ ํ•˜๋ฉด ์•ผ๊ทผ ํ”ผ๋กœ๋„๊ฐ€ ์Œ“์ž…๋‹ˆ๋‹ค. ์•ผ๊ทผ ํ”ผ๋กœ๋„๋Š” ์•ผ๊ทผ์„ ์‹œ์ž‘ํ•œ ์‹œ์ ์—์„œ ๋‚จ์€ ์ผ์˜ ์ž‘์—…๋Ÿ‰์„ ์ œ๊ณฑํ•˜์—ฌ ๋”ํ•œ ๊ฐ’์ž…๋‹ˆ๋‹ค. Demi๋Š” N์‹œ๊ฐ„ ๋™์•ˆ ์•ผ๊ทผ ํ”ผ๋กœ๋„๋ฅผ ์ตœ์†Œํ™”ํ•˜๋„๋ก ์ผํ•  ๊ฒ๋‹ˆ๋‹ค.Demi๊ฐ€ 1์‹œ๊ฐ„ ๋™์•ˆ ์ž‘์—…๋Ÿ‰ 1๋งŒํผ์„ ์ฒ˜๋ฆฌํ•  ์ˆ˜ ์žˆ๋‹ค๊ณ  ํ•  ๋•Œ, ํ‡ด๊ทผ๊นŒ์ง€ ๋‚จ์€ N ์‹œ๊ฐ„๊ณผ ๊ฐ ์ผ์— ๋Œ€ํ•œ ์ž‘์—…๋Ÿ‰ works์— ๋Œ€ํ•ด ์•ผ๊ทผ ํ”ผ๋กœ๋„๋ฅผ ์ตœ์†Œํ™”ํ•œ ๊ฐ’์„ ๋ฆฌํ„ดํ•˜๋Š” ํ•จ์ˆ˜ solution์„ ์™„์„ฑํ•ด์ฃผ์„ธ์š”.

์ œํ•œ ์‚ฌํ•ญ

works๋Š” ๊ธธ์ด 1 ์ด์ƒ, 20,000 ์ดํ•˜์ธ ๋ฐฐ์—ด์ž…๋‹ˆ๋‹ค.

works์˜ ์›์†Œ๋Š” 50000 ์ดํ•˜์ธ ์ž์—ฐ์ˆ˜์ž…๋‹ˆ๋‹ค.

n์€ 1,000,000 ์ดํ•˜์ธ ์ž์—ฐ์ˆ˜์ž…๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ

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

์ž…์ถœ๋ ฅ ์˜ˆ #1

n=4 ์ผ ๋•Œ, ๋‚จ์€ ์ผ์˜ ์ž‘์—…๋Ÿ‰์ด [4, 3, 3] ์ด๋ผ๋ฉด ์•ผ๊ทผ ์ง€์ˆ˜๋ฅผ ์ตœ์†Œํ™”ํ•˜๊ธฐ ์œ„ํ•ด 4์‹œ๊ฐ„๋™์•ˆ ์ผ์„ ํ•œ ๊ฒฐ๊ณผ๋Š” [2, 2, 2]์ž…๋‹ˆ๋‹ค. ์ด ๋•Œ ์•ผ๊ทผ ์ง€์ˆ˜๋Š” 22 + 22 + 22 = 12 ์ž…๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ #2

n=1์ผ ๋•Œ, ๋‚จ์€ ์ผ์˜ ์ž‘์—…๋Ÿ‰์ด [2,1,2]๋ผ๋ฉด ์•ผ๊ทผ ์ง€์ˆ˜๋ฅผ ์ตœ์†Œํ™”ํ•˜๊ธฐ ์œ„ํ•ด 1์‹œ๊ฐ„๋™์•ˆ ์ผ์„ ํ•œ ๊ฒฐ๊ณผ๋Š” [1,1,2]์ž…๋‹ˆ๋‹ค. ์•ผ๊ทผ์ง€์ˆ˜๋Š” 12 + 12 + 22 = 6์ž…๋‹ˆ๋‹ค.

๋‚˜์˜ ํ’€์ด

function solution(n, works) {
    // ํ•  ์ˆ˜ ์žˆ๋Š” ์ผ์˜ ์ด๋Ÿ‰์ด works ๋ฐฐ์—ด์„ ๋ชจ๋‘ ๋น„์šธ ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ
    if(works.reduce((a,b) => a+b,0) <= n) return 0
    
    // ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌ
    works.sort((a,b) => b-a)
    
    // ์•„์ง ํ•  ์ˆ˜ ์žˆ๋Š” ์ผ์ด ๋‚จ์€๊ฒฝ์šฐ
    while(n) {
        // 0๋ฒˆ์งธ ์ธ๋ฑ์Šค๊ฐ€ ํ•ด๋‹น ๋ฐ˜๋ณต์˜ ์ตœ๋Œ“๊ฐ’
        const max = works[0]
        for(let i = 0 ; i < works.length ; i ++) {
            // ํ•ด๋‹น ์ธ๋ฑ์Šค๋„ ์ตœ๋Œ“๊ฐ’๊ณผ ๊ฐ™๋‹ค๋ฉด
            if(works[i] === max) {
                n--
                works[i]--
            }
            if(!n) break
        }    
    }
    
    return works.reduce((a,b) => a+(b**2) ,0)
}
  1. ์—ฐ์‚ฐ์ด ํ•„์š”ํ•˜์ง€ ์•Š์€ ํ•ด์•ผํ•  ์ผ์˜ ์ดํ•ฉ๋ณด๋‹ค ํ•  ์ˆ˜ ์žˆ๋Š”์ผ์ด ๋” ๋งŽ๋‹ค๋ฉด [0,0,...] ์ด๋ฏ€๋กœ 0 ์„ return

  2. ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌ

  3. n์ด ๋‚จ์€๊ฒฝ์šฐ ๋ฐ˜๋ณต

    3-1. ์ตœ๋Œ“๊ฐ’์„ ์ง€์ •ํ•˜๋ฉฐ ์ตœ๋Œ“๊ฐ’๊ณผ ๊ฐ™์€ ๋ฐฐ์—ด ๋‚ด์—์„œ ๊ฐ€์žฅ ํฐ ์ˆ˜๋ฅผ ์ฐพ์•„ ํ•  ์ˆ˜ ์žˆ๋Š” ์ผ์˜ ์ˆ˜์™€ ํ•ด๋‹น ์ธ๋ฑ์Šค์˜ ์ˆ˜๋ฅผ 1์”ฉ ๋บŒ

    โ€ป ํฐ ์ˆ˜์˜ ์ œ๊ณฑ์€ ํ•ญ์ƒ ์ž‘์€ ์ˆ˜์˜ ์ œ๊ณฑ๋ณด๋‹ค ํฌ๊ธฐ ๋•Œ๋ฌธ์— ํฐ ์ˆ˜๋ฅผ ๋ชจ๋‘ ์ฐพ์•„ ๋‚ฎ๊ฒŒ ํ‰์ค€ํ™” ์‹œํ‚ค๋Š” ๊ณผ์ •

    3-2. ํ•ด๋‹น ์ž‘์—…์œผ๋กœ ํ•  ์ˆ˜ ์žˆ๋Š” ์ผ์ด 0๊ฐœ ๋‚จ์•˜๋‹ค๋ฉด ๋ฐ˜๋ณต ์ค‘๋‹จ

  4. ๋‚จ์•„์žˆ๋Š” ์ˆ˜๋ฅผ ๋ชจ๋‘ ์ œ๊ณฑํ•˜์—ฌ ๋”ํ•œ ํ›„ ์ถœ๋ ฅ

profile
๋‚ด ์ง€์‹์„ ๊ณต์œ ํ•  ์ˆ˜ ์žˆ๋Š” ๋Œ€๋‹ดํ•จ

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