LeetCode: 38번 (Count and Say) [JAVA]

문제 링크

https://leetcode.com/problems/count-and-say/

Count and Say - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. count-and-say 기본값으로 1짜리에 대해 "1"을 저장
2. 단순 재귀를 기반으로 주어진 길이 n에 도달할 때까지 이전 결과값을 바탕으로 문장 생성
   1) 문장 속 존재하는 숫자들의 연속하는 개수와 숫자를 통해 문장을 생성
   
3. 해당 n짜리의 결과 반환

 문제에서 요구하는 로직은 일종의 재귀를 통해 이전 길이의 결과를 바탕으로 새로운 문장(digit string)을 생성하는 방식이다. 이전 결과 속 숫자들의 연속되는 개수를 파악해 그 숫자와 그 숫자들의 개수를 다시 이어 붙여 만드는 것으로, 길이 1에 대해 "1" digit string을 시작으로 길이 2의 경우 이전 문장 "1" 속에 1이 한 개(1) 있기 때문에 "11"을, 그 다음 길이 3의 경우 이전 문장 "11"을 통해 1이 두 개(2) 있기 때문에 "21"을 만드는 방식이다. 이런 방식으로 문제 주어진 n에 도달할 때까지 반복하고 그 결과를 반환하면 된다.
 이에 단순히 재귀 방식으로 해당 함수를 구현하면 된다. 이전 결과가 존재하지 않으면 이전 결과 생성을 위해 주어진 길이에서 1을 낮춘 길이로 동일한 함수를 call하는 방식으로 구현한 다음, 그 다음에는 단순히 문장을 돌며 숫자와 연속된 개수를 파악해 이들을 숫자 형태로 표현한다. 이후엔 최종 결과물을 반환하면 된다.

 

class Solution {
    String[] countAndSayResult;

    public String countAndSay(int n) {
        countAndSayResult = new String[n + 1];
        countAndSayResult[1] = "1";

        if (n > 1) {//1 보다 큰 숫자들에 대해
            makeDigitString(n);
        }
        
        return countAndSayResult[n];
    }

    void makeDigitString(int n) {
        if (countAndSayResult[n - 1] == null) {//이전 결과가 없다면
            makeDigitString(n - 1);
        }

        String digitString = countAndSayResult[n - 1];
        StringBuilder result = new StringBuilder();
        int digitCount = 0;

        for (int i = 0; i < digitString.length(); i++) {
            char digit = digitString.charAt(i);
            ++digitCount;

            if (i + 1 >= digitString.length() || digitString.charAt(i + 1) != digit) {//마지막 or 다음 숫자와 다르면 결과 출력
                result.append(digitCount);
                result.append(digit);
                digitCount = 0;
            }
        }

        countAndSayResult[n] = result.toString();
    }
}

결과