[백준] (Swift) 2457번 - 공주님의 정원 (그리디, 골드3)

이것저것 채용 이슈 때문에 문제 풀이는 이 공주님문제는 4월말에 풀기 시작했지만 ㅋㅋㅋㅋ 풀이를 완료한 시점은 약 3주 후인 5월 중순,,,, (아 공주님 진짜 뿌셔버리는게 목표였는데 드디어 뿌셔서 없애버릴 수 있었다.. 다신 안풀어 이거)
자소서쓰고 최종면접보고 이것저것 하느라 코딩테스트에 집중하지 못했다. 다시 푸니까 재밌네? 그리고 확실히 refresh하고 다시 문제를 접하니까 더 잘풀리는 기분이다. 앞으로 다시 화이팅하자!! 

 

⚫️ 문제

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

2457번: 공주님의 정원

 

⚫️ 나의 풀이

와,, 진짜 어렵다. 어려운 이유는, 문제를 보자마자 그리디인 것은 알았지만, 범위설정해서 코드로구현하는게 개어렵다. 문제는, 그리디에서 가장 유명한 '회의실 배정'문제와 비슷하다. 아니면, 프로그래머스에서 풀어봤던 '단속카메라'문제와 비슷하다고 느꼈다.
단속카메라와 더 비슷하다고 느낀 이유는, 단속카메라 문제도 '들어가는 시간' 과 '나오는시간'이 따로 주어졌고, 이 범위를 모두 고려해야만 답을 찾을 수 있었다. (두 개의 문제는 아래에서 볼 수 있다.)
https://didu-story.tistory.com/394

[백준] (Swift) 1931번 - 회의실 배정 (두번째 풀이) (feat. 그리디)

https://didu-story.tistory.com/410

[프로그래머스] (Python) 단속카메라 (lv.3, 그리디)

 
뭐 어쨌든, 공주님이 정원을 관리하는데 3월1일부터 11월30일까지는 무조건 꽃이 한개 이상 피어져 있어야한다. 그니까, 주어진 범위가 겹치는 것을 최소화하면서 꽃을 선택해주어야한다.

1. 정렬해주기

우선, 그리디에서 가장 적합한 해를 먼저 찾아주면서 해를 찾기 위해서 정렬이 필요하다. 공주님의 정원에 있는 꽃들을 먼저 정리해줄것이다. 단, 만약 꽃이 피는 날짜가 같다면, 꽃이 더 오래 피어있는 아이를 더 앞으로 정렬해줌으로써, 나중에 선택하기 편하게 해주자.

2. 범위 비교하기 편하도록 날짜를 숫자개념으로 생각해주자.

input은 모두 숫자로 주어지지만, 사실 이것은 '날짜'를 의미한다. 날짜를 비교하는 일이쉽지 않지만 그냥 숫자로 생각하고 비교해주면된다. 0000 네자리로 만들어주어서 1월1일은 101, 12월 21일은 1221숫자로 만들어주고, 이 숫자들을 비교하면 자연스럽게 날짜비교가 가능해진다. 이 부분도 이 문제의 핵심 포인트라고 생각한다.

3. 내가 보기 편하도록, flowers배열 내부에 조건을 만족하는 꽃들만 넣어주자.

공주님은 3월1일부터 11월30일까지 꽃이 피어있길 바란다. 그러므로, 1월~3월까지 피어있는 꽃은 어차피 정답에 포함할 수 없고, 3월 이후에 지더라도 3월 이전에 핀 꽃들은 그냥 핀 날짜를 3월1일로 여겨도 무방하다. 
이 세 과정을 input을 받고나서 바로바로 처리해줄 것이다.
그리고 그 다음에,,, 이제 비교하는게 문젠데... 

사진은 그냥 기록용으로 올려놓은것, 이해하지 않아도 됩니다 읽어주시는 분들... 헤헤

비교하면서 중요한것은, 지금 만약 꽃을 선택했을 때, 다음꽃도 마찬가지로 선택이 가능한데 만약 지는날이 더 늦으면 그 꽃을 선택해주어야한다. 그래서 지속적으로 꽃을 선택하고, 그 뒤에있는 꽃들도 추가로 봐주면서 지는날이 더 늦는 꽃을 선택해주어야한다. (아오 복잡해 벌써)
max라는 변수에, 가장 마지막으로 진 꽃의 꽃이 진 날짜를 넣어줄 것이다. 그리고 생각한 방식은 while문으로 idx < flowers.count로 돌려줄것이고, 조건은 다음과 같이 넣어준다.

• 만약 max보다 빨리지는 꽃은 continue로 볼 필요도 없다. 
• 지금 max보다 꽃이 max보다 빨리피고, max보다 지는날이 느리면, 그 꽃을 선택해야한다.
• 그러나, 그 꽃 뒤에 혹시 지는날이 더 먼 꽃이 있다면 뒤에있는 기간이 더 긴 꽃을 선택해야해서, for문으로 flowers 전부를 탐색해주면서 뒤에있는 꽃을 확인한다.

이 과정으로 코드를 작성했다.

첫번재 시도 코드 - 틀렸습니다...

import Foundation

func solution() -> Int {
    let n = Int(readLine()!)!
    var flowers = [(Int, Int)]()

    for _ in 0..<n {
        let temp = readLine()!.split(separator: " ").map{ Int($0)! }
        // 1차로 지는날이 3월1일 이전이면 아예 flowers에 넣어주지도 않음
        if temp[2]*100 + temp[3] < 301 {
            continue
        }
        // 2차로 피는 날이 301보다 이전이면, 아예 그냥 301로 바꿔서 넣어줌
        if temp[0]*100 + temp[1] < 301 {
            flowers.append((301, temp[2]*100 + temp[3]))
            continue
        }
        // 3차로 그 중간 범위에 포함되는 애들은 걍 넣어줌
        flowers.append((temp[0]*100 + temp[1], temp[2]*100 + temp[3]))
    }

    // 피는날 오름차순, 같으면 지는날은 내림차순 (길수록 앞에위치)
    flowers.sort {
        if $0.0 == $1.0 {
            return $0.1 > $1.1
        } else {
            return $0.0 < $1.0
        }
    }

    var max = 0
    var temp = 0
    var answerArr = [Int]()
    let start = 301
    let end = 1130
    var idx = 0

    // 301부터 피어있는 꽃이 없는 경우
    if flowers[idx].0 > 301 {
        return 0
    }

    // 입력받은 꽃이 1개인 경우
    if flowers.count == 1 {
        if flowers[idx].0 == start && flowers[idx].1 > end {
            return 1
        } else {
            return 0
        }
    }

    while idx < flowers.count {
        // 어차피 정렬, 맨처음거 일단선택
        if max > end {
            break
        }

        if idx == 0 {
            max = flowers[idx].1 // 지는날이 max
            idx += 1
            answerArr.append(max)
            continue
        }

        // 지금 최종으로 지는날 max보다 지는날이 앞서면 그냥 pass
        if flowers[idx].1 < max {
            idx += 1
            continue
        }

        // 피는날은 max보다 작고, 지는날은 max보다 크면 (우리가 원하는 범위내)
        if flowers[idx].0 <= max, flowers[idx].1 > max {
            // 지금까지 순회한 꽃들 다음으로 탐색하면서 선택 가능성이 있는 꽃 찾아줌
            // 선택가능성? -> 피는날이 범위내에 들어오면서, 지는날은 더 늦는 것
            // 일단 temp에 임시로 지는날 저장해주고, 이 temp보다 큰애 찾아줘
            temp = flowers[idx].1

            for j in idx+1..<flowers.count {
                // 피는날은 우리가 만족하는 범위내고, 지는날은 현재 입력받은 temp보다 크면?
                if flowers[j].0 <= max, flowers[j].1 > temp {
                    temp = flowers[j].1
                } else {
                    break // 어차피 정렬을 해뒀기 때문에 위에 만족 안하면 pass해주는게 맞음
                }
            }

            max = temp
            answerArr.append(max)
        }

        idx += 1
    }

    print(answerArr)

    if answerArr[answerArr.count-1] <= end {
        return 0
    }

    return answerArr.count
}

print(solution())

진짜 미쳐 돌아가시겠네... 도대체 예외케이스 뭘 못찾아서 계속 틀리는지 모르겠다 ㅠㅠ 

음.. 어느부분에서 안되는지 찾아봐야한다 ㅠㅠ 일단, 백준 예제들은 통과하긴 하는데, 채점하는거 보면 1%넘어가다가 바로 틀렸다고 나온다. 즉, 통과하는 케이스가 거의 없다는 뜻이다 ㅋㅋㅋㅋㅋㅋ 그냥 다 틀려먹엇다는 뜻;
다시 구현해야할 위기에 처했다.... 아 이거 지금 이틀째 풀고 있는데 ㅋㅋㅋ 
 

(며칠 후,, 아니 약 한 달 후,,) n차시도 🤯  아직도 공주님은 어렵다 

아니,, 다시 풀어보고자 컴퓨터를 켰다. 요즘 그냥 채용준비 + 자소서 + 면접 등 때문에 알고리즘을 많이 풀지 못했다. 하지만, 최종면접도 이제 끝났으니, 급한불은 껐으니 다시 알고리즘에 집중해보자! 자,,, 공주님 먼저 없애버리자 ;;  차근차근 첨부터 다시 풀어보자. 대신, 방식은 비슷하게 풀 예정이다. go
앞에 데이터를 처리하는 부분 (301로 바꿔주고 입력받아주고 정렬하는 과정)은 동일하게 진행했고, 뒤에 코드를 다르게 바꿨다. 

• 첫번째 flower의 시작점이 301이면 무조건 선택해준다. (꽃이 지는날짜는 내림차순으로 정렬해주었기 때문에 날짜가 같으면 무조건 앞에있는거 선택하는게 가장 최선이다.)
• 만약 301이 아닌경우, 301부터 절대꽃이 필수 없기 때문에 return 0
• 301이 존재한다면, start, end 지점을 첫번째 꽃으로 설정해주고, 다음꽃부터 순회하면서 꽃을 선택해 줄 것이다.
• (변수에서) temp가 들어간 변수는 순회하면서 보고있는 꽃을 임시로 선택했다는 뜻이다.
• while문으로 idx를 기준으로 돌려준다. idx는 현재 선택된 꽃의 index를 의미한다. idx로 선택한 이유는 우리는 꽃을 미리 정렬해두었기 때문에 선택된 꽃 앞부분은 보지 않아도 되기 때문이다.
• start 와 end는 채택된 꽃의 피는날과 지는날인데, 선택된 꽃의 end가 1130보다 크면, 거기서 바로 정답을 출력한다.
• for 문으로 현재 idx보다 한칸 뒤부터 순회해준다.
  • 만약 flowers[i]의 피는날이 현재 start와 같다면 볼필요가 없고 (지는날을 내림차순으로 정렬했기 때문)
  • flowers[i]의 피는날이 현재 start와 end사이에 있고, flowers[i]의 지는날이 tempEnd보다 크면! 더 길게 피어있다는 뜻이기 때문에 temp를 갱신해줄 수 있다. 여기서 tempEnd와 tempStart를 갱신해주고, idx도 갱신해준다.
  • flowers[i]의 지는날이 tempEnd보다 작으면, 순회하고 있는 꽃은 최대길이가 아니므로 볼 필요가 없다.
• 이 모든 과정을 순조롭게 통과하면 flowersList에 idx를 넣어주고 (선택된꽃들의 집합) 
• start와 end에 현재 선택된 idx의 피는날과 지는날(temp)을 갱신해주면 된다. 

이렇게 했는데,,, 답은 맞은것 같다. 근데 메모리초과가 난다....

import Foundation

func solution() -> Int {
    let n = Int(readLine()!)!
    var flowers = [(Int, Int)]()

    for _ in 0..<n {
        let temp = readLine()!.split(separator: " ").map{ Int($0)! }
        
        if temp[2]*100 + temp[3] < 301 {
            continue
        }
        
        if temp[0]*100 + temp[1] < 301 {
            flowers.append((301, temp[2]*100 + temp[3]))
            continue
        }

        flowers.append((temp[0]*100 + temp[1], temp[2]*100 + temp[3]))
    }
    
    flowers.sort {
        if $0.0 == $1.0 {
            return $0.1 > $1.1
        } else {
            return $0.0 < $1.0
        }
    }

    if flowers[0].0 > 301 {
        return 0
    }

    var start = flowers[0].0
    var end = flowers[0].1
    var flowerList = [0]
    var tempStart = 0
    var tempEnd = 0
    var idx = 0
    var flag = false

    while idx < flowers.count {
        if end > 1130 {
            return flowerList.count
        }

        for i in idx+1..<flowers.count {
            if flowers[i].0 == start {
                continue
            } else if flowers[i].0 > start, flowers[i].0 <= end, tempEnd < flowers[i].1 {
                flag = true
                tempEnd = flowers[i].1
                tempStart = flowers[i].0
                idx = i
            } else if flowers[i].1 <= end {
                continue
            }
        }

        if flag {
            end = tempEnd
            start = tempStart
            flowerList.append(idx)
            flag = false
        }
    }
    
    return flowerList.count
}

print(solution())

 

🤯🤯🤯🤯🤯🤯🤯🤯🤯🤯🤯🤯🤯🤯

진짜 막 쌍욕이 나오넹 헤헤 자,,, 차근차근 다시보자 ㅋㅋㅋㅋㅋ 메모리초과? 원인이뭐지.. 답은 맞은거야 뭐야 ; 일단 채점이 98%까지 가다가 메모리초과가 나는데,... 
쓸데없이 for문이나 while문이 돌아가는 불필요한 연산을 줄여줘야겠다고 판단했다. 왜냐면, 우선 채점하는거보면 98%까지 전부 체점을 했지만, 메모리초과가 났기 때문. 일단 나를 믿고 솔루션은 맞았다고 판단해보자.
현재 위에 코드를 보면, for문 내부에서 중간에 끊어주는 지점이 존재하지 않는다. 전부 continue로 넘기게 된다. 여기 부분에서 중간에 끊어서 break해줄 수 있지 않을까?
생각해보니까, 다음 순회하려고 하는 꽃이 end보다 늦게 피면 우리는 아무꽃도 선택할 수 없다. (꽃은 순서대로 정렬되어있기 때문에 중간이 텅 비게 되는 것은 정답이 될 수 없다!) 따라서 break를 걸어줄 수 있도록 하는 코드를 맨앞에 추가했다. 그리고 tempStart도 굳이 필요없는 변수인 것 같아서 삭제해주었다. 그러고 진행한 결과!!

n+1차시도,,,, - 맞았습니다!

진짜 엄청나다. 한달전쯤 공주님 뿌시기가 내 목표일정도로 진짜 스트레스 받았었는데, 나름 며칠 후, 리프래쉬 후 새롭게 문제에 접근해보니 생각보다 빨리 풀렸다. 이 공주님 이자식,,,, 너 내가 다신안봐 (해석하기 편하게 그냥 주석과 print문을 지우지 않고 작성해둡니다,.)

import Foundation

func solution() -> Int {
    let n = Int(readLine()!)!
    var flowers = [(Int, Int)]()

    for _ in 0..<n {
        let temp = readLine()!.split(separator: " ").map{ Int($0)! }
        // 1차로 지는날이 3월1일 이전이면 아예 flowers에 넣어주지도 않음
        if temp[2]*100 + temp[3] < 301 {
            continue
        }
        // 2차로 피는 날이 301보다 이전이면, 아예 그냥 301로 바꿔서 넣어줌
        if temp[0]*100 + temp[1] < 301 {
            flowers.append((301, temp[2]*100 + temp[3]))
            continue
        }
        // 3차로 그 중간 범위에 포함되는 애들은 걍 넣어줌
        flowers.append((temp[0]*100 + temp[1], temp[2]*100 + temp[3]))
    }

    // 피는날 오름차순, 같으면 지는날은 내림차순 (길수록 앞에위치)
    flowers.sort {
        if $0.0 == $1.0 {
            return $0.1 > $1.1
        } else {
            return $0.0 < $1.0
        }
    }

    print(flowers)

    if flowers[0].0 > 301 {
        return 0
    }

    var start = flowers[0].0
    var end = flowers[0].1
    var flowerList = [0] // 첫번째꽃 무조건 선택 (이거 수정해야함. 만약 301보다 이후면?)
    var tempEnd = 0
    var idx = 0
    var flag = false

    while idx < flowers.count {
        if end > 1130 {
            // 답은 무조건 1201이상이어야함.
            print("flowerlist \(flowerList)")
            return flowerList.count
        }

        for i in idx+1..<flowers.count {
            if flowers[i].0 > end { // 다음꽃이 end보다 늦게 피면, 나가도돼
                break
            }

            if flowers[i].0 == start {
                continue
            } else if flowers[i].0 > start, flowers[i].0 <= end, tempEnd < flowers[i].1 {
                // 순회중인 꽃의 시작점이 범위내에 있고, 이전에 비교해온 tempEnd보다 길면 그거선택해야하니까 temp 갱신
                flag = true
                tempEnd = flowers[i].1
                idx = i // idx갱신해줘야해 지금 그 위치에있는 꽃 선택했다고 알려줘야해.
            } else if flowers[i].1 <= end { // end보다 짧으면 볼필요도 없음
                continue
            }
        }

        if flag {
            end = tempEnd
            start = flowers[idx].0
            flowerList.append(idx)
            flag = false
        } else {
            print("아무것도 선택 안된거임? 그럼 중간에 비었단 뜻 0")
            return 0
        }
    }

    return flowerList.count
}

print(solution())

 
 
아 공주님 탈출!!! 완료!!!!! 행복 그잡채 👸🏻