[Swift] [81일차] 1079_LEET 경우의 수 백트래킹

1079. Letter Tile Possibilities

---

문제 설명

1. 문자열 주어지는데, 경우의 수를 구하면 된다.
2. 길이는 1부터 n까지
3. 중복 제거하면서 카운팅을 return하라

---

문제 풀이

1. 처음엔 쫌 막막했다. 이거 공식쓰기에는 같은 게 있어서 원하는대로는 안될 것 같고,,
2. 그렇다고 다 계산하기에는 로직이 좀 모호해졌다.
3. 그렇다보니 이전에 봤던 느낌으로 dfs느낌으로 좀 알아가야하나? 해서 이게 백트래킹으로 결국 틀어서 진행했다.

먼저 백트래킹관련한 함수를 만들어줬다. btf는 백트래킹펑션이다 ㅎㅎ...

        func btf(_ count_dict: inout [Character: Int]) {
            for (item, cnt) in count_dict where cnt > 0 {
                answer += 1 // 지금꺼 카운팅
                count_dict[item]! -= 1 // 지금 보고 있는 것 사용 ( where조건이라 남아있는 친구임 )

                btf(&count_dict) // 더 깊게 파기

                count_dict[item]! += 1 // 하나 빼고 다시
            }
        }

1. where cnt > 0 이 부분을 생각 못했다.
2. 그리고 for문으로 dict를 돌려줄때 가장 걱정했던게 "A"를 카운팅하고 또 다음에 "A"가 나오면 어쩌지? 였는데, dict로 for문을 돌리면 이게 종류별로 나오기 때문에 그럴 경우는 없다는게 당연하면서도 놓치고 있던 사실이었다.

최종 제출 코드

class Solution {
    func numTilePossibilities(_ tiles: String) -> Int {
        var answer = 0
        var count_dict: [Character: Int] = [:]
        for item in tiles {
            count_dict[item, default: 0] += 1
        }

        func btf(_ count_dict: inout [Character: Int]) {
            for (item, cnt) in count_dict where cnt > 0 {
                answer += 1 // 지금꺼 카운팅
                count_dict[item]! -= 1 // 지금 보고 있는 것 사용 ( where조건이라 남아있는 친구임 )

                btf(&count_dict) // 더 깊게 파기

                count_dict[item]! += 1 // 하나 빼고 다시
            }
        }
        btf(&count_dict)
        return answer
    }
}

---

타인의 코드

비교적 효율적이라고 생각했는데, 캐시부터 뭐 utf8, updatevalue? 처음보는 방식의 코드들을 확인할 수 있었다. 그 중 가독성이 좋은 코드를 가져와봤다.

class Solution {
    var count = 0
    func numTilePossibilities(_ tiles: String) -> Int {
        
        var arr = Array(tiles.sorted())
        print(arr)
        var indexSet = Set<Int>()
        backtrack(arr, &indexSet)
        return count

    }

    func backtrack(_ arr: [Character], _ indexSet: inout Set<Int>) {
        
        // print(indexSet)
        for i in 0..<arr.count {
            if indexSet.contains(i) {continue}
            if i > 0 && arr[i] == arr[i-1] && !indexSet.contains(i-1) {continue}

            indexSet.insert(i)
            count = count + 1
            backtrack(arr, &indexSet)
            // count = count + 1
            indexSet.remove(i)
        }
    }
}

특이한 점은

if i > 0 && arr[i] == arr[i-1] && !indexSet.contains(i-1) {continue}

• 같은 문자가 연속해서 나타났을 때, 앞 문자를 선택하지 않은 경우라면 건너뛰는 조건이다.
  AAB에서 2번째 A 먼저 선택하며 ㄴ어그러지니까 그 부분을 방지해준 것으로 볼 수 있다.
  나머지는 dict에서 카운팅을 빼주는 것과 동일하다 insert, remove의 차이