모각코 6회차 활동정리

목표 : 백준 알고리즘 문제 풀고 블로그에 정리하기

 

https://ethereal-coder.tistory.com/97

백준 [자바 java] 12904 : A와 B

https://www.acmicpc.net/problem/12904

12904번: A와 B

 

처음에는 dfs로 풀었는데 시간초과가 났다. 그래서 더 효율적인 방법을 찾다가 완성된 문자열에서 처음 문자열로 돌아가는 방법을 쓰게 되었다. 

문자열의 제일 끝이 A이면 이전에 기존 문자열 끝에 A를 썼다는 의미이므로 A를 뺴고 그대로 두면 되고, B이면 B를 빼고 문자를 뒤집으면 된다. 

이를 반복하다가 문자가 아예 사라지면 break를 통해 나오고 안된다는 결론을 내면 된다.

 

import java.io.*;
import java.util.*;



public class Main {

    static String BB(String k){
        char[] arr = k.toCharArray();
        char[] arr2 = new char[arr.length-1];

        for(int i = 0;i<arr.length-1;i++){
            arr2[i] = arr[arr.length -2 -i];
        }

        return new String(arr2);
    }

    static String AA(String k){
        char[] arr = k.toCharArray();
        char[] arr2 = new char[arr.length-1];

        for(int i = 0;i<arr.length-1;i++){
            arr2[i] = arr[i];
        }

        return new String(arr2);
    }

    public static void main(String[] args) throws IOException{

        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));

        String fir = br.readLine();
        String sec = br.readLine();

        //String Stack 만들고 이를 이용해서 풀기
        Stack<String> s = new Stack<>();



        s.push(sec);

        while(s.isEmpty() != true){
            String now = s.pop();
            //System.out.println(now);

            char[] arr = now.toCharArray();
            if(arr.length == 0) break;

            if(arr[arr.length-1] == 'A'){
                String k= AA(now);
                s.push(k);
            }

            if(arr[arr.length-1] == 'B'){
                String k= BB(now);
                s.push(k);
            }

            //System.out.println(now);

            if(now.equals(fir)){
                System.out.println(1);
                System.exit(0);
            }


        }

        System.out.println(0);

    }
}

 

 

https://ethereal-coder.tistory.com/98

코드트리 [자바 java] 아름다운 수

https://www.codetree.ai/missions/2/problems/beautiful-number/submissions

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

이 문제는 입력받은 수 길이의 아름다운 수가 얼마나 있는지 계산하는 것이다.

1은 하나씩, 2는 두개씩, 3은 3개씩, 4는 4개씩 한번에 나타나야 한다. 이 문제는 위와 같은 방식이지만, 1,2,3,4를 한 덩어리로 생각해서 배열에 넣어주었다. 이 문제에서 한 덩어리의 수를 넣었을 때 배열을 벗어나는 경우에 대한 예외처리를 해야하는 것을 주의해야 한다.

 

import java.io.*;
import java.util.*;


public class Main {
    static int n;
    static int cnt = 0;
    static int[] arr;



    static void func(int num){
        if(num == n){
            cnt++;
        }
        else{
            for(int i = 1;i<=4;i++){
                if(num+i > n){
                     return;
                }
                else{
                    for(int j = 0;j<i;j++){
                        arr[num + j] = i;
                    }
                    func(num + i);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException{
        // 여기에 코드를 작성해주세요.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        arr = new int[n];
        func(0);
        System.out.println(cnt);

        
    }
}

 

 

느낀점 : 아직 알고리즘을 공부하는데 많이 부족한 것 같아서 앞으로는 기초부분을 더 꼼꼼히 공부해야겠다고 생각했습니다.