[240216] 알고리즘 리부트 8일차 - 백준 10448, 11005, 11068 자바

[Part1-Chapter04-Clip02]

-백준 10448 유레카 이론

 

 

아무리 생각해도 재귀가 아니라면 반복문을 3중으로 돌리는 수밖에 없다고 생각해서 아래와 같이 3중 반복문을 구현하여 돌렸다. 불필요한 순회를 줄이기 위해 찾으면 바로 반복문을 빠져나오도록 처리했다.

 

package BaekJoon.bruteforce;

import java.util.Arrays;
import java.util.Scanner;

public class BJ10448 {
    public static void main(String[] args) {
        solve();

    }


    private static void solve() {
        Scanner sc = new Scanner(System.in);

        int t = sc.nextInt();

        String ans = "";

        while (t-- > 0) {

            int n = sc.nextInt();
            int[] arr = new int[n + 1];

            arr[1] = 1;

            for (int i = 1; i <= n; i++) {
                arr[i] = arr[i - 1] + i;
            }

            //System.out.println(Arrays.toString(arr));

            boolean find = false;
            outer:
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    for (int k = 1; k <= n; k++) {
                        if (arr[i] + arr[j] + arr[k] == n) {
                            ans += "1" + "\n";
                            find = true;
                            break outer;
                        }
                    }
                }
            }

            if (!find) {
                ans += "0" + "\n";
            }
        }

        System.out.println(ans);
    }
}

 

그리고 아래는 강사님의 풀이이다. 삼각수를 매번 구하지 않고 배열을 만들어 놓음으로써 불필요한 연산을 줄였다. 또 한가지 흥미로운 점은 나는 삼중 반복문을 사용했는데 최대한 시간복잡도를 줄이기 위해 두개의 합을 먼저 구한 후에 1개의 수를 나중에 더했다는 점이다. 그 와중에도 두개의 합이 1000이 넘어버리면 가차없이 고려하지 않도록 설계함.. 이렇게 시간 복잡도를 세세하게 설계할 수 있다니 머리가 복잡한데 또 습관처럼 생각해야 하는 것 같다. 확실히 메모리와 시간을 덜 사용하는 것을 알 수 있다. 

 

package BaekJoon.bruteforce;

import java.util.Arrays;
import java.util.Scanner;

public class BJ10448_1 {
    public static int[] triangleNum = new int[50];
    public static boolean[] isSumOfTriangle = new boolean[1000];
    public static boolean[] isEurekaNum = new boolean[1001];

    public static void main(String[] args) {
        preprocess();

        Scanner sc = new Scanner(System.in);

        int t = sc.nextInt();

        while (t-- > 0) {
            int n = sc.nextInt();
            System.out.println(isEurekaNum[n] ? 1 : 0);
        }


    }

    private static void preprocess() {

        // 1000 미만까지의 삼각수 만들어 놓기
        int k = 1000;
        int idx = 1;

        for (int i = 1; ; i++) {
            //System.out.println("i: " + i);
            int thisNum = i * (i + 1) / 2;
            if (thisNum >= k) {
                //System.out.println(i);
                break;
            }
            triangleNum[idx++] = thisNum;
            //System.out.println("thisNum: "+thisNum);
        }
        //System.out.println(idx);
        //System.out.println(Arrays.toString(triangleNum));

        // 세개의 삼각수의 합으로 표현이 되는 수인지 확인
        // 단순히 삼중 반복문 대신 이중 반복문으로만 처리해서 시간 복잡도 줄이기
        // 1000 이하의 삼각수를 가지는 인덱스를 idx로 구했으니 활용!
        for (int i = 1; i < idx; i++) {
            for (int j = 1; j < idx; j++) {
            // 두개의 수가 천보다 작아서 다른 한 수를 더 더해 타겟 수가 될 수 있다면
                if (triangleNum[i] + triangleNum[j] < 1000) { 
                    // 가능성이 있는 두개의 조합이니 true로 만들어줌
                    isSumOfTriangle[triangleNum[i] + triangleNum[j]] = true;             
                }
            }
        }

        for (int i = 1; i < 1000; i++) {
            if (isSumOfTriangle[i]) { // 천을 넘지 않는 조합이었다면
                for (int j = 1; j < idx; j++) { // 나머지 한 수 더해보자
                    int eurekaNum = i + triangleNum[j]; // 세 수의 합을 정의하고
                    if (eurekaNum > 1000) break; // 천 보다 크면 버리고
                    isEurekaNum[eurekaNum] = true; // 천보다 작으면 그 인덱스를 true로 변경
                }
            }
        }


    }
}

 

[Part1-Chapter04-Clip03]

-백준 11005 진법 변환 2

 

 

문제를 봤을 때는 나는 2진법이랑 10진법 밖에 모르는데 어떡하지 라는 생각이 들었지만 브론즈 문제야 정신차려.. 라는 생각으로 다시 고민해봤다. 결국 숫자로 표시할 수 없는 자리는 A부터 Z까지의 알파벳으로 대체해서 표현하면 된다였다. 필요한 연산은 정수 나눗셈과 나머지를 구하는 연산 두개뿐.. 초반에 당황한 건 10진법 외의 수는 생각해 본적이 극히 드물다는 이유라고 생각한다. 

 

그래서 일단 해당하는 진법 수로 숫자를 나눠주고 나머지를 stringBuilder에 담는다. 마지막은 while문 밖에서 더해준다. 이 때 주의할 점은 10진법부터는 알파벳으로 값을 넣을 수 있도록 아스키 코드를 활용하는 것이다. 진법 수 10에 55를 더해서 A의 아스키 코드 65를 만들어주는 방식으로 처리했다. 

 

package BaekJoon.bruteforce;

import java.util.Scanner;

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

        int n = sc.nextInt();
        int b = sc.nextInt();

        int remaining = 0;


        StringBuilder sb = new StringBuilder();

        while (n >= b) {

            remaining = n % b;

            n /= b;

            System.out.println("remaining: " + remaining);
            System.out.println("n: " + n);

            if (remaining >= 10) {
                // 10에 55를 더하면 65니까 'A'
                remaining += 55;
                sb.append((char) remaining);
            } else {
                sb.append(remaining);
            }

        }
        if (n >= 10) {
            n += 55;
            sb.append((char) n);
        } else {
            sb.append(n);
        }


        System.out.println(sb.reverse().toString());
    }
}

 

 

[Part1-Chapter04-Clip04]

-백준 11068 회문인 수

 

 

장담하건대 위의 문제를 풀지 않았다면 많은 고민을 했을 것 같은 문제였다. 위와 동일하게 접근했고 처음에는 그냥 나눈 수 그대로를 문자열에 더하고자 했다. 제출하니 1%에서 틀려버림. 고민해봤다. 왜 틀렸을까 생각해보니 나머지를 더해가면서 의도치 않게 한개의 연산이 아닌 복수의 연산을 통해 다른 수와 연속적으로 결합되면 팰린드롬이 될 수도 있다는 것이었다. 그래서 결국 위 문제처럼 나머지를 문자로 치환해서 더해주는 방식으로 진행했다. 대문자부터 소문자 그리고 특수기호까지 아스키 코드를 활용하게 된 것 같다. 그 코드 안에 동일한 문자는 없으니 어떤 문자든 아무래도 상관없었다. 

 

진짜 바보같은 소리였다..하하 아래와 같은 이유로 팰린드롬을 판별하는  데 실패했던 거였다. 분명 알고 있었고 배웠던 건데 말이죠? 그래서 강사님은 각각의 배열에 나머지를 담아서 처리하고 계셨다.. 하하 문자열을 이용할거면 한 글자인 문자로 치환해서 처리~~! 방법은 맞았으나 근거가 야무지게 틀려버림^0^;;;

 

package BaekJoon.bruteforce;

import java.util.Scanner;

public class BJ11068 {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int t = sc.nextInt();

        String ans = "";

        while (t-- > 0) {
            System.out.println("========================================");

            int n = sc.nextInt();

            boolean palindrome = false;

            for (int i = 2; i <= 64; i++) {
                System.out.println("i: " + i);

                int thisNum = n;

                StringBuilder sb = new StringBuilder();

               // 단순히 수를 더하면 안되는 이유가
			   // StringBuilder에 2자리 수 이상의 수를 단순히 이어붙여버리면 회문이 안됨 
               // 11 62 62 11 은 회문인데 단순히 문자열로 보면 회문이 아니게 됨
               // 그래서 숫자를 하나의 문자열로 치환해주는 거임
                while (thisNum >= i) {
                    int remaining = thisNum % i;

                    if (i > 10) {
                        remaining += 55;
                        sb.append((char) remaining); // 어쨌든 다른 문자만 더해지면 되니까...
                    } else {
                        sb.append(remaining);
                    }

                    thisNum /= i;

                    System.out.println("thisNum: " + thisNum);
                    System.out.println("remaining: " + remaining);
                }
                if (i > 10) {
                    thisNum += 55;
                    sb.append((char) thisNum);
                } else {
                    sb.append(thisNum);
                }

                String originOrder = sb.toString();
                String reverseOrder = sb.reverse().toString();

                System.out.println("originOrder: " + originOrder);
                System.out.println("reverseOrder: " + reverseOrder);

                if (originOrder.equals(reverseOrder)) palindrome = true;

                if (palindrome) {
                    ans += "1" + "\n";
                    break;
                }

            }

            if (!palindrome) {
                ans += "0" + "\n";
            }


        }
        System.out.println(ans);
    }
}