회고 및 문제해결

BOJ1009 분산처리

• 진법과의 관련성을 고민해보았지만, 쉽지 않을 거라는 생각에 규칙을 먼저 찾게 되었다.
• 규칙은 제곱을 여러번 반복했을 때, 1의 자리는 일정하게 나타난다.
• 계속 같은 수를 반복하는 경우도 있었고, 두번, 네번 반복하는 규칙이 있었다.
• 하나 하나 케이스를 나누기보다는 몇번의 반복이 더 진행 될 수 있겠지만 지수를 4로 나눠서 나머지를 통해서 제곱횟수를 최소화하는 방식으로 구현하였다.

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

public class BOJ1009 {

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(bufferedReader.readLine());
        StringTokenizer stringTokenizer;

        StringBuilder stringBuilder = new StringBuilder();
        while (T-- > 0) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int base = Integer.parseInt(stringTokenizer.nextToken());
            int exponent = Integer.parseInt(stringTokenizer.nextToken());

            int lastIndex = findLastIndex(base, exponent);
            stringBuilder.append(lastIndex).append('\n');
        }
        System.out.println(stringBuilder.toString());

    }

    static int findLastIndex(int base, int exponent) {
        int exp = exponent % 4 + 4;

        int index = base; // index(찾고자하는 순서) -> base 값으로 초기화해서 반복을 1부터 시작
        for (int i = 1; i < exp; i++) {

            index = (index * base) % 10;
        }

        if (index == 0) { // 1부터 10으로 순서를 찾기때문에 0은 10으로 변환
            index = 10;
        }

        return index;
    }
}

BOJ1076 저항

• 색상별로의 저항 값과 곱을 어떻게 처리하는지가 키포인트이다.
• 처음에 보자마자 Map이 떠올라서 Map으로 구현하게 되었다.
• 저항 값과 곱이 인덱스로 처리하기에도 간편하게 되어있는 문제이기도 했지만, 리뷰하면서 들은 내용으로는 성능 측면에서는 Map을 선택하는 것이 맞는 것 같다.
  (enum으로 구현해서 enumMap으로 처리하는 것이 HashMap보다도 더 성능이 좋다고 한다.)
• 답을 계산할 때, 숫자를 모두 String으로 처리하는 것이 더 단순할 것 같아서 StringBuilder를 통해서 처리했다.
• 하지만, 합과 곱이 포함되어있었기에 0이 들어가는 경우를 예외처리하지않으면, String으로 출력하지 못한다.
• 이 부분도 예외처리하기보다는 단순히 출력을 long으로 변환하는 것으로 해결했다.
• 성능적인 면이나 기능의 확장성을 고려한다면 오류가 발생할지도?

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

public class BOJ1076 {
    static final Map<String, Integer> COLOR_MAP = Map.of("black", 0,
            "brown", 1,
            "red", 2,
            "orange", 3,
            "yellow", 4,
            "green", 5,
            "blue", 6,
            "violet", 7,
            "grey", 8,
            "white", 9);
    static StringBuilder stringBuilder = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        String first = bufferedReader.readLine();
        String second = bufferedReader.readLine();
        String third = bufferedReader.readLine();

        long resist = Long.valueOf(findResistance(first, second, third));
        System.out.println(resist);
    }

    static String findResistance(String first, String second, String third) {
        stringBuilder.append(findValue(first)).append(findValue(second));
        multiply(third);
        return stringBuilder.toString();
    }

    static String findValue(String color) {
        return String.valueOf(COLOR_MAP.get(color));
    }

    static void multiply(String color) {
        int multiplier = COLOR_MAP.get(color);
        stringBuilder.append("0".repeat(multiplier));
    }
}

BOJ1052 물병

• 가장 많은 것을 고민하게하고, 알고리즘 문제의 출제 의도에 대해서 생각하게 하는 문제였다.
• 처음에는 요구사항을 제대로 이해하지 못해서 K개의 물병이 모두 같은 양의 물로 채울 수 있는 경우를 구하는 것으로 해석했다.
• 하지만 단순히 k개 이하의 물병으로 만드는 것이 제대로된 이해였다.
• 그 와중에 문제 밑에 비트마스크라는 키워드를 보게 되었고, 찾아보게되었다(정확히는 이해 못했음 ㅎ). 이 문제와는 결이 조금 다른 것같지만 이진법을 활용하는 것은 분명했다. (다르게 풀이할 수 도 있지만)
• 처음에 모든 물병에는 물이 1리터씩 들어있다. 상점에서 사는 물병은 물이 1리터 들어있다. 같은 양의 물이 들어있는 물병 두 개를 고른다. -> 다른 양이 들어있는 물병끼리는 합칠 수 없다.
  이진법으로 생각하게 되니 이러한 특이한 요구사항이 힌트였음을..
• 비트마스크 공부를 해보자..

  n += n & (-n)로 제출했을 때 128ms, n++ 로 제출했을 때 324ms로 성능차이가 났다.
  200ms가 실질적인 프로그램에서의 성능차이가 클까?

문제 이해하기

1. 1리터가 든 물병은 이진수로 표현하면 0001이다.
2. 1리터물병 + 1리터물병 = 2리터물병 -> 0001 + 0001 = 0010
3. 마찬가지로 2리터물병 + 2리터물병 = -> 0010 + 0010 = 0100이 된다. 결론적으로 2의 제곱수는 물병 하나만으로도 옮길 수 있다.
4. 1리터물병 + 2리터물병 != 3리터물병 -> 0001 + 0010 = 0011 -> 2리터물병 하나, 1리터물병 하나
5. 문제의 요구사항 중 같은 양의 물이 들어있는 물병 두 개를 고른다. -> 다른 양이 들어있는 물병끼리는 합칠 수 없다.
   이러한 사항 때문에 이진수안의 1의 갯수와 k의 갯수를 비교하면된다.
6. 물병을 상점에서 구매하는 것은 1 == 0001이 추가되는 것이다. 기존의 물병의 갯수에 1이 더해지면서 물병 갯수는 증가하지만 이진수로 보면 1의 갯수가 줄어들 수 있다.(물병이 합쳐지는 것과 같은 원리)
7. 예시1) 1리터물병 17개가 있다면 (17 == 10001) 합치는 과정을 통하면, 16리터물병 하나와 1리터물병 하나로 2개의 물병만으로 옮길수 있다.

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

public class BOJ1052 {

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int N = Integer.parseInt(stringTokenizer.nextToken());
        int K = Integer.parseInt(stringTokenizer.nextToken());

        System.out.println(countBottle(N, K));

    }

    static int countBottle(int n, int k) {
        int bottles = n; // 처음 주어진 물병의 갯수를 저장
        while (true) {
            int count = countTrue(n);

            if (count <= k) { // 합친 물병의 갯수가 요구하는 물병의 갯수 k보다 작거나 같으면 반복 종료
                break;
            }
            n += n & (-n); // 128ms 물병을 하나 구매한다.
            //n++; 324ms
        }
        return n - bottles; // 구매한 물병의 갯수를 반환
    }

    static int countTrue(int n) {
        int count = 0; // 2진수에서 1의 갯수를 카운트
        while (n != 0) {
            if ((n & 1) == 1) { // 홀짝 확인. 홀이면 카운트
                count++;
            }
            n >>= 1; // 비트밀어내기
        }
        return count;
    }
}

BOJ10757 큰 수 A+B

• 숫자를 덧셈할 때 고려해야하는 부분이 올림수이기 때문에, 숫자를 뒤집는 것이 키포인트이지 않을까?
• 순서를 뒤집지말고, 마지막 index부터 찾아서 계산하고 그때그때 StringBuilder에 집어넣는 식으로 구현했다.
• Stringbuilder에는 reverse() 함수가 너무나도 간편하기 때문에...

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

public class BOJ10757 {
    static StringBuilder stringBuilder = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine()," ");

        String first = stringTokenizer.nextToken();
        String second = stringTokenizer.nextToken();

        String answer = pulsBigNum(first, second);
        System.out.println(answer);

    }

    static String pulsBigNum(String first, String second) {

        int firstIndex = first.length()-1; // 첫번째숫자의 인덱스
        int secondIndex = second.length()-1; // 두번째숫자의 인덱스
        int carry = 0; // 올림수 0으로 초기화

        while(firstIndex >= 0 || secondIndex >= 0) {
            int sum = 0;

            if(firstIndex >= 0) {
                sum += first.charAt(firstIndex) - '0';
                firstIndex--;
            }
            if(secondIndex>=0) {
                sum+= second.charAt(secondIndex) - '0';
                secondIndex--;
            }

            sum += carry;
            carry = sum / 10; // 올림수 저장
            stringBuilder.append(sum % 10); // 1의 자리수만 더하기
        }

        if(carry > 0) {
            stringBuilder.append(carry);
        }

        return stringBuilder.reverse().toString();
    }

}