๐Ÿ›ฐ[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ๊ธฐ์ง€๊ตญ ์„ค์น˜

Chobbyยท2022๋…„ 9์›” 13์ผ
1

Programmers

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

ํ•ด๋‹น ํ’€์ด๋Š” eunchanee๋‹˜์˜ tistory๋ฅผ ์ฐธ๊ณ ํ•˜์—ฌ ์ œ์ž‘๋˜์—ˆ์Œ์„ ๋ฏธ๋ฆฌ ๋ฐํž™๋‹ˆ๋‹ค.

๋ฌธ์ œ ์„ค๋ช…

N๊ฐœ์˜ ์•„ํŒŒํŠธ๊ฐ€ ์ผ๋ ฌ๋กœ ์ญ‰ ๋Š˜์–ด์„œ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด ์ค‘์—์„œ ์ผ๋ถ€ ์•„ํŒŒํŠธ ์˜ฅ์ƒ์—๋Š” 4g ๊ธฐ์ง€๊ตญ์ด ์„ค์น˜๋˜์–ด ์žˆ์Šต๋‹ˆ๋‹ค. ๊ธฐ์ˆ ์ด ๋ฐœ์ „ํ•ด 5g ์ˆ˜์š”๊ฐ€ ๋†’์•„์ ธ 4g ๊ธฐ์ง€๊ตญ์„ 5g ๊ธฐ์ง€๊ตญ์œผ๋กœ ๋ฐ”๊พธ๋ ค ํ•ฉ๋‹ˆ๋‹ค. ๊ทธ๋Ÿฐ๋ฐ 5g ๊ธฐ์ง€๊ตญ์€ 4g ๊ธฐ์ง€๊ตญ๋ณด๋‹ค ์ „๋‹ฌ ๋ฒ”์œ„๊ฐ€ ์ข์•„, 4g ๊ธฐ์ง€๊ตญ์„ 5g ๊ธฐ์ง€๊ตญ์œผ๋กœ ๋ฐ”๊พธ๋ฉด ์–ด๋–ค ์•„ํŒŒํŠธ์—๋Š” ์ „ํŒŒ๊ฐ€ ๋„๋‹ฌํ•˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด 11๊ฐœ์˜ ์•„ํŒŒํŠธ๊ฐ€ ์ญ‰ ๋Š˜์–ด์„œ ์žˆ๊ณ , [4, 11] ๋ฒˆ์งธ ์•„ํŒŒํŠธ ์˜ฅ์ƒ์—๋Š” 4g ๊ธฐ์ง€๊ตญ์ด ์„ค์น˜๋˜์–ด ์žˆ์Šต๋‹ˆ๋‹ค. ๋งŒ์•ฝ ์ด 4g ๊ธฐ์ง€๊ตญ์ด ์ „ํŒŒ ๋„๋‹ฌ ๊ฑฐ๋ฆฌ๊ฐ€ 1์ธ 5g ๊ธฐ์ง€๊ตญ์œผ๋กœ ๋ฐ”๋€” ๊ฒฝ์šฐ ๋ชจ๋“  ์•„ํŒŒํŠธ์— ์ „ํŒŒ๋ฅผ ์ „๋‹ฌํ•  ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค. (์ „ํŒŒ์˜ ๋„๋‹ฌ ๊ฑฐ๋ฆฌ๊ฐ€ W์ผ ๋•, ๊ธฐ์ง€๊ตญ์ด ์„ค์น˜๋œ ์•„ํŒŒํŠธ๋ฅผ ๊ธฐ์ค€์œผ๋กœ ์ „ํŒŒ๋ฅผ ์–‘์ชฝ์œผ๋กœ W๋งŒํผ ์ „๋‹ฌํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.)

  • ์ดˆ๊ธฐ์—, 1, 2, 6, 7, 8, 9๋ฒˆ์งธ ์•„ํŒŒํŠธ์—๋Š” ์ „ํŒŒ๊ฐ€ ์ „๋‹ฌ๋˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค.

  • 1, 7, 9๋ฒˆ์งธ ์•„ํŒŒํŠธ ์˜ฅ์ƒ์— ๊ธฐ์ง€๊ตญ์„ ์„ค์น˜ํ•  ๊ฒฝ์šฐ, ๋ชจ๋“  ์•„ํŒŒํŠธ์— ์ „ํŒŒ๋ฅผ ์ „๋‹ฌํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

  • ๋” ๋งŽ์€ ์•„ํŒŒํŠธ ์˜ฅ์ƒ์— ๊ธฐ์ง€๊ตญ์„ ์„ค์น˜ํ•˜๋ฉด ๋ชจ๋“  ์•„ํŒŒํŠธ์— ์ „ํŒŒ๋ฅผ ์ „๋‹ฌํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์ด๋•Œ, ์šฐ๋ฆฌ๋Š” 5g ๊ธฐ์ง€๊ตญ์„ ์ตœ์†Œ๋กœ ์„ค์น˜ํ•˜๋ฉด์„œ ๋ชจ๋“  ์•„ํŒŒํŠธ์— ์ „ํŒŒ๋ฅผ ์ „๋‹ฌํ•˜๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ์œ„์˜ ์˜ˆ์‹œ์—์„  ์ตœ์†Œ 3๊ฐœ์˜ ์•„ํŒŒํŠธ ์˜ฅ์ƒ์— ๊ธฐ์ง€๊ตญ์„ ์„ค์น˜ํ•ด์•ผ ๋ชจ๋“  ์•„ํŒŒํŠธ์— ์ „ํŒŒ๋ฅผ ์ „๋‹ฌํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์•„ํŒŒํŠธ์˜ ๊ฐœ์ˆ˜ N, ํ˜„์žฌ ๊ธฐ์ง€๊ตญ์ด ์„ค์น˜๋œ ์•„ํŒŒํŠธ์˜ ๋ฒˆํ˜ธ๊ฐ€ ๋‹ด๊ธด 1์ฐจ์› ๋ฐฐ์—ด stations, ์ „ํŒŒ์˜ ๋„๋‹ฌ ๊ฑฐ๋ฆฌ W๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ๋ชจ๋“  ์•„ํŒŒํŠธ์— ์ „ํŒŒ๋ฅผ ์ „๋‹ฌํ•˜๊ธฐ ์œ„ํ•ด ์ฆ์„คํ•ด์•ผ ํ•  ๊ธฐ์ง€๊ตญ ๊ฐœ์ˆ˜์˜ ์ตœ์†Ÿ๊ฐ’์„ ๋ฆฌํ„ดํ•˜๋Š” solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด์ฃผ์„ธ์š”

์ œํ•œ์‚ฌํ•ญ

  • N: 200,000,000 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜
  • stations์˜ ํฌ๊ธฐ: 10,000 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜
  • stations๋Š” ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌ๋˜์–ด ์žˆ๊ณ , ๋ฐฐ์—ด์— ๋‹ด๊ธด ์ˆ˜๋Š” N๋ณด๋‹ค ๊ฐ™๊ฑฐ๋‚˜ ์ž‘์€ ์ž์—ฐ์ˆ˜์ž…๋‹ˆ๋‹ค.
  • W: 10,000 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜

์ž…์ถœ๋ ฅ ์˜ˆ

NstationsWanswer
11[4, 11]13
16[9]23

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

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

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

  • ์ดˆ๊ธฐ์—, 1~6, 12~16๋ฒˆ์งธ ์•„ํŒŒํŠธ์—๋Š” ์ „ํŒŒ๊ฐ€ ์ „๋‹ฌ๋˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค.

  • 3, 6, 14๋ฒˆ์งธ ์•„ํŒŒํŠธ ์˜ฅ์ƒ์— ๊ธฐ์ง€๊ตญ์„ ์„ค์น˜ํ•  ๊ฒฝ์šฐ ๋ชจ๋“  ์•„ํŒŒํŠธ์— ์ „ํŒŒ๋ฅผ ์ „๋‹ฌํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

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

function solution(n, stations, w) {
    let result = 0
    let start = 1
    let index = 0
    let range = [stations[index]-w,stations[index]+w]
    while(start <= n) {
        // ๊ธฐ์ง€๊ตญ ๋ฒ”์œ„ ๋‚ด์— ์žˆ๋Š” ๊ฒฝ์šฐ
        if(start >= stations[index]-w && start <= stations[index]+w) {
            start = stations[index]+w
            index++
        // ๊ธฐ์ง€๊ตญ ์„ค์น˜ ํ•„์š”
        } else {
            // ์ด์ „, ์ดํ›„ ๋ฒ”์œ„๊ฐ€ ์ค‘๋ณต๋˜์ง€ ์•Š๋„๋ก ๋ฒ”์œ„์— 2๋ฐฐ๋ฅผ ๊ณฑํ•ด ๋‹ค์Œ ์•„ํŒŒํŠธ๋กœ ์ด๋™
            start += w*2
            result++
        }
        start++
    }
    return result
}

๋ฒ”์œ„๊ฐ€ ํฌ์ง€ ์•Š์•„ Brute Force๋กœ๋„ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ์˜€๋‹ค.

์ดํ•ดํ•˜๊ธฐ ํž˜๋“ค์—ˆ๋˜ ๋ถ€๋ถ„์€ ํ•ด๋‹น

start+=w*2

๋กœ ์–ด์งธ์„œ ๋ฒ”์œ„์˜ 2๋ฐฐ๋งŒํผ์„ start์— ๋”ํ•˜๋Š”๊ฑฐ์ง€? ๋ผ๋Š” ์ƒ๊ฐ์„ ํ–ˆ์—ˆ๋Š”๋ฐ

์ด๋Š” ์•ž์œผ๋กœ๋งŒ ํ•ด๋‹น๋˜๋Š” ๋ฒ”์œ„๊ฐ€ ์•„๋‹Œ ๋‹ค์Œ ์•„ํŒŒํŠธ ๋‹จ์ง€์˜ ๋’ค๋กœ ์ค‘๋ณต๋˜๋Š” ๊ฒฝ์šฐ๊ฐ€ ์—†๋„๋ก ๋ฒ”์œ„์˜ 2๋ฐฐ์ธ ์•ž๋’ค๋ฅผ ์ง€์ •ํ•ด ๋”ํ•ด์ฃผ์—ˆ๋‹ค๋Š” ๊ฒƒ์„ ์•Œ๊ฒŒ๋˜์—ˆ์Œ

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

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