[코테연습] 1415. The k-th Lexicographical String of All Happy Strings of Length n

https://leetcode.com/problems/the-k-th-lexicographical-string-of-all-happy-strings-of-length-n/description/?envType=daily-question&envId=2025-02-19

 

 

문제 타입

• 백트래킹 (Backtracking)
• 재귀 (Recursion)
• 문자열 (String)
• 사전순 순열 (Lexicographical Order)
• 구현 (Implementation)

---

🔹 문제 분석

• 문자열의 길이 nnn과 정수 kkk가 주어진다.
• 'a', 'b', 'c'의 문자만 사용하여 Happy String을 만든다.
• Happy String이란, 인접한 문자가 같은 경우가 없는 문자열을 의미한다.
• 모든 Happy String을 사전순으로 정렬했을 때, kkk번째 문자열을 찾는다.
• Happy String의 개수가 kkk보다 작으면 빈 문자열("")을 반환해야 한다.

---

🔹 문제 해석

• 입력값
  • nnn : 문자열의 길이 (1 ≤ nnn ≤ 10)
  • kkk : 찾고 싶은 Happy String의 순서 (1 ≤ kkk ≤ 3×2(n−1)3 \times 2^{(n-1)}3×2(n−1))
• 출력값
  • Happy String 중에서 사전순으로 kkk번째 문자열을 반환.
  • 만약 kkk번째 Happy String이 존재하지 않으면 ""(빈 문자열) 반환.

> java

 

class Solution {
    List<String> list;
    public String getHappyString(int n, int k) {
        String [] arr = {"a","b","c"};
        list = new ArrayList<>();
        backtrack(new StringBuilder(), n, 0);
        if (k <= list.size()) {
            Collections.sort(list);
            return list.get(k-1);
        }
        return "";
    }

    public void backtrack(StringBuilder sb, int n, int depth) {
        if (depth == n) {
            list.add(sb.toString());
            return;
        }

        for (char c : new char[]{'a', 'b', 'c'}) {
            if (depth == 0 || sb.charAt(depth - 1) != c) { // 인접한 문자 다르면 추가
                sb.append(c);
                backtrack(sb, n, depth + 1);
                sb.deleteCharAt(sb.length() - 1); // 백트래킹
            }
        }
    }
}

 

 

> python

 

class Solution:
    def __init__(self):
        self.arr = []  # 인스턴스 변수로 리스트 선언

    def getHappyString(self, n: int, k: int) -> str:
        self.backtrack('', n, 0)  # 백트래킹 실행
        
        # k번째 문자열이 존재하면 반환, 없으면 빈 문자열 반환
        return self.arr[k - 1] if k <= len(self.arr) else ""

    def backtrack(self, _str, n, depth):
        if depth == n:
            self.arr.append(_str)  # 리스트에 happy string 추가
            return
        
        for s in ['a', 'b', 'c']:
            if depth == 0 or _str[depth - 1] != s:  # 인접 문자가 같지 않을 때만 추가
                self.backtrack(_str + s, n, depth + 1)  # 새로운 문자열을 추가하고 백트래킹 실행