๐Ÿ… ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค 120876 : ๊ฒน์น˜๋Š” ์„ ๋ถ„์˜ ๊ธธ์ด - Javascript

๋ฌธ์ œ ์„ค๋ช…

์„ ๋ถ„ 3๊ฐœ๊ฐ€ ํ‰ํ–‰ํ•˜๊ฒŒ ๋†“์—ฌ ์žˆ์Šต๋‹ˆ๋‹ค. ์„ธ ์„ ๋ถ„์˜ ์‹œ์ž‘๊ณผ ๋ ์ขŒํ‘œ๊ฐ€ [[start, end], [start, end], [start, end]] ํ˜•ํƒœ๋กœ ๋“ค์–ด์žˆ๋Š” 2์ฐจ์› ๋ฐฐ์—ด lines๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ๋‘ ๊ฐœ ์ด์ƒ์˜ ์„ ๋ถ„์ด ๊ฒน์น˜๋Š” ๋ถ€๋ถ„์˜ ๊ธธ์ด๋ฅผ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด๋ณด์„ธ์š”.

lines๊ฐ€ [[0, 2], [-3, -1], [-2, 1]]์ผ ๋•Œ ๊ทธ๋ฆผ์œผ๋กœ ๋‚˜ํƒ€๋‚ด๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.

example img

์„ ๋ถ„์ด ๋‘ ๊ฐœ ์ด์ƒ ๊ฒน์นœ ๊ณณ์€ [-2, -1], [0, 1]๋กœ ๊ธธ์ด 2๋งŒํผ ๊ฒน์ณ์žˆ์Šต๋‹ˆ๋‹ค.


์ œํ•œ์‚ฌํ•ญ

  • lines์˜ ๊ธธ์ด = 3
  • lines์˜ ์›์†Œ์˜ ๊ธธ์ด = 2
  • ๋ชจ๋“  ์„ ๋ถ„์€ ๊ธธ์ด๊ฐ€ 1 ์ด์ƒ์ž…๋‹ˆ๋‹ค.
  • lines์˜ ์›์†Œ๋Š” [a, b] ํ˜•ํƒœ์ด๋ฉฐ, a, b๋Š” ๊ฐ๊ฐ ์„ ๋ถ„์˜ ์–‘ ๋์  ์ž…๋‹ˆ๋‹ค.
    • -100 โ‰ค a << b โ‰ค 100

์ž…์ถœ๋ ฅ ์˜ˆ

lines result
[[0, 1], [2, 5], [3, 9]] 2
[[-1, 1], [1, 3], [3, 9]] 0
[[0, 5], [3, 9], [1, 10]] 8
  • ์˜ˆ์ œ #1
    ๋‘ ๋ฒˆ์งธ, ์„ธ ๋ฒˆ์งธ ์„ ๋ถ„ [2, 5], [3, 9]๊ฐ€ [3, 5] ๊ตฌ๊ฐ„์— ๊ฒน์ณ์žˆ์œผ๋ฏ€๋กœ 2๋ฅผ return ํ•ฉ๋‹ˆ๋‹ค.

  • ์˜ˆ์ œ #2
    ๊ฒน์นœ ์„ ๋ถ„์ด ์—†์œผ๋ฏ€๋กœ 0์„ return ํ•ฉ๋‹ˆ๋‹ค.

  • ์˜ˆ์ œ #2

    • ์ฒซ ๋ฒˆ์งธ์™€ ๋‘ ๋ฒˆ์งธ ์„ ๋ถ„์ด [3, 5] ๊ตฌ๊ฐ„์—์„œ ๊ฒน์นฉ๋‹ˆ๋‹ค.
    • ์ฒซ ๋ฒˆ์งธ์™€ ์„ธ ๋ฒˆ์งธ ์„ ๋ถ„ [1, 5] ๊ตฌ๊ฐ„์—์„œ ๊ฒน์นฉ๋‹ˆ๋‹ค.
    • ๋‘ ๋ฒˆ์งธ์™€ ์„ธ ๋ฒˆ์งธ ์„ ๋ถ„ [3, 9] ๊ตฌ๊ฐ„์—์„œ ๊ฒน์นฉ๋‹ˆ๋‹ค.
    • ๋”ฐ๋ผ์„œ [1, 9] ๊ตฌ๊ฐ„์— ๋‘ ๊ฐœ ์ด์ƒ์˜ ์„ ๋ถ„์ด ๊ฒน์ณ์žˆ์œผ๋ฏ€๋กœ, 8์„ return ํ•ฉ๋‹ˆ๋‹ค.

ํ’€์ด ๊ณผ์ •

๋ฐฐ์—ด์„ ํ•˜๋‚˜ ์ƒ์„ฑํ•ด ์„ ๋ถ„์ด ๋†“์ด๋Š” ์œ„์น˜์˜ ๊ฐ’์„ 1์”ฉ ์ฆ๊ฐ€์‹œํ‚ค๊ณ , 1์„ ์ดˆ๊ณผํ•˜๋Š” ์š”์†Œ์˜ ์ˆ˜๋ฅผ ๋ฐ˜ํ™˜ํ•˜๋Š” ๊ฐ„๋‹จํ•œ ๋ฐฉ๋ฒ•์œผ๋กœ ์‹œ๋„ํ–ˆ์Šต๋‹ˆ๋‹ค.

function solution(lines) {
  //์„ ๋ถ„์ด ์กด์žฌํ•˜๋Š” ์œ„์น˜๋ฅผ ๋ฐฐ์—ด์— ๋‹ด์Œ
  const line = [];
  for (const [start, end] of lines) {
    for (let i = start; i < end; ++i) {
      line[i] = (line[i] ?? 0) + 1;
    }
  }

  //๋ฐฐ์—ด์˜ ์š”์†Œ ์ค‘ 1์„ ์ดˆ๊ณผํ•˜๋Š” ์š”์†Œ์˜ ์ˆ˜๋ฅผ ๋ฐ˜ํ™˜
  return line.filter((count) => count > 1).length;
}

ํ•˜์ง€๋งŒ ์œ„ ์ฝ”๋“œ๋Š” start์™€ end๊ฐ€ ์Œ์ˆ˜์ธ ๊ฒฝ์šฐ ์ œ๋Œ€๋กœ ์ž‘๋™ํ•˜์ง€ ์•Š์•„ ์‹คํŒจํ–ˆ์Šต๋‹ˆ๋‹ค. ์Œ์ˆ˜๋ฅผ ์ฒ˜๋ฆฌํ•˜๊ธฐ ์œ„ํ•ด ๋ฐฐ์—ด์ด ์•„๋‹Œ ๋งต์— ๋‹ด๋„๋ก ์ˆ˜์ •ํ–ˆ์Šต๋‹ˆ๋‹ค.

function solution(lines) {
  //์„ ๋ถ„์ด ์กด์žฌํ•˜๋Š” ์œ„์น˜๋ฅผ ๋งต์— ๋‹ด์Œ
  const line = new Map();
  for (let [start, end] of lines) {
    for (let i = start; i < end; ++i) {
      line.set(i, (line.get(i) ?? 0) + 1);
    }
  }

  //๋งต์˜ ์š”์†Œ ์ค‘ 1์„ ์ดˆ๊ณผํ•˜๋Š” ์š”์†Œ์˜ ์ˆ˜๋ฅผ ๋ฐ˜ํ™˜
  return [...line.values()].filter((count) => count > 1).length;
}

๋˜๋‹ค๋ฅธ ๋ฐฉ๋ฒ•

๋ฐฐ์—ด ๋Œ€์‹  ๋งต์„ ์‚ฌ์šฉ ๋ฐฉ๋ฒ•์œผ๋กœ ์ด๋ฏธ ํ•ด๊ฒฐํ–ˆ์ง€๋งŒ ๋ฐฐ์—ด์„ ์‚ฌ์šฉํ•˜์ง€ ๋ชปํ–ˆ๋˜ ์ด์œ ๋Š” ์Œ์ˆ˜ ์ธ๋ฑ์Šค๋ฅผ ์ œ๋Œ€๋กœ ์ฒ˜๋ฆฌํ•˜์ง€ ๋ชปํ•˜๊ธฐ ๋•Œ๋ฌธ์ธ๋ฐ, ์ด ๋ฌธ์ œ์˜ ๊ฒฝ์šฐ line์˜ ์š”์†Œ์˜ ๊ฐ’์ด -100 ์ด์ƒ์œผ๋กœ ์ œํ•œ ๋˜์–ด์žˆ๊ธฐ ๋•Œ๋ฌธ์— ์•„๋ž˜์™€ ๊ฐ™์ด ์ธ๋ฑ์Šค์— 100์„ ๋”ํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ๋„ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

function solution(lines) {
  //์„ ๋ถ„์ด ์กด์žฌํ•˜๋Š” ์œ„์น˜๋ฅผ ๋ฐฐ์—ด์— ๋‹ด์Œ
  const line = [];
  for (const [start, end] of lines) {
    for (let i = start; i < end; ++i) {
      //์Œ์ˆ˜๋ฅผ ์ฒ˜๋ฆฌํ•˜๊ธฐ ์œ„ํ•ด ์ธ๋ฑ์Šค์— 100์„ ๋”ํ•จ (-100 ์ด์ƒ์ด๊ธฐ ๋•Œ๋ฌธ)
      line[i + 100] = (line[i + 100] ?? 0) + 1;
    }
  }

  //๋ฐฐ์—ด์˜ ์š”์†Œ ์ค‘ 1์„ ์ดˆ๊ณผํ•˜๋Š” ์š”์†Œ์˜ ์ˆ˜๋ฅผ ๋ฐ˜ํ™˜
  return line.filter((count) => count > 1).length;
}