[Leet.2375] Streak Day 95 🔥

2375. Construct Smallest Number From DI String

---

문제 설명

1. I,D로 이루어진 문자열이주어진다.
2. I가 나오면 현재 숫자로부터 다음 index에 숫자가 올라가야하고 D는 그 반대
3. 1~9가 최대 한번씩만 쓰여야한다! 가능한 숫자배치를 return !

---

문제 풀이

• 일단 너무 처음부터 감이 안왔다. 이게 내맘대로 12349876배치를 할 수가 있나? "IIIIDDDD"가 아니라 ,만약 뒤에 "IIIIDIII"라면? 등 수많은 안될 예시들만 생각이 났다.
• 결국 이게 I로 계속 올려주다가 뒤에 D가 얼마나 나올지 미리 보고 판단해야하나? 정도 생각을 했다.

최종 제출 코드

class Solution {
    func smallestNumber(_ pattern: String) -> String {
        var answer = [Int]()

        var Dstack = [Character]()
        var num = 1
        for (idx, item) in Array(pattern).enumerated() {
            if item == "I" {
                while !Dstack.isEmpty {
                    Dstack.removeLast()
                    answer.append(num)
                    num -= 1
                }
                answer.append(num)
                num += 1
            }
            else { // D만나니까 다시 쭉 올려줘야함
                Dstack.append(item)
                num += 1
            }
        }

        while !Dstack.isEmpty {
            Dstack.removeLast()
            answer.append(num)
            num -= 1
        }
        return answer.map { String($0) }.joined()
    }
}

거의 다 푼것같은데 123549876이 안나오고 12354876으로 D하나가 무시된느낌으로 좀 숫자하나가 모자르는 문제가 좀 발생했다.
일단 하나가 모자른거는 마지막에 answer.append(nums)는 고정!으로 확정을 짓긴했는데, 그래도 정답은 아니게 나왔다.

그래서 보니까 이게 내려갔을때, 다시 올려주는 로직이 안돼서 중간에 많이 내려갈 수록 뒤에 숫자가 겹치는 상황이 나와서 이 부분에 downCnt라고 하는 변수에 연속으로 내려간 값을 담고, I가 나왔을때 1을 올려주는게 아니라 downCnt만큼 올려주는 방식을 통해서 해결할 수 있었다.

class Solution {
    func smallestNumber(_ pattern: String) -> String {
        var answer = [Int]()

        var Dstack = [Character]()
        var num = 1
        for item in Array(pattern) {
            var downCnt = 0
            if item == "I" {
                while !Dstack.isEmpty {
                    downCnt += 1
                    Dstack.removeLast()
                    answer.append(num)
                    num -= 1
                }

                answer.append(num)
                num += 1 + downCnt
            }
            else { // D만나니까 다시 쭉 올려줘야함
                Dstack.append(item)
                num += 1
            }
        }

        while !Dstack.isEmpty {
            Dstack.removeLast()
            answer.append(num)
            num -= 1
        }

        answer.append(num) // 마지막꺼 추가하는거는 인정 !

        return answer.map { String($0) }.joined()
    }
}

---

타인의 코드

class Solution {
    func smallestNumber(_ pattern: String) -> String {
        var ret = String()
        var patt = Array(pattern.map { String($0) })
        var arr = [1]
        var i = 0
        var val = 1

        while i < patt.count {
            if patt[i] == "I" {
                val += 1
                arr.append(val)
            }
            else if patt[i] == "D" {
                val += 1
                arr.insert(val, at: max(arr.count-1, 0))

                var j = arr.count-2
                print("-----------------")
                while j >= 0 && patt[j] != "I" {
                    arr[j] = arr[j + 1] + 1
                    print("arr \(arr) J : \(j)")
                    j -= 1
                }
            }
            i += 1
        }
        ret = arr.map { "\($0)" }.joined()
        return ret
    }
}

insert해주면서, max(arr.count-1,0) 인게 이해가 안됐는데, 이거 결국 맨처음부터 D나올때에 대한 처리를 한거고 사실상 append를 하기 위한 것이라고 생각하면 될 것 같다.
num을 그만큼 복구 시켜주기 위해서 downCnt쓴 것 대신에 아예 j를 건드려줘서 val을 계속 가지고 갈 수 있게했다. (계속 상승하는 구조, 떨어지는거는 J가 대신 ),

아래 로그에서 확인할 수 잇듯이 일단 맨뒤에서 앞에 사이(arr.count-1)에 val을 넣어주고, 이 배열을 D가 연속된만큼 타고 올라가면서 +1씩을 점차적으로 해주면 연속되게 내려가는 배열을 만들어낼 수 있다.

-----------------
arr [1, 2, 3, 5, 4] J : 3
-----------------
arr [1, 2, 3, 5, 5, 4] J : 4
arr [1, 2, 3, 6, 5, 4] J : 3
-----------------
arr [1, 2, 3, 6, 5, 4, 8, 7] J : 6
-----------------
arr [1, 2, 3, 6, 5, 4, 8, 8, 7] J : 7
arr [1, 2, 3, 6, 5, 4, 9, 8, 7] J : 6

---

• D를 만나면 맨 뒤에 insert → 기본적인 내림차순 패턴이 유지됨 !
• D가 연속된만큼 j를 거슬러 올라가면서 +1을 아래서부터 적용(arr[i] = arr[i]+1
• val은 계속 증가하는 구조니까 굳이 -1 안해주고, 어처피 사이에 껴지니까 고려하지 않아도 된다.