[Swift] [46일차] 763_LEET

763. Partition Labels

문제 설명

1. 알파벳이 무작위로 쭉 나열되어있는 문자열 s가 주어진다.
2. 최대한의 큰 덩어리 부분으로 나누면서
3. 한 덩어리 안의 알파벳은 다른 덩어리에 등장하지 않도록함 !

---

문제 접근

1. 일단 a가 시작부분에도 나오고 끝에도 나올 수 있으니까 전체를 알아야지 짜를 수 있겠다 싶었고,
2. Constraints가 문자열길이 <= 500인걸로 봤을 때 O(N^2)까지는 거뜬할 듯? 보인다.
3. 그러면 각각 알파벳을 언제 처음나오는지, 언제 마지막에 나오는지를 잘 파악해서 잘라야하나 ?
4. 노트에 써보고 하다보니 이런식으로 풀면 되겠구나를 알 수 있었다.

그리디처럼! 맨 앞친구의 끝지점을 찾고, 거기까지 포함된 친구의 마지막으로 잘라주고, 그다음으로 넘어가면은 될 것이다.

이렇게 a의 끝을 찾으니 그안에 포함된 b,c 친구들 역시 a의 빨간줄 바운더리에 속하기 때문에 a~a까지 짤라주면 된다 !

---

문제풀이

func findBackLetterIndex(_ s: [Character], _ find: Character) -> Int {
    for i in stride(from: s.count - 1, to: 0, by: -1) {
        if s[i] == find {
            return i
        }
    }
    return 999 // 어처피 위에서 return 될거라 그냥 999 넣음
}

class Solution {
    func partitionLabels(_ s: String) -> [Int] {
        var 시작점 = 0
        var 다시탐색스위치 = false
        var 여기까지탐색완료 = 0
        var answer = [Int]()
        var s = Array(s)
        while 여기까지탐색완료 < s.count - 1 { // 끝에 도착하면 끝
            var findingLetter = s[여기까지탐색완료 + 1] // 현재 찾는 친구
            repeat { // 여기에서 다음 잘 찾을 수 있게 커서까지 옮겨주고 끝낼거임 !
                다시탐색스위치 = false
                여기까지탐색완료 = findBackLetterIndex(s, findingLetter)
                var tmpSet = Set(
                    s[시작점 ... 여기까지탐색완료] // 일단 처음들어온 친구가 어디까지 뒤로가는지 볼까 ?
                )
                tmpSet.remove(findingLetter) // 처음 들어온친구 빼고 이제 나머지 돌아가면서 어디까지 되는지 판단
                var 탐색최대값 = 여기까지탐색완료

                for element in tmpSet {
                    var tmp = findBackLetterIndex(s, element)

                    if tmp > 탐색최대값 { // 안에 들어있던 친구가 기존 원소보다 더 멀리 있을 때 ( 더 꼬리에 가까울 때 )
                        탐색최대값 = tmp
                        findingLetter = element
                        다시탐색스위치 = true
                    }
                }

            } while 다시탐색스위치
            answer.append(여기까지탐색완료 - 시작점)
            시작점 = 여기까지탐색완료
        }
        answer[0] += 1
        return answer
    }
}

이게 코드가 엄청 길어지게 됐다. 더 뒤에있는 친구를 찾을 수록 더 뒤를 봐야하다보니 변수가 많아지고, while문 계속 사용하고 있어서 한글변수 서주면서 혼선을 줄이고자했다.. 설명을 해보자면

1. while문이 두개로 이루어져있고 내부 while문은 다시탐색스위치가 ON되어있을 때만 가동한다.
2. 예제의 ababcbacadefegdehijhklij를 기준으로 한다면, 맨뒤의 a가 8이 나왔을 때
   0~8까지의 원소를 모두 SET()으로 찾아주고
3. 그 SET에서 a를 제외한 애들을 반복문돌리면서 현재 8보다 더 뒤에있는애가 있는지 탐색한다.
4. 더 뒤에있으면 또 그것을 기준으로 그때까지 0~새로찾은 뒤의원소 위치 로 짤라주고, 이를 반복한다.
5. 그렇게 한 덩어리가 끝나면 내부 while문을 벗어나면서 그 다음부터 탐색을 진행한다.

어찌저찌 무한루프 겨우 벗어나니까 풀리긴했는데, 테스트 제출과정에서 에러가 떴다.

TESTCASE : caedbdedda
Array index is out of range

---

디버깅!

func findBackLetterIndex(_ s: [Character], _ find: Character) -> Int {
    for i in stride(from: s.count - 1, to: 0, by: -1) {
        if s[i] == find {
            return i
        }
    }
    return 999 // 어처피 위에서 return 될거라 그냥 999 넣음
}

여기서 999가 나오다보니 그런 버그가 뜬것이었다. 길이는 최대500이라서 일부러 디버깅을 위해서 999가 나오게끔 해준 것이다. 이게 절대 나올 수가 없는건데, 알고보니

    for i in stride(from: s.count - 1, to: 0, by: -1) {

to:0으로 되어있어서 그랬다. 이게 싫으면 throungh를 해줘야한다. 혹은 -1 로 조정.. 그래서 이부분 조정을 해줬고,

var findingLetter = s[여기까지탐색완료 + 1]

이렇게 여기까지 탐색을 했으니 다음친구는 +1을 해준 상태였는데, 초기값 설정시에 var 여기까지탐색완료 = 0으로 되어있어서 첫 알파벳을 탐색에 넣지 않는 문제가 있었다 이부분역시 -1로 수정을 거쳤다.

최종제출

func findBackLetterIndex(_ s: [Character], _ find: Character) -> Int {
    for i in stride(from: s.count - 1, to: -1, by: -1) {
        if s[i] == find {
            return i
        }
    }
    return 999 // 어처피 위에서 return 될거라 그냥 999 넣음
}

class Solution {
    func partitionLabels(_ s: String) -> [Int] {
        var 시작점 = 0
        var 다시탐색스위치 = false
        var 여기까지탐색완료 = -1
        var answer = [Int]()
        var s = Array(s)
        while 여기까지탐색완료 < s.count - 1 { // 끝에 도착하면 끝
            var findingLetter = s[여기까지탐색완료 + 1] // 현재 찾는 친구

            repeat { // 여기에서 다음 잘 찾을 수 있게 커서까지 옮겨주고 끝낼거임 !
                다시탐색스위치 = false
                여기까지탐색완료 = findBackLetterIndex(s, findingLetter)

                var tmpSet = Set(
                    s[시작점 ... 여기까지탐색완료] // 일단 처음들어온 친구가 어디까지 뒤로가는지 볼까 ?
                )
                tmpSet.remove(findingLetter) // 처음 들어온친구 빼고 이제 나머지 돌아가면서 어디까지 되는지 판단
                var 탐색최대값 = 여기까지탐색완료

                for element in tmpSet {
                    var tmp = findBackLetterIndex(s, element)

                    if tmp > 탐색최대값 { // 안에 들어있던 친구가 기존 원소보다 더 멀리 있을 때 ( 더 꼬리에 가까울 때 )
                        탐색최대값 = tmp
                        findingLetter = element
                        다시탐색스위치 = true
                    }
                }

            } while 다시탐색스위치

            answer.append(여기까지탐색완료 - 시작점)

            시작점 = 여기까지탐색완료
        }
        answer[0] += 1
        return answer
    }
}

중하위권정도에 위치할 수 있었다.

내 코드가 엄청 번거롭게 푼거같아서 최상위 복잡도 코드는 어떨지 궁금했다.

타인의 코드

class Solution {
    func partitionLabels(_ s: String) -> [Int] {
        var lastIndex: [Character: Int] = [:]
    
    for (index, char) in s.enumerated() {
        lastIndex[char] = index
    }
    
    var partitions: [Int] = []
    var start = 0
    var end = 0
    
    for (index, char) in s.enumerated() {
        if let last = lastIndex[char] {
            end = max(end, last)
        }
        
        if index == end {
            partitions.append(end - start + 1)
            start = index + 1
        }
    }
    
    return partitions
    }
}

코드를 받아서 디버깅을 해보면서 반복문 하나로 끝내준점..

내 코드는 계속해서 max값이 갱신되는 상황에 대해 대처하는게 미숙했던것 같다.
해당 코드는 먼저 딕셔너리로 end값을 정의해놓고, 그마저도 나처럼 계속해서 문자별로 뒤에서 o(N)돌려주는 것 대신에 한 번 돌리는 걸로 수행한 것 부터 좀 격차가 느껴진 부분이었다.
그래서 최종적으로는 반복문 돌려주면서 현재 가장 큰 값을 end로 놓고 그게 지금 보고있는 커서값(index)값이면 이제 그걸 return해서 짤라주면 되는 것이었다..