[프로그래머스.뒤에있는 큰 수 찾기] Streak Day 92 🔥

뒤에 있는 큰 수 찾기

아마 이전에 낑낑대다가 답보고 푼 것 같아서 북마크가 걸려있는것을 보고 이번에 다시 도마위에 올려봤다.

---

문제 설명

1. [2, 3, 3, 5] 이런식으로 숫자배열이 나오면,
2. 해당 인덱스에서 다음번으로 큰 수를 적어내서 각 인덱스별 다음 큰 수를 기록한 배열을 Return
3. 예시 [2,3,3,5] => [3, 5, 5, -1]

---

문제 풀이

1. 이게 아무래도 다음에 큰애가 언제 올지를 알려면 뒤에서부터 봐주는게 맞는 방향이었고,
2. 그리고 이게 길이가 100만까지 늘어나고 있어서 당연스럽게 푸는 완탐으로는 O(N^2)라서 고려대상에서 제외하였다.
3. 그래서 일단 스택으로 하는정도까지는 짐작을 할 수 있었는데, 이 스택을 어떤형태로 가져갈지, 어떻게 스택을 관리해줄지가 모호한 상태에서 좀 많이 해맸던 것 같다.

• 그래서 이게 일단 뒤에서부터 알아보면서 stack에 넣으며 관리하되, 투 트랙으로 answer배열에 이제 기록을 해줄 것이다.
• stack의 첫값은 당연히 맨뒤의 뒤는 없을테니까 -1 넣고 출발을 할 것이고
• 스택을 비교하면서 만약에 [5,3,4,5,6]이면, 이게 [6,5,4,3]까지 자연스럽게 잘 들어가다가 다시 5를 만났을때는 이제부터 5 앞에 오는 애들은 5뒤의 3,4,5가 필요가없을것이라서, 그걸 지워주면 되는 것이다.
• 5를 만나면 다시 스택은 [5,6] 밖에 남지를 않는 것

if stack.last! < curr {
            print(curr, stack)
            while stack.count > 0, stack.last! < curr { // 스택이 유지되는 선에서
                stack.removeLast()
            }
        }

그래서 이부분을 좀 핵심처럼 잡고 갔다. 스택 마지막보다 큰친구가 들어오면 이제 트리거가돼서 쫙 훑어주는 것이다.

import Foundation

func solution(_ numbers: [Int]) -> [Int] {
    var answer = Array(repeating: -1, count: numbers.count)
    var stack = [Int]()
    for i in stride(from: numbers.count - 1, to: -1, by: -1) {
        let curr = numbers[i]
        if stack.isEmpty {   // 첫값에 -1넣고 시작하기
            stack.append(curr)
            answer[i] = -1
            continue
        }
        if stack.last! < curr {
            print(curr, stack)
            while stack.count > 0, stack.last! < curr { // 스택이 유지되는 선에서
                stack.removeLast()
            }
        }
        else {
//            print(curr, stack)
            answer[i] = stack.last!
        }
        stack.append(curr)
    }

    return [1] //그냥 임의로 박아둔 것 
}
// solution([2, 3, 3, 5])
solution([9, 1, 5, 3, 6, 2])

근데 보면서 계속 틀리다고 나와서 대체 왜 이런거지 해서 좀 더 로직을 다듬어보니까

 else {
            answer[i] = stack.last!
}

이 부분때문이었다. else{}일때만 해주는 게아니라, 위에서 while로 탈곡기를 수행했을때에도 answer[i]는 항상 stack의 최상단으로 고정을 해줘야한다.(그게 뒤 큰 수니까 !)

import Foundation

func solution(_ numbers: [Int]) -> [Int] {
    var answer = Array(repeating: -1, count: numbers.count)
    var stack = [Int]()
    for i in stride(from: numbers.count - 1, to: -1, by: -1) {
        let curr = numbers[i]
        if stack.isEmpty {
            stack.append(curr)
            answer[i] = -1
            continue
        }
        if stack.last! < curr {
//            print(curr, stack)
            while stack.count > 0, stack.last! < curr { // 스택이 유지되는 선에서
                stack.removeLast()
            }
        }
        if !stack.isEmpty {
            answer[i] = stack.last!
        }
        stack.append(curr)
    }
    return answer
}

예제는 맞길래 기대했는데, 그냥 3번까지맞고 다틀려서 또다시 1시간 연장이 됐다...

코드 회생 방안

1. 일단 반례를 찾는다.

// ex : [3,3,3,3]
코드 : [3,3,3,-1]
정답 : [-1,-1,-1,-1]

2. 반례 기반으로 코드 수정 (+디버깅)
   이걸 보니까 이게 아무래도 같은 숫자인데도 더 큰걸로 인식을 하는 것 같아서 부등호를 수정했다. <를 <=로 수정해서 같을때도 탈곡기가 실행되도록했다.

while stack.count > 0, stack.last! <= curr { // 스택이 유지되는 선에서
                stack.removeLast()
            }

3. 코드를 수정하는 과정에서

 if stack.last! < curr {
            while stack.count > 0, stack.last! < curr { 
                stack.removeLast()
            }
        }

이게 얼마나 말도안되는 코드인지 깨닫고 바깥의 if조건문을 지워줬다. 안에랑 중복되기 때문 !

최종 제출 코드

import Foundation

func solution(_ numbers: [Int]) -> [Int] {
    var answer = Array(repeating: -1, count: numbers.count)
    var stack = [Int]()
    for i in stride(from: numbers.count - 1, to: -1, by: -1) {
        let curr = numbers[i]
        if stack.isEmpty {
            stack.append(curr)
            answer[i] = -1
            continue
        }

        while stack.count > 0, stack.last! <= curr { // 스택이 유지되는 선에서
            stack.removeLast()
        }
        if !stack.isEmpty {
            answer[i] = stack.last!
        }

        stack.append(curr)
    }

    return answer
}

채점 결과

정확성: 100.0
합계: 100.0 / 100.0

---

타인의 코드

import Foundation

func solution(_ numbers:[Int]) -> [Int] {
    var answer = [Int]()
    var stack = [(Int, Int)]()
    for i in 0..<numbers.count {
        answer.append(-1)
        while !stack.isEmpty {
            if stack.last!.1 >= numbers[i] { break }
            answer[stack.removeLast().0] = numbers[i]
        }
        stack.append((i, numbers[i]))
    }

    return answer
}

이분이 정말 야무진게, 앞에서부터 풀면서 O(N)으로 풀었다는 점이다.
풀면서 이게 개인적으로는 직관적으로 로직이 와닿지않아서 이걸 생각해서 푼다는게 신기했다.
먼저 -1을 담고, 스택 최상단이 뒤에오는 수보다 작으면 이때 pop(),
이게 !stack.isEmpty라서 걍 무한으로 돌것같으면서도

if stack.last!.1 >= numbers[i] { break }

야무지게 처리한 것을 볼 수 있다.