๐Ÿงก๋ฌธ์ œ ์„ค๋ช…

์ฒ ์ˆ˜๋Š” ๋กค์ผ€์ดํฌ๋ฅผ ๋‘ ์กฐ๊ฐ์œผ๋กœ ์ž˜๋ผ์„œ ๋™์ƒ๊ณผ ํ•œ ์กฐ๊ฐ์”ฉ ๋‚˜๋ˆ  ๋จน์œผ๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ์ด ๋กค์ผ€์ดํฌ์—๋Š” ์—ฌ๋Ÿฌ๊ฐ€์ง€ ํ† ํ•‘๋“ค์ด ์ผ๋ ฌ๋กœ ์˜ฌ๋ ค์ ธ ์žˆ์Šต๋‹ˆ๋‹ค. ์ฒ ์ˆ˜์™€ ๋™์ƒ์€ ๋กค์ผ€์ดํฌ๋ฅผ ๊ณตํ‰ํ•˜๊ฒŒ ๋‚˜๋ˆ ๋จน์œผ๋ ค ํ•˜๋Š”๋ฐ, ๊ทธ๋“ค์€ ๋กค์ผ€์ดํฌ์˜ ํฌ๊ธฐ๋ณด๋‹ค ๋กค์ผ€์ดํฌ ์œ„์— ์˜ฌ๋ ค์ง„ ํ† ํ•‘๋“ค์˜ ์ข…๋ฅ˜์— ๋” ๊ด€์‹ฌ์ด ๋งŽ์Šต๋‹ˆ๋‹ค. ๊ทธ๋ž˜์„œ ์ž˜๋ฆฐ ์กฐ๊ฐ๋“ค์˜ ํฌ๊ธฐ์™€ ์˜ฌ๋ ค์ง„ ํ† ํ•‘์˜ ๊ฐœ์ˆ˜์— ์ƒ๊ด€์—†์ด ๊ฐ ์กฐ๊ฐ์— ๋™์ผํ•œ ๊ฐ€์ง“์ˆ˜์˜ ํ† ํ•‘์ด ์˜ฌ๋ผ๊ฐ€๋ฉด ๊ณตํ‰ํ•˜๊ฒŒ ๋กค์ผ€์ดํฌ๊ฐ€ ๋‚˜๋ˆ„์–ด์ง„ ๊ฒƒ์œผ๋กœ ์ƒ๊ฐํ•ฉ๋‹ˆ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด, ๋กค์ผ€์ดํฌ์— 4๊ฐ€์ง€ ์ข…๋ฅ˜์˜ ํ† ํ•‘์ด ์˜ฌ๋ ค์ ธ ์žˆ๋‹ค๊ณ  ํ•ฉ์‹œ๋‹ค. ํ† ํ•‘๋“ค์„ 1, 2, 3, 4์™€ ๊ฐ™์ด ๋ฒˆํ˜ธ๋กœ ํ‘œ์‹œํ–ˆ์„ ๋•Œ, ์ผ€์ดํฌ ์œ„์— ํ† ํ•‘๋“ค์ด [1, 2, 1, 3, 1, 4, 1, 2] ์ˆœ์„œ๋กœ ์˜ฌ๋ ค์ ธ ์žˆ์Šต๋‹ˆ๋‹ค. ๋งŒ์•ฝ ์„ธ ๋ฒˆ์งธ ํ† ํ•‘(1)๊ณผ ๋„ค ๋ฒˆ์งธ ํ† ํ•‘(3) ์‚ฌ์ด๋ฅผ ์ž๋ฅด๋ฉด ๋กค์ผ€์ดํฌ์˜ ํ† ํ•‘์€ [1, 2, 1], [3, 1, 4, 1, 2]๋กœ ๋‚˜๋‰˜๊ฒŒ ๋ฉ๋‹ˆ๋‹ค. ์ฒ ์ˆ˜๊ฐ€ [1, 2, 1]์ด ๋†“์ธ ์กฐ๊ฐ์„, ๋™์ƒ์ด [3, 1, 4, 1, 2]๊ฐ€ ๋†“์ธ ์กฐ๊ฐ์„ ๋จน๊ฒŒ ๋˜๋ฉด ์ฒ ์ˆ˜๋Š” ๋‘ ๊ฐ€์ง€ ํ† ํ•‘(1, 2)์„ ๋ง›๋ณผ ์ˆ˜ ์žˆ์ง€๋งŒ, ๋™์ƒ์€ ๋„ค ๊ฐ€์ง€ ํ† ํ•‘(1, 2, 3, 4)์„ ๋ง›๋ณผ ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ, ์ด๋Š” ๊ณตํ‰ํ•˜๊ฒŒ ๋‚˜๋ˆ„์–ด์ง„ ๊ฒƒ์ด ์•„๋‹™๋‹ˆ๋‹ค. ๋งŒ์•ฝ ๋กค์ผ€์ดํฌ์˜ ๋„ค ๋ฒˆ์งธ ํ† ํ•‘(3)๊ณผ ๋‹ค์„ฏ ๋ฒˆ์งธ ํ† ํ•‘(1) ์‚ฌ์ด๋ฅผ ์ž๋ฅด๋ฉด [1, 2, 1, 3], [1, 4, 1, 2]๋กœ ๋‚˜๋‰˜๊ฒŒ ๋ฉ๋‹ˆ๋‹ค. ์ด ๊ฒฝ์šฐ ์ฒ ์ˆ˜๋Š” ์„ธ ๊ฐ€์ง€ ํ† ํ•‘(1, 2, 3)์„, ๋™์ƒ๋„ ์„ธ ๊ฐ€์ง€ ํ† ํ•‘(1, 2, 4)์„ ๋ง›๋ณผ ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ, ์ด๋Š” ๊ณตํ‰ํ•˜๊ฒŒ ๋‚˜๋ˆ„์–ด์ง„ ๊ฒƒ์ž…๋‹ˆ๋‹ค. ๊ณตํ‰ํ•˜๊ฒŒ ๋กค์ผ€์ดํฌ๋ฅผ ์ž๋ฅด๋Š” ๋ฐฉ๋ฒ•์€ ์—ฌ๋Ÿฌ๊ฐ€์ง€ ์ผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์œ„์˜ ๋กค์ผ€์ดํฌ๋ฅผ [1, 2, 1, 3, 1], [4, 1, 2]์œผ๋กœ ์ž˜๋ผ๋„ ๊ณตํ‰ํ•˜๊ฒŒ ๋‚˜๋‰ฉ๋‹ˆ๋‹ค. ์–ด๋–ค ๊ฒฝ์šฐ์—๋Š” ๋กค์ผ€์ดํฌ๋ฅผ ๊ณตํ‰ํ•˜๊ฒŒ ๋‚˜๋ˆ„์ง€ ๋ชปํ•  ์ˆ˜๋„ ์žˆ์Šต๋‹ˆ๋‹ค.

๋กค์ผ€์ดํฌ์— ์˜ฌ๋ ค์ง„ ํ† ํ•‘๋“ค์˜ ๋ฒˆํ˜ธ๋ฅผ ์ €์žฅํ•œ ์ •์ˆ˜ ๋ฐฐ์—ด topping์ด ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ๋กค์ผ€์ดํฌ๋ฅผ ๊ณตํ‰ํ•˜๊ฒŒ ์ž๋ฅด๋Š” ๋ฐฉ๋ฒ•์˜ ์ˆ˜๋ฅผ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด์ฃผ์„ธ์š”.


๐Ÿ’›์ œํ•œ์‚ฌํ•ญ

  • 1 โ‰ค topping์˜ ๊ธธ์ด โ‰ค 1,000,000
  • 1 โ‰ค topping์˜ ์›์†Œ โ‰ค 10,000

๐Ÿ’š์ž…์ถœ๋ ฅ ์˜ˆ

toppingresult
[1, 2, 1, 3, 1, 4, 1, 2]2
[1, 2, 3, 1, 4]0

๐Ÿ’™์ž…์ถœ๋ ฅ ์˜ˆ ์„ค๋ช…

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

  • ๋กค์ผ€์ดํฌ๋ฅผ [1, 2, 1, 3], [1, 4, 1, 2] ๋˜๋Š” [1, 2, 1, 3, 1], [4, 1, 2]์™€ ๊ฐ™์ด ์ž๋ฅด๋ฉด ์ฒ ์ˆ˜์™€ ๋™์ƒ์€ ๊ฐ๊ฐ ์„ธ ๊ฐ€์ง€ ํ† ํ•‘์„ ๋ง›๋ณผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด ๊ฒฝ์šฐ ๊ณตํ‰ํ•˜๊ฒŒ ๋กค์ผ€์ดํฌ๋ฅผ ๋‚˜๋ˆ„๋Š” ๋ฐฉ๋ฒ•์€ ์œ„์˜ ๋‘ ๊ฐ€์ง€๋งŒ ์กด์žฌํ•ฉ๋‹ˆ๋‹ค.

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

  • ๋กค์ผ€์ดํฌ๋ฅผ ๊ณตํ‰ํ•˜๊ฒŒ ๋‚˜๋ˆŒ ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค.

๐Ÿ’œ๋‚˜์˜ ํ’€์ด

function solution(topping) {
    // ํ† ํ•‘ ๊ฐ€์ง“ ์ˆ˜ ๋ฐ ์ธ๋ฑ์Šค ์ˆ˜๋ฅผ ์ €์žฅํ•  ๋ฐฐ์—ด ์ƒ์„ฑ
    const [bro1Set, bro1Arr, bro2Set, bro2Arr] = [new Set(), [], new Set(), []]
    // ํ† ํ•‘ ์ˆœํšŒ
    topping.forEach((top, i) => {
        // ๋™์ƒ์—๊ฒŒ ํ† ํ•‘ ๋ถ€์—ฌ
        bro1Set.add(top)
        // ํ˜•์˜ ์ธ๋ฑ์Šค๊ฐ€ 0์ธ๊ฒฝ์šฐ // at(-1) === at(0) ์ด๋ฏ€๋กœ ์ƒ๋žต
        if(i !== 0) {
            bro2Set.add(topping.at(-i))
        }
        // ํ† ํ•‘ ๊ฐ€์ง“์ˆ˜ ์ €์žฅ
        bro1Arr.push(bro1Set.size)
        bro2Arr.push(bro2Set.size)
    })
    // ํ† ํ•‘ ๊ฐ€์ง“์ˆ˜๊ฐ€ ๊ฐ™๋‹ค๋ฉด result+1
    return bro1Arr.reduce((acc,cur,i) => 
                          cur === bro2Arr.at(-i-1) ? acc+1 : acc, 0)
}
profile
๋‚ด ์ง€์‹์„ ๊ณต์œ ํ•  ์ˆ˜ ์žˆ๋Š” ๋Œ€๋‹ดํ•จ

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