백준 1663 -XYZ 문자열

CT대비 문제를 풀다가 관련 문제를 풀어봤다.

 

일단 규칙을 보니 dp[n] = dp[n-3] + dp[n-2] 가 되었고, dp풀면 되겠다고 생각했다.

 

이 점화식을 이용해 String객체 배열 안에 해당 순서의 String을 저장해 주는 방식으로 풀었다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

//XYZ 문자열
public class Baek_1663 {
    static String[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int num= Integer.parseInt(br.readLine());
        int N = Integer.parseInt(br.readLine());
        dp = new String[N+1];
        dp[1] ="X";
        dp[2] = "YZ";
        dp[3] = "ZX";
        String nxyz = xyz(N);

        switch (num){
            case 1:
                System.out.println(nxyz.length());
                break;
            case 2:
                int k = Integer.parseInt(br.readLine());
                System.out.println(nxyz.charAt(k-1));
            break;
            case 3:
                char c = br.readLine().charAt(0);
                count(c,nxyz);
                System.out.println(count(c,nxyz));
                break;
        }

    }
    static String xyz(int N){
        if(dp[N]!=null) return dp[N];
        return dp[N] = xyz(N-3) + xyz(N-2) ;
    }
    static int count(char c, String nxyz){
        int count =0;
        for(int i=0; i<nxyz.length(); i++){
            if(c == nxyz.charAt(i)) count++;
        }
        return count;
    }
    //dp함수 -> 반환값 string
    //1.문자열 길이
    //2.문자열에서 k번째 문자 구하기(3째줄에)
    //3.문자열에서 특정 문자 몇번 나타나는지 구하기
}

메모리 초과 - >  String은 불변 객체이기에 덧셈 연산자 사용시 새로운 스트링을 만들어 합한 것을 저장해주고, 따라서 시간, 메모리 낭비가 심하기 떄문에 String끼리 더할 수 있는 StringBuilder클래스를 만들어 주었다( 미리 일정한 크기의 배열을 잡아두고 거기에 붙여나가는 방식)

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

//XYZ 문자열
public class Baek_1663 {
    static StringBuilder[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int num= Integer.parseInt(br.readLine());
        int N = Integer.parseInt(br.readLine());
        dp = new StringBuilder[N+1];
        dp[1] = new StringBuilder("X");
        dp[2] = new StringBuilder("YZ");
        dp[3] = new StringBuilder("ZX");
        StringBuilder nxyz = xyz(N);

        switch (num){
            case 1:
                System.out.println(nxyz.length());
                break;
            case 2:
                int k = Integer.parseInt(br.readLine());
                System.out.println(nxyz.charAt(k-1));
            break;
            case 3:
                char c = br.readLine().charAt(0);
                System.out.println(count(c,nxyz.toString()));
                break;
        }

    }
    static StringBuilder xyz(int N){
        if(dp[N]!=null) return dp[N];
        return dp[N] = xyz(N-3).append(xyz(N-2)) ;
    }
    static int count(char c, String nxyz){
        int count =0;
        for(int i=0; i<nxyz.length(); i++){
            if(c == nxyz.charAt(i)) count++;
        }
        return count;
    }
    //dp함수 -> 반환값 string
    //1.문자열 길이
    //2.문자열에서 k번째 문자 구하기(3째줄에)
    //3.문자열에서 특정 문자 몇번 나타나는지 구하기
}

그래도 메모리 초과 ㅠ

 

String클래스의 배열을 만들어주는 것 말고 다른 방식이 필요할 것 같다 ㅠ 

여기서 시간을 많이써서 오늘은 여기까지만 생각할래...