[Swift Algorithm] 공주님의 정원 BOJ #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개의 꽃들 중에서 위의 두 조건을 만족하는, 즉 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 꽃들을 선택할 때, 선택한 꽃들의 최소 개수를 출력하는 프로그램을 작성하시오. 

 

입력

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

 

출력

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

 

입출력 예제

입력

10
2 15 3 23
4 12 6 5
5 2 5 31
9 14 12 24
6 15 9 3
6 3 6 15
2 28 4 25
6 15 9 27
10 5 12 31
7 14 9 1

출력

5

 

내 문제 풀이

import Foundation

let n = Int(readLine()!)!
var flowers = [[Int]]() // [[피는 시기, 지는 시기]]

for _ in 0..<n {
    let tmp = readLine()!.split(separator: " ").map{Int(String($0))!}
    let s = tmp[0] * 100 + tmp[1] // 피는 시기
    let e = tmp[2] * 100 + tmp[3] // 지는 시기
    if e >= 301 { 
        if s <= 301 { flowers.append([301, e]) }
        else { flowers.append([s, e]) }
    }
}

flowers.sort(by: {$0[0] < $1[0]}) // 피는 시기를 기준으로 오름차순 정렬

var start = 301 // 꽃이 피어야 하는 시기를 저장하기 위한 변수
var max = 0 // 선택한 꽃들 중 가장 늦게 지는 시기를 저장하기 위한 변수
var answer = 0 // 선택한 꽃의 개수를 카운트하는 변수

for i in 0..<n {
    // 입력받은 꽃의 개수가 1개 이하일 경우
    if flowers.count <= 1 {
        if flowers.count == 0 { break }
        else {
            if flowers[0][0] == 301 && flowers[0][1] > 1130 { answer = 1; break }
            else { break }
        }
    }
    
    // 꽃이 피는 시기가 start 이전일 경우
    if flowers[i][0] <= start {
        if flowers[i][1] > max { max = flowers[i][1] }
        
        // 마지막 반복일 경우
        if i == n-1 {
            if max > 1130 { answer += 1; break }
            else { answer = 0; break }
        }
        
        // 다음 꽃의 시작 시기가 start 이후일 경우 시행되어야 할 업데이트
        else if flowers[i+1][0] > start {
            answer += 1
            start = max
            if start > 1130 { break }
        }
    }
    
    // 꽃이 피는 시기가 start 이후일 경우
    else { answer = 0; break }
}

print(answer)

👉 이 문제는 생각해줘야할 예외도 많은데 일 단위의 날짜가 개입되어있다보니 더 힘든 문제였던 것 같다.

따라서 문제를 풀기 전 더욱더 정확히! 필요한 풀이 과정과 예외를 정리해보자.

(우선, 나는 날짜들의 대소관계를 쉽게하기 위해 3월 1일은 301, 12월 1일은 1201. 이런 식으로 [월*100 + 일]의 연산을 통해 재정립했다는 것을 명시한다.)

1. 끝나는 날이 301 이하인 꽃들은 입력받지 않는다. (정확히는, 배열에 추가하지 않는다.)
2. 1의 경우를 제외한 301보다 피는 시기가 빠른 꽃들은 시작 시기를 301로 바꿔준다.
3. 꽃이 피는 시기를 기준으로 꽃 배열을 오름차순 정렬한다.
4. 피는 시기가 301인 꽃부터 검색, 301에 피는 꽃 중 지는 시기가 가장 늦는 꽃을 선택한다. (카운트)
5. 4번에서 선택한 꽃의 지는 시기를 다시 시작하는 시기로 저장한다. (만약 그 날이 1201 이상이면 바로 끝!)
6. 3, 4, 5 반복

내가 코드를 작성하기 전 정리했던 노트를 그대로 옮겨왔다.

이렇게 풀이 과정을 정리했다면 이제 코드를 자세히 보자.

• 첫 번째 for문은 입력으로 주어진 데이터를 받아오는 과정을 구현한 부분이다.
  피는 시기와 지는 시기 모두 위에서 말한 방법으로 연산하여 바꿔 각각 s, e 변수에 담았고
  지는 시기가 301 이전일 경우는 아예 배열에 추가하지 않았다.
  지는 시기가 301 이후일 경우에는, 만약 피는 시기가 301 이전인 꽃은 피는 시기를 301로 바꿔 추가했고
  피는 시기가 301 이후인 꽃은 바로 배열에 추가했다.
• 위의 방법으로 받은 꽃들의 배열 flowers를 피는 시기 기준 오름차순 정렬했다.
• 우선 301부터 꽃이 피는 시기를 검사하기 위해 start 변수는 301로 초기화했다.
• 두 번째 for문은 정렬된 flowers 배열을 처음부터 검사하는데,
  만약 flowers 배열이 1 이하라면 굳이 반복할 필요 없기때문에 따로 처리했다.
• flowers 배열이 1 이하일 경우, 우선 크기가 0일때는 answer를 0으로 마무리하여 반복 종료했고
  크기가 1일때는 피는 시기가 301부터 1130을 모두 채우는지를 확인하여 맞다면 answer을 1로
  바꿔준 후에 반복 종료, 모두 채워주지 않는다면 answer가 0인채로 반복 종료해주었다.
• flowers 배열이 2 이상일 경우에는 다음 if 조건을 실행할 수 있는데,
  flowers 배열의 i 번째 꽃 피는 시기가 start 이전이어야 빈틈없이 꽃이 피어있을 수 있다.
  따라서 그 여부를 확인해주는데, start 이전이 맞다면 해당 꽃의 지는 시기와 max를 비교해준다.
  만약 max보다 늦게 진다면 max를 해당 꽃의 지는 시기로 업데이트해준다.
  그리고 다음 반복으로 넘어가기 전 i+1 번째 꽃의 피는 시기를 확인해주는데,
  확인하여 현재의 start보다 크다면 카운트, start는 max로 업데이트한다. 
  그리고 이 때 start가 혹시 1130보다 크다면 더이상 반복할 필요가 없으므로 바로 종료한다.
• 그리고 이 반복문에서는 마지막 반복일 경우 추가로 확인해주어야 할 점이 있는데, 
  max가 1130보다 큰지 체크해야한다. 1130보다 크다면 모든 기간을 채웠다는 뜻이므로
  카운트해준 후 반복을 종료해주면 되고, 그렇지 않다면 answer를 0으로 초기화하여 종료한다.
• 마지막으로, 꽃이 피는 시기가 start보다 크다면 중간에 비는 기간이 생긴다는 의미이므로
  answer를 0으로 초기화한 후 break해준다.

 

💡 피드백

• 처음엔 문제가 너무 어렵게 다가와서,, 하루종일 못풀었는데
  며칠 뒤 다시 문제를 보니 예외만 정확히 정리해주면 되는 문제였다.
• 날짜를 그대로 받지 않고 1130 이런 식으로 표현해준 것이 포인트였던 것 같고,
  앞으로 그리디 문제를 접할 때는 필요한 부분을 잘 골라서 이해하는 것이 중요할 것 같다.

 

---

 

문제

https://www.acmicpc.net/problem/2457