[Algorithm] 6월 19일 알고리즘 연습 (백준) - 에이젠

백준 2745 진법 변환 - 성공

직접 실행해서 볼땐 에러가 없는데 이러한 런타임에러가 계속 발생하였다.

알고보니 클래스 이름을 Main으로 지어야하는 문제...

내풀이 

class Main {
    public static StringBuilder sb = new StringBuilder();
    //숫자.
    public static String N = "";
    //진법
    public static int B = 0;
    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args){
        input();
        System.out.println(converter());
    }

    public static void input(){
        N = sc.next();
        B = sc.nextInt(); //진법 입력
        return;
    }

    public static int converter(){
        int result = 0;
        int index = 0;
        for(int i = N.length()-1; i >=0; i--){
//            String ss = s.substring(i,i+1);
            char sc = N.charAt(i);
            int num = 0;
            //만약 알파벳이라면
            if(sc >= 'A' && sc <= 'Z'){
                num  = 9 + sc - 'A' + 1 ;
            }
            else{
                num = sc - '0';
            }
            if(index == 0){
                result = result + num;
            }else{
                result = result + num*(int)Math.pow(B,index);
            }
            index++;
        }
        return result;
    }
}

 

 

주로 런타임 에러가 발생하는 경우

배열에 할당된 크기를 넘어서 접근했을 때
전역 배열의 크기가 메모리 제한을 초과할 때
지역 배열의 크기가 스택 크기 제한을 넘어갈 때
0으로 나눌 떄
라이브러리에서 예외를 발생시켰을 때
재귀 호출이 너무 깊어질 때
이미 해제된 메모리를 또 참조할 때

 

 

백준 11005 진법 변환2 - 성공

내풀이

import java.util.Scanner;

class Main {
    public static StringBuilder sb = new StringBuilder();
    //숫자.
    public static int N = 0;
    //진법
    public static int B = 0;
    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args){
        input();
        System.out.println(converter());
    }

    public static void input(){
        N = sc.nextInt();
        B = sc.nextInt(); //진법 입력
        return;
    }

    public static String converter(){
        while(N > 0){
            int rest = N % B;
            //나머지가 10이상이라면 A,B,C...
            char sc = ' ';
            if(rest >= 10){
                sc = (char)('A' + rest - 10);
                sb.append(sc);
            }else{
                sb.append(rest);
            }
            N = N/B;
        }
        String result = sb.reverse().toString();
        return result;
    }
}

 

 

백준 9019 DSLR - 실패

내풀이 : 코드 자체도 길어지고 나머지는 다 통과하는 것 같지만 1000과 1이 입력되었을때 케이스를 해결하지 못함.

class Scratch {
    static StringBuilder sb = new StringBuilder();
    static Scanner sc = new Scanner(System.in);
    static ArrayList<String> list = new ArrayList<>();
    //TestCase
    public static int T = 0;
    
    public static void main(String[] args){
        input();
        for(int i = 0; i < T; i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            solver(a,b);
        }
        for(String s : list){
            System.out.println(s);
        }

    }
    public static void input(){
        T = sc.nextInt();//테스트 케이스 입력

    }

    public static String solver(int input, int output){

        //1. 모두 같은 숫자가 존재한다면. -> L, R
        //숫자는 존재하는데 순서가 엉망이면? 존재하는 숫자 찾아서 이어붙이기
        //2. input > output -> S
        //3. input < output -> D

        String aa = "" + input;
        String bb = "" + output;
        //R,L사용이 가능한 상황이라면
        while(true){
            if(isPossible(aa,bb)){
                //R과 L사
                howShift(aa,bb);
                list.add(sb.toString());
                sb.setLength(0);
                return "";
            }else{ // 불가한 상황이라면
                int intA = Integer.parseInt(aa);
                int intB = Integer.parseInt(bb);
                if(intA > intB){
                    //더 크므로 S 사용
                    intB--;
                    bb = ""+ intB;
                    sb.append('S');
                    continue;
                }else if(intA < intB){
                    //작으면 D사용
                    intA = intA*2;
                    aa = "" + intA;
                    sb.append('D');
                    continue;
                }else if(intA == intB){ //문자열이 같다면 종료

                    list.add(sb.toString()); //초기화
                    sb.setLength(0);
                    return"";
                }

            }
        }

    }
    //시프트로 같게 만들 수 있는지 판단.
    public static boolean isPossible(String aa, String bb){
        String ext = aa.substring(0,1);
        if(bb.contains(ext) && bb.length() == aa.length()){

            int startIndex = bb.indexOf(ext);
            String front = bb.substring(startIndex);
            String back = "";
            if(startIndex == 0) {
                back = bb.substring(0);
            }else{
                back = bb.substring(0,startIndex-1);
            }

            front = front + back;
            if(aa.contains(front)){
                //존재한다면 R,L사용여부 가능.
                return true;
            }
        }//불가능
        else if(bb.contains(ext) && bb.replace("0","").length() == aa.replace("0","").length()){
            
        }
        return false;
    }
    public static void howShift(String aa, String bb){
        String ext = aa.substring(0,1);
        if(bb.contains(ext)){

            int startIndex = bb.indexOf(ext);
            int left = startIndex;
            int right = aa.length() - startIndex;

            //왼쪽이 가깝니 오른쪽이 가깝니.
            if(left > right){ //왼쪽으로 시프트가 더 빠른경우
                for(int i = 0; i < right; i++) {
                    sb.append('R');
                }
            }else{
                for(int i = 0; i < left; i++) {
                    sb.append('L');
                }
            }
        }//불가능
        return ;
    }
}

 

참고한 풀이

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for (int tc = 1; tc <= T; tc++) {
            int A = sc.nextInt(), B = sc.nextInt();
            boolean[] visit = new boolean[10000];
            visit[A] = true;

            Queue<Register> que = new LinkedList<>();
            que.add(new Register(A, ""));

            String ans = "";
            while (!que.isEmpty()) {
                Register cur = que.poll();

                if (cur.num == B) {
                    System.out.println(cur.command);
                    break;
                }

                if (!visit[cur.D()]) {
                    que.add(new Register(cur.D(), cur.command + "D"));
                    visit[cur.D()] = true;
                }
                if (!visit[cur.S()]) {
                    que.add(new Register(cur.S(), cur.command + "S"));
                    visit[cur.S()] = true;
                }
                if (!visit[cur.L()]) {
                    que.add(new Register(cur.L(), cur.command + "L"));
                    visit[cur.L()] = true;
                }
                if (!visit[cur.R()]) {
                    que.add(new Register(cur.R(), cur.command + "R"));
                    visit[cur.R()] = true;
                }

            }
        }

    }

    static class Register {
        int num;
        String command;

        Register(int num, String command) {
            this.num = num;
            this.command = command;
        }

        int D() {
            return (num * 2) % 10000;
        }

        int S() {
            return num == 0 ? 9999 : num - 1;
        }

        int L() {
            return num % 1000 * 10 + num / 1000;
        }

        int R() {
            return num % 10 * 1000 + num / 10;
        }
    }
}

https://girawhale.tistory.com/15

[백준] 9019번: DSLR - JAVA

참고한 풀이 (2)

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
 
        for (int i = 0; i <n ; i++) {
            int a = sc.nextInt();
            int b =sc.nextInt();
            String[] command = new String[10000]; // 정답 담는곳
            boolean[] visited = new boolean[10000]; // BFS 탐색의 방문 여부 체크
            Queue<Integer> q = new LinkedList<>();
 
            visited[a] = true;
            q.add(a);
            Arrays.fill(command,"");
            while (!q.isEmpty() && !visited[b]){
                int now =q.poll();
                int D = (2*now)%10000;
                int S = (now == 0) ? 9999 : now-1;
                int L = (now % 1000) * 10 + now/1000;
                int R = (now % 10) * 1000 + now/10;
 
                if(!visited[D]){
                    q.add(D);
                    visited[D]=true;
                    command[D]=command[now] + "D";
                }
 
                if(!visited[S]){
                    q.add(S);
                    visited[S]=true;
                    command[S]=command[now] + "S";
                }
                if(!visited[L]){
                    q.add(L);
                    visited[L]=true;
                    command[L]=command[now] + "L";
                }
                if(!visited[R]){
                    q.add(R);
                    visited[R]=true;
                    command[R]=command[now] + "R";
                }
            }
            System.out.println(command[b]);
        }
 
    }
}

https://log-laboratory.tistory.com/134

[백준] 9019번 자바 DSLR