문제

  • 링크
    title: "코딩테스트 연습 - 4단 고음"
image: "https://image.freepik.com/free-vector/landing-page-template-for-a-website_23-2147782747.jpg"
description: ""
url: "https://school.programmers.co.kr/learn/courses/30/lessons/1831"

    문제 풀이

    문제 접근

  • 모든 경우의 수를 볼 수 없다.
  • 제일 큰 경우의 문자열은 *++ *++ = 17
  • 최소는 **++++ = 13
  • 위는 규칙성이 있을까?
    • 최대는 *++만큼 증가 (x3 +2)
    • 최소는 3*n + n*2
    • 최종음높이에 따라, 가능한 3단고음의 개수의 범위를 구한다.
  • 이후, 계산
    • 스택을 활용해서, 올바른 문자열인지 확인할까? (효율적인가? 과연?)
    • 모든 조합은 안된다. -> +로 시작하는 등의 예제가 n과 일치할 수도 있다.
    • 조건
      • 첫번째는 무조건 *
      • 마지막 * 뒤는 무조건 +가 두개 이상.
      • * 는 n-별순서 만큼의 두 배만큼

        간단한 수도 코드 정리

        ```pseudocode 함수 solution(n): 초기화 answer = 0 초기화 min_pattern = 0 초기화 max_pattern = 0

    // 최소 패턴 길이 계산 초기화 tmp = 0 WHILE n >= tmp AND tmp <= Integer.MAX_VALUE: tmp = 3^(min_pattern + 1) + (min_pattern + 1)^2 min_pattern = min_pattern + 1 END WHILE min_pattern = min_pattern - 1 // 최소 패턴 길이 감소

    // 최대 패턴 길이 계산 초기화 tmp = 1 WHILE n >= tmp AND tmp <= Integer.MAX_VALUE: tmp = tmp * 3 + 2 max_pattern = max_pattern + 1 END WHILE

    // 결과 계산 FOR i FROM min_pattern TO max_pattern: answer = answer + calResult(n, i) END FOR

    RETURN answer

함수 calResult(n, pattern): 초기화 count = 0 초기화 combinations = 빈 리스트 generateCombinations(“”, pattern, pattern * 2, combinations)

FOR 각 조합 s IN combinations:
    초기화 sum = 1
    FOR 각 문자 c IN s:
        IF c == '*':
            sum = sum * 3
        ELSE IF c == '+':
            sum = sum + 1
        END IF
    END FOR
    
    IF n == sum:
        count = count + 1
        출력 s
    END IF
END FOR

RETURN count

// 재귀적으로 문자열 조합을 생성하는 메소드 함수 generateCombinations(current, remainingStars, remainingPluses, combinations): // 현재 조합에서 ‘*‘와 ‘+’의 개수가 다 사용되었으면 추가 IF remainingStars == 0 AND remainingPluses == 0: 추가 current TO combinations RETURN

// '*'가 남아있다면 추가
IF remainingStars > 0:
    generateCombinations(current + "*", remainingStars - 1, remainingPluses, combinations)
END IF

// '+'가 남아있다면 추가
IF remainingPluses > 0:
    generateCombinations(current + "+", remainingStars, remainingPluses - 1, combinations)
END IF


---
## 풀이 코드
```java
import java.util.*;

class Solution {
    public int solution(int n) {
        int answer = 0;
        int min_pattern = 0; // 3단고음 패턴의 최소 갯수
        int max_pattern = 0; // 3단고음 패턴의 최대 갯수
        
        // min max length
        int tmp = 0;
        while (n >= tmp || tmp > Integer.MAX_VALUE) {
            tmp = (int)Math.pow(3, min_pattern+1) + (int)Math.pow(min_pattern+1, 2);
            min_pattern++;
        }
        min_pattern--;
        
        tmp = 1;
        while (n >= tmp || tmp > Integer.MAX_VALUE) {
            tmp = tmp * 3 + 2;
            max_pattern++;
        }
        
        // result
        for (int i = min_pattern; i <= max_pattern; i++) {
            answer += calResult(n, i);
        }
        
        return answer;
    }
    
    public static int calResult(int n, int pattern) {
        int count = 0;
        List<String> combinations = new ArrayList<>();
        generateCombinations("", pattern, pattern*2, combinations);
        
        for (String s : combinations) {
            int sum = 1;
            for (char c : s.toCharArray()) {
                if (c == '*') {
                    sum *= 3;
                } else if (c == '+') {
                    sum++;
                }
            }
            
            if (n == sum) {
                count++;
                System.out.println(s);
            }
        }
        
        return count;
    }
    
    // 재귀적으로 문자열 조합을 생성하는 메소드
    private static void generateCombinations(String current, int remainingStars, int remainingPluses, List<String> combinations) {
        // 현재 조합에서 '*'와 '+'의 개수가 다 사용되었으면 추가
        if (remainingStars == 0 && remainingPluses == 0) {
            combinations.add(current);
            return;
        }

        // '*'가 남아있다면 추가
        if (remainingStars > 0) {
            generateCombinations(current + "*", remainingStars - 1, remainingPluses, combinations);
        }
        
        // '+'가 남아있다면 추가
        if (remainingPluses > 0) {
            generateCombinations(current + "+", remainingStars, remainingPluses - 1, combinations);
        }
    }
}

미완성 코드다..

| | | |—|—| |테스트 1| | |입력값 〉|15| |기댓값 〉|1| |실행 결과 〉|테스트를 통과하였습니다.| |출력 〉|++++|

  
테스트 2 
입력값 〉24
기댓값 〉0
실행 결과 〉테스트를 통과하였습니다.
  
테스트 3 
입력값 〉41
기댓값 〉2
실행 결과 〉테스트를 통과하였습니다.
출력 〉++++++
++++++
  
테스트 4 
입력값 〉2147483647
기댓값 〉1735
실행 결과 〉실행 중단