๋”ฐํŒŒ๐Ÿ•
Hwaiian Pizza IT Pub
๋”ฐํŒŒ๐Ÿ•
  • ALL (62)
    • Front-End (13)
      • HTML & CSS (2)
      • JavaScript (7)
      • React (2)
      • TypeScript (0)
      • Jquery (0)
      • Git (1)
      • Editor (0)
    • Algorithms (44)
      • Baekjoon (28)
      • Programmers (13)
      • Algorithms (3)
    • Computer Science (0)
      • Math (0)
    • Conference (1)
    • Life (3)
      • Book (0)
hELLO ยท Designed By ์ •์ƒ์šฐ.
๋”ฐํŒŒ๐Ÿ•
Algorithms/Baekjoon

[JS] ๋ฐฑ์ค€ 1931 ๋ฒˆ : ํšŒ์˜์‹ค ๋ฐฐ์ •(feat.๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜)

[JS] ๋ฐฑ์ค€ 1931 ๋ฒˆ : ํšŒ์˜์‹ค ๋ฐฐ์ •(feat.๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜)
Algorithms/Baekjoon

[JS] ๋ฐฑ์ค€ 1931 ๋ฒˆ : ํšŒ์˜์‹ค ๋ฐฐ์ •(feat.๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜)

2022. 5. 24. 21:40
๋ฐ˜์‘ํ˜•

 

 

Question

 

๋ฐฑ์ค€ 1931๋ฒˆ : ํšŒ์˜์‹ค ๋ฐฐ์ •

ํ•œ ๊ฐœ์˜ ํšŒ์˜์‹ค์ด ์žˆ๋Š”๋ฐ ์ด๋ฅผ ์‚ฌ์šฉํ•˜๊ณ ์ž ํ•˜๋Š” N๊ฐœ์˜ ํšŒ์˜์— ๋Œ€ํ•˜์—ฌ ํšŒ์˜์‹ค ์‚ฌ์šฉํ‘œ๋ฅผ ๋งŒ๋“ค๋ ค๊ณ  ํ•œ๋‹ค. ๊ฐ ํšŒ์˜ I์— ๋Œ€ํ•ด ์‹œ์ž‘์‹œ๊ฐ„๊ณผ ๋๋‚˜๋Š” ์‹œ๊ฐ„์ด ์ฃผ์–ด์ ธ ์žˆ๊ณ , ๊ฐ ํšŒ์˜๊ฐ€ ๊ฒน์น˜์ง€ ์•Š๊ฒŒ ํ•˜๋ฉด์„œ ํšŒ์˜์‹ค์„ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋Š” ํšŒ์˜์˜ ์ตœ๋Œ€ ๊ฐœ์ˆ˜๋ฅผ ์ฐพ์•„๋ณด์ž. ๋‹จ, ํšŒ์˜๋Š” ํ•œ๋ฒˆ ์‹œ์ž‘ํ•˜๋ฉด ์ค‘๊ฐ„์— ์ค‘๋‹จ๋  ์ˆ˜ ์—†์œผ๋ฉฐ ํ•œ ํšŒ์˜๊ฐ€ ๋๋‚˜๋Š” ๊ฒƒ๊ณผ ๋™์‹œ์— ๋‹ค์Œ ํšŒ์˜๊ฐ€ ์‹œ์ž‘๋  ์ˆ˜ ์žˆ๋‹ค. ํšŒ์˜์˜ ์‹œ์ž‘์‹œ๊ฐ„๊ณผ ๋๋‚˜๋Š” ์‹œ๊ฐ„์ด ๊ฐ™์„ ์ˆ˜๋„ ์žˆ๋‹ค. ์ด ๊ฒฝ์šฐ์—๋Š” ์‹œ์ž‘ํ•˜์ž๋งˆ์ž ๋๋‚˜๋Š” ๊ฒƒ์œผ๋กœ ์ƒ๊ฐํ•˜๋ฉด ๋œ๋‹ค.

 

 

1931๋ฒˆ: ํšŒ์˜์‹ค ๋ฐฐ์ •

(1,4), (5,7), (8,11), (12,14) ๋ฅผ ์ด์šฉํ•  ์ˆ˜ ์žˆ๋‹ค.

www.acmicpc.net

 

์ž…๋ ฅ

์ฒซ์งธ ์ค„์— ํšŒ์˜์˜ ์ˆ˜ N(1 โ‰ค N โ‰ค 100,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N+1 ์ค„๊นŒ์ง€ ๊ฐ ํšŒ์˜์˜ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์ง€๋Š”๋ฐ ์ด๊ฒƒ์€ ๊ณต๋ฐฑ์„ ์‚ฌ์ด์— ๋‘๊ณ  ํšŒ์˜์˜ ์‹œ์ž‘์‹œ๊ฐ„๊ณผ ๋๋‚˜๋Š” ์‹œ๊ฐ„์ด ์ฃผ์–ด์ง„๋‹ค. ์‹œ์ž‘ ์‹œ๊ฐ„๊ณผ ๋๋‚˜๋Š” ์‹œ๊ฐ„์€ 231-1๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜ ๋˜๋Š” 0์ด๋‹ค.

 

์ถœ๋ ฅ

์ฒซ์งธ ์ค„์— ์ตœ๋Œ€ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋Š” ํšŒ์˜์˜ ์ตœ๋Œ€ ๊ฐœ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

 

์ž…๋ ฅ์˜ˆ์‹œ

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

 

์ถœ๋ ฅ์˜ˆ์‹œ

4

 


 

My Code

 

 

์ •๋ ฌ์„ ์ž˜๋ชป ์ƒ๊ฐํ–ˆ๋‹ค ๐Ÿคฏ

์ •๋ ฌ์ด ์–ด๋– ๋ƒ์— ๋”ฐ๋ผ ๋‹ต์ด ๋‹ฌ๋ผ์กŒ๋‹ค.

์ฒ˜์Œ์—๋Š” ์‹œ์ž‘ํ•˜๋Š” ์‹œ๊ฐ„์„ ๊ธฐ์ค€์œผ๋กœ ์ •๋ ฌ์„ ํ–ˆ๋‹ค.

๊ฒฐ๊ณผ๋Š” ํ‹€๋ ธ๋‹ค๐Ÿ˜

const fs = require('fs');
const input = fs.readFileSync('example.txt').toString().trim().split('\n');

let num = Number(input.shift());

// ์ˆซ์ž ์ด์ค‘๋ฐฐ์—ด๋กœ ์ „ํ™˜
let arr = [];
for (let i = 0; i < num; i++) {
    arr.push(input[i].split(' ').map(Number))
}

// ๋ฐฐ์—ด ์ •๋ ฌ
arr = arr.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]);

let result = 1;
let end = arr[0][1];

for (let i = 1; i < arr.length; i++) {
    let [from, to] = arr[i];
    if (from >= end) {
        end = to;
        result++;
    }
}

console.log(result)

 

 

WHY? (ํ‹€๋ฆฐ์ด์œ )

 

์‹œ์ž‘ํ•˜๋Š” ์‹œ๊ฐ„์„ ์ค‘์ ์œผ๋กœ ์ •๋ ฌ์„ ํ•˜๋ฉด ์ตœ๋Œ€๋กœ ๋งŽ์ด ํšŒ์˜๋ฅผ ํ•  ์ˆ˜ ์žˆ๋Š” ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•  ์ˆ˜ ์—†๋‹ค.

๋๋‚˜๋Š” ์‹œ๊ฐ„์ด ๋“ค์‘ฅ ๋‚ ์‘ฅ ํ•˜๊ธฐ ๋•Œ๋ฌธ์—

๊ทธ๋‹ค์Œ ํ„ด์œผ๋กœ ๋„˜์–ด๊ฐ€๋ฉด ๋” ๋นจ๋ฆฌ ๋๋‚˜๋Š” ์‹œ๊ฐ„๋Œ€๊ฐ€ ์žˆ์Œ์—๋„ ๋ถˆ๊ตฌํ•˜๊ณ  ๋†“์น˜๊ณ  ๋งŒ๋‹ค.

๋”ฐ๋ผ์„œ ์ตœ๋Œ€์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•  ์ˆ˜ ์—†๋‹ค.

 

๋๋‚˜๋Š” ์‹œ๊ฐ„์„ ๊ธฐ์ ์œผ๋กœ ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌ์„ ํ•ด์•ผ ํ–ˆ๋‹ค.

 

 

 

์ˆ˜์ •ํ•œ ์ฝ”๋“œ

const fs = require('fs');
const input = fs.readFileSync('example.txt').toString().trim().split('\n');

let num = Number(input.shift());

// ์ˆซ์ž ์ด์ค‘๋ฐฐ์—ด๋กœ ๋ณ€ํ™˜
let arr = [];
for (let i = 0; i < num; i++) {
    arr.push(input[i].split(' ').map(Number))
}


// ๋ฐฐ์—ด ์ •๋ ฌ (๋๋‚˜๋Š” ์‹œ๊ฐ„ ๊ธฐ์ )
arr = arr.sort((a, b) => a[1] === b[1] ? a[0] - b[0] : a[1] - b[1]);

let result = 1;
let end = arr[0][1];

for (let i = 1; i < arr.length; i++) {
    let [from, to] = arr[i];
    if (from >= end) {
        end = to;
        result++;
    }
}

console.log(result)

๋งž์•˜์Šต๋‹ˆ๋‹ค!!

 

 

 

HOW? (ํ’€์ด๋ฐฉ๋ฒ•)

 

  • ํƒ์š•์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋‹ต๊ฒŒ ํ˜„์žฌ ์ƒํ™ฉ์—์„œ ์ตœ์„ ์˜ ์„ ํƒ์ด ๋˜๋Š” ๊ฒƒ์„ ํ•œ๋‹ค.
  • ์ •๋ ฌํ•œ ์‹œ๊ฐ„์— ๊ฐ€์žฅ ์ฒ˜์Œ ์‹œ๊ฐ„๋Œ€๋ถ€ํ„ฐ ์‹œ์ž‘ํ•œ๋‹ค.
  • ๋๋‚˜๋Š” ์‹œ๊ฐ„์˜ ๋ณ€์ˆ˜๋ฅผ ์ฒ˜์Œ ์‹œ๊ฐ„๋Œ€์˜ ๋๋‚˜๋Š” ์‹œ๊ฐ„์œผ๋กœ ์ง€์ •ํ•œ๋‹ค.
  • ๊ทธ๋‹ค์Œ ์‹œ๊ฐ„๋Œ€๋ถ€ํ„ฐ ๋๊นŒ์ง€ for๋ฌธ์„ ๋Œ๋ ค์ค€๋‹ค.
  • ๋๋‚˜๋Š” ์‹œ๊ฐ„๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™์€ ์‹œ์ž‘ํ•˜๋Š” ์‹œ๊ฐ„์ด ์žˆ๋‹ค๋ฉด ๋‹ค์Œ ํšŒ์˜๋กœ ๋„˜๊ฒจ์ค€๋‹ค.
  • ํšŒ์˜๊ฐ€ ๋„˜๊ฒจ์งˆ ๋•Œ๋งˆ๋‹ค result๊ฐ€ +1์ด ๋˜๋„๋ก ํ•œ๋‹ค.
  • result๋ฅผ ์ถœ๋ ฅํ•˜๋ฉด ๋!

 

 

 

 

๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ๊ด€ํ•œ ์ž์„ธํ•œ ๋‚ด์šฉ์€ ์ด ํฌ์ŠคํŒ…์„ ๋ณด๋ฉด ํ™•์ธํ•  ์ˆ˜ ์žˆ๋‹ค.

 

[์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ธฐ๋ณธ] ํƒ์š•(Greedy) ์•Œ๊ณ ๋ฆฌ์ฆ˜

1. ํƒ์š• ์•Œ๊ณ ๋ฆฌ์ฆ˜ (Greedy Algorithms) ํƒ์š•(Greedy)์€ ๋ง ๊ทธ๋Œ€๋กœ ์ง€๋‚˜์น˜๊ฒŒ ์š•์‹ฌ์ด ๋งŽ๋‹ค๋Š” ๋œป์ด๋‹ค. ๊ทธ๋ ‡๋‹ค๋ฉด ํƒ์š•์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๋ฌด์—‡์ผ๊นŒ? ๋ฏธ๋ž˜๋ฅผ ์ƒ๊ฐํ•˜์ง€ ์•Š๊ณ  ํ˜„์žฌ์˜ ๋‹จ๊ณ„์—์„œ ๊ฐ€์žฅ ์ตœ์„ ์˜ ์„ ํƒ์„ ํ•˜๋Š”

hawaiian-pizza-it.tistory.com

 

 

 

๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•ด๋„ ์ƒํ™ฉ์— ๋งž๊ฒŒ ๋งŒ๋“ค์–ด์„œ ์‚ฌ์šฉํ•ด์•ผ ํ•œ๋‹ค๋Š” ๊ฒƒ์„ ๊นจ๋‹ฌ์•˜๋‹ค.

๋‚˜๋Š” ๋ถ„๋ช… ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ–ˆ๋Š”๋ฐ ์™œ ์•ˆ ํ’€๋ฆฌ์ง€?

์ƒ๊ฐํ–ˆ๋˜ ๋ถ€๋ถ„์ด ํ’€๋ ค์„œ ๋‹คํ–‰์ด๋‹ค.

๋”ฐ๋ด‰ ๊ตฌ๊ธ€๋ง์—๊ฒŒ ์–ธ์ œ๋‚˜ ๊ณ ๋ง™๋‹ค.

 

 

 

์š”์ฆ˜ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ํ‘ธ๋Š” ๋‚ด ๋ชจ์Šต

ํ’€๋ ค๋„ ์ดํ•ด๊ฐ€ ์•ˆ ๋ผ์„œ ์›ƒ๊ธฐ๋‹ค.

๊ทธ๋ž˜๋„ ๋๊นŒ์ง€ ์ดํ•ดํ•˜๋ ค๊ณ  ํ•œ๋‹ค.

 

 

 

๋ฐ˜์‘ํ˜•
์ €์ž‘์žํ‘œ์‹œ ๋น„์˜๋ฆฌ ๋ณ€๊ฒฝ๊ธˆ์ง€ (์ƒˆ์ฐฝ์—ด๋ฆผ)

'Algorithms > Baekjoon' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[JS] ๋ฐฑ์ค€ 10815๋ฒˆ : ์ˆซ์ž ์นด๋“œ  (0) 2022.06.05
[JS] ๋ฐฑ์ค€ 10841๋ฒˆ : ๋‚˜์ด์ˆœ ์ •๋ ฌ  (0) 2022.05.28
[JS] ๋ฐฑ์ค€ 10870๋ฒˆ : ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜ 5  (0) 2022.05.16
[JS] ๋ฐฑ์ค€ 10872๋ฒˆ : ์žฌ๊ท€  (0) 2022.05.15
[JS] ๋ฐฑ์ค€ 2108๋ฒˆ : ํ†ต๊ณ„ํ•™  (0) 2022.05.13
  • Question
  • My Code
  • WHY? (ํ‹€๋ฆฐ์ด์œ )
  • HOW? (ํ’€์ด๋ฐฉ๋ฒ•)
'Algorithms/Baekjoon' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [JS] ๋ฐฑ์ค€ 10815๋ฒˆ : ์ˆซ์ž ์นด๋“œ
  • [JS] ๋ฐฑ์ค€ 10841๋ฒˆ : ๋‚˜์ด์ˆœ ์ •๋ ฌ
  • [JS] ๋ฐฑ์ค€ 10870๋ฒˆ : ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜ 5
  • [JS] ๋ฐฑ์ค€ 10872๋ฒˆ : ์žฌ๊ท€
๋”ฐํŒŒ๐Ÿ•
๋”ฐํŒŒ๐Ÿ•
์ €์ชฝ ์†๋‹˜์ด ๋ณด๋‚ด์‹  ์—๋Ÿฌ์ž…๋‹ˆ๋‹ค. ๋””๋ฒ„๊น… ํ•˜์‹œ๊ฒ ์Šต๋‹ˆ๊นŒ?๐Ÿน

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”

๋‹จ์ถ•ํ‚ค

๋‚ด ๋ธ”๋กœ๊ทธ

๋‚ด ๋ธ”๋กœ๊ทธ - ๊ด€๋ฆฌ์ž ํ™ˆ ์ „ํ™˜
Q
Q
์ƒˆ ๊ธ€ ์“ฐ๊ธฐ
W
W

๋ธ”๋กœ๊ทธ ๊ฒŒ์‹œ๊ธ€

๊ธ€ ์ˆ˜์ • (๊ถŒํ•œ ์žˆ๋Š” ๊ฒฝ์šฐ)
E
E
๋Œ“๊ธ€ ์˜์—ญ์œผ๋กœ ์ด๋™
C
C

๋ชจ๋“  ์˜์—ญ

์ด ํŽ˜์ด์ง€์˜ URL ๋ณต์‚ฌ
S
S
๋งจ ์œ„๋กœ ์ด๋™
T
T
ํ‹ฐ์Šคํ† ๋ฆฌ ํ™ˆ ์ด๋™
H
H
๋‹จ์ถ•ํ‚ค ์•ˆ๋‚ด
Shift + /
โ‡ง + /

* ๋‹จ์ถ•ํ‚ค๋Š” ํ•œ๊ธ€/์˜๋ฌธ ๋Œ€์†Œ๋ฌธ์ž๋กœ ์ด์šฉ ๊ฐ€๋Šฅํ•˜๋ฉฐ, ํ‹ฐ์Šคํ† ๋ฆฌ ๊ธฐ๋ณธ ๋„๋ฉ”์ธ์—์„œ๋งŒ ๋™์ž‘ํ•ฉ๋‹ˆ๋‹ค.