[Swift] [34일차] 뒤에 있는 큰 수 찾기

핀·2025년 1월 10일

SwiftAlgorithm

목록 보기

37/105

문제 설명

numbers배열이 주어지는데, 자신보다 크면서 가까이 있는 수를 배열에 담아주면됨

백준에도 비슷한 문제가 있었던 것 같은데, 빌딩 이라고 생각하고 겹치거나 이제 자신보다 큰 빌딩중에 가까운 친구, 즉 그냥 옥상에서 바라봤을 때 눈을 가로막거나 같으면 그것을 배열에 넣어주면된다.

문제 접근

뒤에서 타고가면서 tuple로 현재값, 그 현재값 뒤큰수 를 같이 만들어준뒤

해당 튜플을 계속 최신화 해주면서 뒤에서 부터 타고가면 된다고 생각을 했다.

import Foundation

func solution(_ numbers: [Int]) -> [Int] {
    var current_number = (0, 0)
    var answer = [Int]()
    func caclulate(_ current_tuple: (Int, Int), _ number: Int) -> (
        Int,
        Int
    ) {
        if current_tuple.0 > number { // 크거나 같으면 ?
            answer.append(current_tuple.0)
            return (number, current_tuple.0)
        }
        else if current_tuple.1 > number {
            answer.append(current_tuple.1)
            return (number, current_tuple.1)
        }
        else {
            answer.append(-1)
            return (number, -1)
        }
    }
    // 현재 기준

    for item in numbers.reversed() {
        current_number = caclulate(current_number, item)
    }
    answer.reverse()
    return answer
}

채점 결과

정확성: 26.1
합계: 26.1 / 100.0

5개?정도 맞고 나머지를 다틀려버리더라..!

반례를 찾아봤다.

반례 : [3, 1, 2, 4]
기대값 : [4,2,4,-1] 
내 코드 출력 : [-1,2,4,-1]

왜 틀렸는지?

나는 최신화해주는 기준을 차용하고 있기 때문에 4,2,1을 거쳐오면서 3을 마주했을때는 (1,2)가 나와버린다. 사실 뒤에 더 있어요!를 말해줘야하는데, 그게 안되는 상황, 이걸 계속 누적시킬거면 더 쉽게 찾는 법을 터득해야할 듯 한데..

일단 튜플을 하나씩 저장하던 것을 배열로 늘려줬다. 그리고 이 배열을 뒤에서부터 타고가면서 못찾으면 뒤로 계속 타면서 이동하게끔 구현을 해줬다.

import Foundation

func solution(_ numbers: [Int]) -> [Int] {
    var current_number = [(0, 0)]
    var answer = [Int]()
    func caclulate(_ number: Int) -> (
        Int,
        Int
    ) {
        for current_tuple in current_number.reversed() {
            if current_tuple.0 > number { // 크거나 같으면 ?
                answer.append(current_tuple.0)
                return (number, current_tuple.0)
            }
            else if current_tuple.1 > number {
                answer.append(current_tuple.1)
                return (number, current_tuple.1)
            }
            else {
                continue
            }
        }
        answer.append(-1)
        return (number, -1)
    }
    for item in numbers.reversed() {
        current_number.append(caclulate(item))
    }
//    print(current_number)
    // 현재 기준
    answer.reverse()
    return answer
}

채점 결과

정확성: 91.3
합계: 91.3 / 100.0

다 맞은지 알았는데 시간초과가 2개 발생했다!

시도 1 : answer 배열을 append하지말고 인덱스로 접근해서 값 수정하기

이렇게하면 append로 해주고 reversed해주는 시간초과를 해소할 수는 있을 것 같았다.

var answer: [Int] = Array(repeating: 0, count: numbers.count)

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

동일하게 실패 ! 시간초과2개

시도 2 : 결국 대규모 공사를 거쳤다. tuple이 아니라 정통 스택을 사용해야하는 것을 알게되었고 대대적인 공사에 들어갔다.

import Foundation

func solution(_ numbers: [Int]) -> [Int] {
    var stack = [Int]()
    var answer: [Int] = Array(repeating: -1, count: numbers.count)

    for i in stride(from: numbers.count - 1, through: 0, by: -1) {
        let current_focus = numbers[i]
        print(stack)
        while let last_number = stack.last, last_number <= current_focus { // 이게 현재보다 stack.last 즉, stack에서 가장 가까운 큰놈부터 지금 나보다 작으면 다 삭제
            stack.removeLast()
        }
        if let last = stack.last { // last 가장 근접한 친구 중에서 큰놈이 answer
            answer[i] = last
        }

        stack.append(current_focus) // 그리고 현재값 넣어주면됨
    }
    //    print(current_number)
    // 현재 기준

    return answer
}

결국 어떻게 이 값들을 다 저장할 것이냐..에서 튜플을 떠올린 거였는데,

while let last_number = stack.last, last_number <= current_focus { // 이게 현재보다 stack.last 즉, stack에서 가장 가까운 큰놈부터 지금 나보다 작으면 다 삭제
            stack.removeLast()
        }

해당 로직으로 다 해결할 수 있었다.

계속 가장 큰값을 last로 해줘야하나 싶어서 생각이 꼬였던 것인데, 그냥 큰값을 0번으로 두고, 가까운 큰값을 last로 두면서 계속 솎아주면 되는 것이었다...

최종코드

import Foundation

func solution(_ numbers: [Int]) -> [Int] {
    var stack = [Int]()
    var answer: [Int] = Array(repeating: -1, count: numbers.count)

    for i in stride(from: numbers.count - 1, through: 0, by: -1) {
        let current_focus = numbers[i]
        
        while let last_number = stack.last, last_number <= current_focus { // 이게 현재보다 stack.last 즉, stack에서 가장 가까운 큰놈부터 지금 나보다 작으면 다 삭제
            stack.removeLast()
        }
        if let last = stack.last { // last 가장 근접한 친구 중에서 큰놈이 answer
            answer[i] = last
        }

        stack.append(current_focus) // 그리고 현재값 넣어주면됨
    }
    return answer
}

채점 결과

정확성: 100.0
합계: 100.0 / 100.0

타인의 코드 (주석을 달아봤다.)

import Foundation

func solution(_ numbers:[Int]) -> [Int] {
    var answer = [Int]()
    var stack = [(Int, Int)]() // (인덱스, value) 튜플 사용
    for i in 0..<numbers.count {
        answer.append(-1) // 초기값 -1 (동일, 못찾은거는 -1이기 때문)
        while !stack.isEmpty {
            if stack.last!.1 >= numbers[i] { 
                break // 스택의 꼭대기가 현재 값보다 크거나 같으면 루프 끝
            }
            // 스택 꼭대기값이 값이 현재 값보다 작으면 pop하고, 뒷큰수로 설정
            answer[stack.removeLast().0] = numbers[i]
        }
        // 현재 값과 인덱스를 스택에 push
        stack.append((i, numbers[i]))
    }

    return answer
}