[JavaScript] 백준 2457번: 공주님의 정원

난이도 : 골드 3
알고리즘 유형 : 그리드 알고리즘
문제 링크 : https://www.acmicpc.net/problem/2457

 

 

문제

오늘은 공주님이 태어난 경사스러운 날이다. 왕은 이 날을 기념하기 위해 늘 꽃이 피어있는 작은 정원을 만들기로 결정했다.

총 N개의 꽃이 있는 데, 꽃은 모두 같은 해에 피어서 같은 해에 진다. 하나의 꽃은 피는 날과 지는 날이 정해져 있다. 예를 들어, 5월 8일 피어서 6월 13일 지는 꽃은 5월 8일부터 6월 12일까지는 꽃이 피어 있고, 6월 13일을 포함하여 이후로는 꽃을 볼 수 없다는 의미이다. (올해는 4, 6, 9, 11월은 30일까지 있고, 1, 3, 5, 7, 8, 10, 12월은 31일까지 있으며, 2월은 28일까지만 있다.)

이러한 N개의 꽃들 중에서 다음의 두 조건을 만족하는 꽃들을 선택하고 싶다.

1. 공주가 가장 좋아하는 계절인 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 한다.
2. 정원이 넓지 않으므로 정원에 심는 꽃들의 수를 가능한 적게 한다. 

입력

첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, 3 8 7 31은 꽃이 3월 8일에 피어서 7월 31일에 진다는 것을 나타낸다. 

출력

첫째 줄에 선택한 꽃들의 최소 개수를 출력한다. 만약 두 조건을 만족하는 꽃들을 선택할 수 없다면 0을 출력한다.

 

 

풀이 과정

• 모두 같은 해에 피어나 같은 해에 진다
    -> 입력에 12월 1일 부터 4월 1일 처럼 해를 넘어가는 입력은 주어지지 않음.
• 입력은 피는 날과 지는 날이 주어지는데, 지는 날에는 꽃을 볼 수 없다.
    -> 입력이 1 1 5 31 이면 5월 31일에는 꽃이 피어있지 않음.
          & 가장 늦게 지는 꼿이 11월 30일이라면 조건에 부합하지 않음.
• 조건을 만족하는 꽃이 없다면 0을 출력한다.
• 로직 과정
     메인 생각 : 조건에 부합하는 꽃들 중 가장 늦게 지는 꽃을 선택함.
  
  
  1. 꽃이 피는 날이 빠른 순으로 꽃들의 기간을 정렬함.
  2. while문을 통해 조건에 부합하는 꽃들 중 가장 늦게 지는 꽃을 계속 선택함.
     • 3월 1일 부터 꽃이 피어있어야 함으로, 처음 꽃이 지는 기간(s)을 3월 1일로 선택함.
     • s의 기간보다 이전에 피어난 꽃들 중 가장 늦게 지는 꽃을 선택함.
     • 위에 선택한 꽃이 지는 날로 s의 값을 갱신.
     • 위의 두 과정을 s가 11월 30일보다 커질 때까지 반복.
     • 중간에 s가 갱신되지 않으면 조건을 만족하는 꽃이 없다는 의미이므로 while문 나감.
  3. 갱신 완료된 s의 값이 11월 30일보다 큰지 확인.
     • 11월 30일 보다 크면 선택된 꽃들의 갯수 출력.
     • 11월 30일 보다 크지 않다면 0 출력.

 

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : 'BACKJOON_002457.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split(/\r?\n/);
input.shift();

const arr = input.map((data) => {
  const [sm, sd, em, ed] = data.split(' ').map(Number);
  return [(sm - 1) * 31 + sd, (em - 1) * 31 + ed];
});

const sortedArr = arr.sort((a, b) => (a[0] - b[0]));
const len = sortedArr.length;

let s = 2 * 31 + 1, idx=0, maxE=0, prevIdx=0;
const e = 11 * 31 + 1;

let answer = 0;

while( s < e && idx < len ){
  while(idx < len  && sortedArr[idx][0] <= s){
    maxE = maxE < sortedArr[idx][1] ? sortedArr[idx][1] : maxE;
    idx++;
  }
  answer += 1;
  s = maxE;

  if(prevIdx === idx) break;
  prevIdx = idx;
}

if(e <= s)
  console.log(answer);
else 
  console.log(0);

 

 

회고

언제나 문제를 주의깊게 읽어야 된다고 생각한다. 하지만... 글이 눈에 들어오지 않을 때가 있다.. 오늘도 조건을 만족하는 꽃이 없다면 0을 출력한다는 문구와 지는 날은 꽃이 없다는 문구를 유의하지 못하여 틀린 점을 찾는데 시간을 소요하였다...ㅠㅠ
고등학교때 문제 지문 읽을 때도 지금도 문제를 잘 읽어야 하는데 주의력이 부족한 것 같다.....
앞으로는 문제를 풀기 전에 문제 설명을 요약하는 주석을 달아봐야겠다!!