[Swift] [83일차] 1415_LEETCODE k번째 문자열

1415. The k-th Lexicographical String of All Happy Strings of Length n

---

문제 설명

1. n,k가 주어지고, a,b,c 총 3개 원소밖에 없다고 가정
2. 길이 n인 것으로 순서대로해서 k번째에 해당하는 문자열을 출력하면 됨

---

문제 풀이

1. 이런 문자열의 순서따지는거는 아무래도 dfs처럼 경로탐색이 필요한 것 같았다.
2. 그럼 dfs함수에 들어갈 인자가 무엇인지를 판단해야하는데, 결국 그냥 이전 문자랑만 다르면 되기 때문에 방금 넣은 문자열하나랑 현재까지 만든 문자열 이게 될 것이다.
3. 그러면 이제 n길이만큼 현재까지 만든 문자열이 도달하게 된다면은 그때부터 카운팅에 들어가면 될 것이다.

---

일단

var dict: [String: [String]] = ["a": ["b", "c"], "b": ["a", "c"], "c": ["a", "b"]]

이렇게 순서대로 들어갈 수 있도록 배열에 순서를 맞춰줬다. ex)'b','a'가 아니라 'a','b'
그렇게해서 이제 카운팅 쳐주면서 해당 카운팅때 멈춰주면 끝일것이다 순서대로는 알아서 들어간다.

if now.count == n {
                if cnt == k {
                    answer = now
                    cnt += 1
                    return
                }
                else {
                    cnt += 1
                }
            }

근데 여기서 주의해야되는거는 처음에는 어떠한 경향성이 없기때문에a,b,c,모두 들어갈 수 있기 때문에 그 부분도 처리를 해줘야한다.

if currentChar == "" { // 들어있는게 없으면
                    for item in ["a", "b", "c"] {
                        dfs(item, now + item)
                    }
                }

이렇게 보니까 좀 정직한 풀이가 된 것 같은데, 성능은 나름 준수하게 찍혀서 그렇게 어긋난 풀이는 아니었음을 알 수 있었다.

최종 제출 코드

class Solution {
    func getHappyString(_ n: Int, _ k: Int) -> String {
        var dict: [String: [String]] = ["a": ["b", "c"], "b": ["a", "c"], "c": ["a", "b"]]
        var answer = ""
        var cnt = 1
        func dfs(_ currentChar: String, _ now: String) {
            if now.count == n {
                if cnt == k {
                    answer = now
                    cnt += 1
                    return
                }
                else {
                    cnt += 1
                }
            }
            else {
                if currentChar == "" { // 들어있는게 없으면
                    for item in ["a", "b", "c"] {
                        dfs(item, now + item)
                    }
                }
                else {
                    for item in dict[currentChar]! {
                        dfs(item, now + item)
                    }
                }

            }
        }
        dfs("", "")
        return answer
    }
}

---

타인의 코드

엄청 다양한 풀이가 많았다. 백트래킹부터, 비트연산자를 다루는 풀이까지 ,, 빠른 코드 중 비슷한 풀이를 가져와봤다.

class Solution {
    let candidates = ["a", "b", "c"]

    func dfs(_ n: Int, _ k: Int, _ current: String, _ previousCharacter: String,  _ result: inout [String]) {
        if n == 0 {
            result.append(current)
            return
        }

        if result.count == k {
            return
        }

        for char in candidates {
            if char == previousCharacter {
                continue
            }

            dfs(n - 1, k, current + char, char, &result)
        }
    }

    func getHappyString(_ n: Int, _ k: Int) -> String {
        var result = [String]()

        dfs(n, k, "", "", &result)
        
        //print(result)

        if k > result.count {
            return ""
        }
        return result[k - 1]
    }
}

이분은 보면은 굉장히 유사하긴한데, 다른점이라하면은 result를 배열로해서 계속 가지고 갔다는 점인 것 같다. 이게 여러 결과값을 또 연산해야하는게 아니라서 좀 디버깅할때나 풀어가는 과정에 있어서는 유리하겠지만 메모리를 많이 차지할 것 같긴했고, 여기서 나와있는 if result.count == k {return}이 부분 보면서 너무도 당연한데, 나는 좀 이런거 신경안쓰고 풀어버렸던 것 같아서 이 부분을 기점으로 내 코드도 좀 깔끔하게 다듬어봤다.

1. 카운팅이 k를 넘으면 바로 아웃
2. answer찾아도 바로 아웃
3. 카운팅하면서 바로 그 카운트로 관리해주기
4. 올라간 카운트를 기점으로하기때문에 기존 cnt = 1을 0 으로 변경하기

개선 코드

class Solution {
    func getHappyString(_ n: Int, _ k: Int) -> String {
        var dict: [String: [String]] = ["a": ["b", "c"], "b": ["a", "c"], "c": ["a", "b"]]
        var answer = ""
        var cnt = 0
        func dfs(_ currentChar: String, _ now: String) {
            if(cnt >= k){return}
            if now.count == n {
                cnt += 1
                if cnt == k {
                    answer = now
                    return
                    }
            }
            else {
                if currentChar == "" { // 들어있는게 없으면
                    for item in ["a", "b", "c"] {
                        dfs(item, now + item)
                    }
                }
                else {
                    for item in dict[currentChar]! {
                        dfs(item, now + item)
                    }
                }
            }
        }
        dfs("", "")
        return answer
    }
}

28ms -> 3ms 개선