[Swift] [20일차] 택배상자

핀·2024년 12월 27일

programmers swift

SwiftAlgorithm

목록 보기

23/105

programmers-택배상자

문제 설명
보니까 다음과 같이 구성이 되어있는거에서 제약조건과 함께 얼만큼 담을 수 있는지를 return 하는 문제였다. 일단 맨 앞에 있는거만 꺼낼 수 있다고 하니까 stack이 생각났다.

초기코드

import Foundation

func solution(_ order: [Int]) -> Int {
    var answer = 0
    var Conveyer = Array(1 ... order.count)
    var support_stack = [Int]()
//    answer자체가 인덱스의 역할을 할 것

    while true { // 양쪽 컨베이어에서 못찾을 때로 조건 변경해줄 수도 ?
        let target = order[answer] // 지금 찾아야 하는 것
        while Conveyer.first! < target {
            support_stack.append(Conveyer.removeFirst())
        }
        // 찾고자하는걸 찾을 수 있는지
        if Conveyer.first == target {
            Conveyer.removeFirst()
            answer += 1
        }
        else if !support_stack.isEmpty && support_stack.last! == target {
            support_stack.removeLast()
            answer += 1
        }
        else {
            break
        }
    }
    return answer
}

이렇게하니까 [4,3,1,2,5] 는 통과하는데, [5,4,3,2,1]은 터져버린다.

원인

 print("CONVEYER", Conveyer)
        while Conveyer.first! < target {
            support_stack.append(Conveyer.removeFirst())
        }

출력
CONVEYER [1, 2, 3, 4, 5]
CONVEYER []
배열이 없는데 여기서 first! 강제 언래핑을 해줬기 때문이다. 이부분을 좀 조정하면...

수정코드

import Foundation

func solution(_ order: [Int]) -> Int {
    var answer = 0
    var Conveyer = Array(1 ... order.count)
    var support_stack = [Int]()
//    answer자체가 인덱스의 역할을 할 것

    for target in order {
        while let first = Conveyer.first, first < target {
            support_stack.append(Conveyer.removeFirst())
        }
        if Conveyer.first == target {
            Conveyer.removeFirst()
            answer += 1
        }
        else if !support_stack.isEmpty && support_stack.last! == target {
            support_stack.removeLast()
            answer += 1
        }
        else {
            break
        }
    }
    return answer
}

복잡한 while문 하나를 빼주고 어처피 order배열의 원소를 하나씩찾는것이니까 for문으로 바꿨다.

if let만 되는게 아니라 while let으로 할 수가 있더라

시간초과

근데 결국 샘플만 통과하고 테스트케이스를 거의 통과못하고 다 시간초과가 뜨게 되었다..

1. 혹시 내가 너무 무분별하게 removeFirst 를 사용했나? 싶었다.

배열의 첫번째 원소 건드는건 O(N) 맨뒤는 O(1)이니까 빡빡하게 시간제한 걸려있으면 이부분부터 건드려야할 것 같아서 일단 전부 removeLast로 바꿔줬다.

var Conveyer = Array(1 ... order.count) // 이건 오케이
var Conveyer = Array(order.count ... 1)  // 이건 실패 
이렇게 역순서로 해주는건 에러가 있길래 좀 서칭해보니
stackoverflow-Array descending
reverse를 해주거나 stride를 사용하라고 한다.

print(Array(stride(from: 5, to: 1, by: -1)))  // [5,4,3,2]

reverse도 쓸 수 있다지만, 이 stride를 써보도록하자. 사용하니까
[5,4,3,2] 이렇게 1이 빠진채로 나오는걸 확인할 수 있었다. 그래서 to부분을 0으로 해줘야겠구나해서 이를 사용해서 코드를 다듬어서 제출했더니..

결과는?

채점 결과
정확성: 100.0
합계: 100.0 / 100.0

오 진짜 이 차이였다. 나름 n - N^2 만큼 큰차이가 아니라 큰 차이가 없을지 알았는데, 다음부터는 좀 디테일하게 생각해야겠구나 싶었다.

최종 코드

import Foundation

func solution(_ order: [Int]) -> Int {
    var answer = 0
    var Conveyer = Array(
        stride(from: order.count, to: 0, by: -1)
    )
    var support_stack = [Int]()
//    answer자체가 인덱스의 역할을 할 것

    for target in order {
        while let first = Conveyer.last, first < target {
            support_stack.append(Conveyer.removeLast())
        }
        if Conveyer.last == target {
            Conveyer.removeLast()
            answer += 1
        }
        else if !support_stack.isEmpty && support_stack.last! == target {
            support_stack.removeLast()
            answer += 1
        }
        else {
            break
        }
    }
    return answer
}

타인의 코드

import Foundation

func solution(_ order:[Int]) -> Int {
    var stack = [Int]()
    var number = 1
    var answer = 0

    for i in 0..<order.count {
        while number <= order[i] {
            stack.append(number)
            number += 1
        }
        if stack.last! == order[i] {
            _ = stack.popLast()
            answer += 1
        } else {
            break
        }
    }

    return answer
}

나는 찐 컨베이어 벨트를 하나 만들어줬는데, 어처피 순서대로 되어있으니, 그냥 숫자로 치환해서 풀어준게 진짜 깔끔하다고 느꼈다.
만약 4를 찾는거라면 4에서 멈추고, 왼쪽 컨베이어(찐컨베이어), 보조컨베이어 둘 다 조건문을 걸어주면서 충족하는데에서 넣어주게끔했는데, 그게 아니라 이거는 4까지 보고 지나간다음에 , 무조건 보조컨베이이어벨트에서 담는 방식으로 해준게 너무 좋다고 느껴졌다.
이를 바탕으로 내꺼를 개선해보자면...

개선코드

import Foundation

func solution(_ order: [Int]) -> Int {
    var answer = 0
    var Conveyer = Array(
        stride(from: order.count, to: 0, by: -1)
    )
    var support_stack = [Int]()
//    answer자체가 인덱스의 역할을 할 것

    for target in order {
        while let first = Conveyer.last, first <= target {
            support_stack.append(Conveyer.removeLast())
        }
        if !support_stack.isEmpty && support_stack.last! == target {
            support_stack.removeLast()
            answer += 1
        }
        else {
            break
        }
    }
    return answer
}