9575번: 백준 - 행운의 수(Java)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

문제 출처 : https://www.acmicpc.net/problem/9575

[문제 설명]

3개의 배열이 주어지고 각 배열에서 숫자를 하나씩 뽑아 더했을 때 합을 구한다.

그 합이 5와 8로만 이루어졌으면 이 숫자는 행운의 숫자다.

행운의 숫자의 총 개수를 구하시오.

 

[접근 방법]

제약 조건
수열 크기는 50을 넘지 않고, 원소는 30,000보다 작거나 같은 양의 정수 1<= 원소의 값 <= 30,000

1. 완전 탐색으로 풀기.
시간 복잡도 O(n^3) -> 50^3 ->125,000
문제에선 중복된 숫자는 같은 걸로 처리함.

2. 중복을 처리할 수 있는 방법들
2.1 해시셋
2.2 배열을 이용하여 방문처리
만족하는 원소 개수(행운의 숫자 개수)가 k개라고 했을 때,
공간복잡도는 해시셋은 O(k), 배열은 무조건 90,000(원소의 크기가 최대 3만이고 수열의 개수가 3개니까)
해시셋의  경우 모든 요소를 찾는데 O(k)가 걸리지만, 배열은 최소 90,000이 걸린다.
그러나, 문제의 조건은 모든 숫자를 찾는 것이 아닌 개수를 구하는 것이므로 배열을 사용하겠다.(해싱 함수에도 시간이 걸리므로, 배열이 빨라 보여서)

 

[Java 코드]

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

public class Main {
    static boolean[] isCheckedLuckyNumber;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cntOfTestcases = Integer.parseInt(br.readLine());

        // 테스트 케이스 수만큼 반복
        for (int noOfTestcases = 1; noOfTestcases <= cntOfTestcases; noOfTestcases++) {
            int[][] sequences = new int[3][];

            // 배열의 개수(3)만큼 반복
            for (int noOfSequences = 0; noOfSequences < sequences.length; noOfSequences++) {
                int size = Integer.parseInt(br.readLine());
                StringTokenizer st = new StringTokenizer(br.readLine()," ");

                sequences[noOfSequences] = new int[size];
                //배열 채우기
                for (int idxOfSequence = 0; idxOfSequence < size; idxOfSequence++) {
                    int number = Integer.parseInt(st.nextToken());
                    sequences[noOfSequences][idxOfSequence] = number;
                }
            }

            isCheckedLuckyNumber  = new boolean[90001];
            System.out.println(getCntOfLuckNumber(sequences,0,0));
        }
    }

    private static int getCntOfLuckNumber(int[][] sequences, int currentNumber, int idxOfSequences) {
        int answer = 0;
        if (idxOfSequences == sequences.length) {
            // 이전에 체크한 숫자면 이미 추가한 행운의 숫자거나, 행운의 숫자가 아님
            if (isCheckedLuckyNumber[currentNumber]) {
                return 0;
            }
            // 방문 여부 체크
            isCheckedLuckyNumber[currentNumber] = true;
            // 행운의 숫자면 총 개수에 1을 더해줌
            if (checkIsLuckyNumber(currentNumber)) {
                return 1;
            }

            // 행운의 숫자가 아니므로 더하지 않음
            return 0;
        }

        // 현재 선택한 수열
        int[] currentSequence = sequences[idxOfSequences];
        for (int valOfSequence : currentSequence) {
            answer += getCntOfLuckNumber(sequences, currentNumber+valOfSequence, idxOfSequences+1);
        }

        return answer;
    }

    // 5,8로만 이루어진 숫자인지 확인하는 메소드
    private static boolean checkIsLuckyNumber(int currentNumber) {
        do {
            if (currentNumber % 10 != 5 && currentNumber % 10 != 8) {
                return false;
            }
            currentNumber /= 10;
        } while (currentNumber > 0);

        return true;
    }
}

 

[리팩토링]

getCntOfLuckyNumber 메소드에 if문이 맘에 안들어서 수정 했다.

// 수정 전
private static int getCntOfLuckNumber(int[][] sequences, int currentNumber, int idxOfSequences) {
    int answer = 0;
    if (idxOfSequences == sequences.length) {
        if (isCheckedLuckyNumber[currentNumber]) {
            return 0;
        }
        isCheckedLuckyNumber[currentNumber] = true;
        if (checkIsLuckyNumber(currentNumber)) {
            return 1;
        }

        return 0;
    }
   
// 수정 후
private static int getCntOfLuckNumber(int[][] sequences, int currentNumber, int idxOfSequences) {
    int answer = 0;
    if (idxOfSequences == sequences.length) {
        if (!isCheckedLuckyNumber[currentNumber]) {
            isCheckedLuckyNumber[currentNumber] = true;
            if (checkIsLuckyNumber(currentNumber)) {
                return 1;
            }
        }

        return 0;
    }

 

[최종 코드]

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

public class Main {
    static boolean[] isCheckedLuckyNumber;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cntOfTestcases = Integer.parseInt(br.readLine());

        for (int noOfTestcases = 1; noOfTestcases <= cntOfTestcases; noOfTestcases++) {
            int[][] sequences = new int[3][];

            for (int noOfSequences = 0; noOfSequences < sequences.length; noOfSequences++) {
                int size = Integer.parseInt(br.readLine());
                StringTokenizer st = new StringTokenizer(br.readLine()," ");

                sequences[noOfSequences] = new int[size];
                for (int idxOfSequence = 0; idxOfSequence < size; idxOfSequence++) {
                    int number = Integer.parseInt(st.nextToken());
                    sequences[noOfSequences][idxOfSequence] = number;
                }
            }

            isCheckedLuckyNumber  = new boolean[90001];
            System.out.println(getCntOfLuckNumber(sequences,0,0));
        }
    }

    private static int getCntOfLuckNumber(int[][] sequences, int currentNumber, int idxOfSequences) {
        int answer = 0;
        if (idxOfSequences == sequences.length) {
            if (!isCheckedLuckyNumber[currentNumber]) {
                isCheckedLuckyNumber[currentNumber] = true;
                if (checkIsLuckyNumber(currentNumber)) {
                    return 1;
                }
            }

            return 0;
        }

        int[] currentSequence = sequences[idxOfSequences];
        for (int valOfSequence : currentSequence) {
            answer += getCntOfLuckNumber(sequences, currentNumber+valOfSequence, idxOfSequences+1);
        }

        return answer;
    }

    private static boolean checkIsLuckyNumber(int currentNumber) {
        do {
            if (currentNumber % 10 != 5 && currentNumber % 10 != 8) {
                return false;
            }
            currentNumber /= 10;
        } while (currentNumber > 0);

        return true;
    }
}

14명중 1등~ 이럴 때 아니면 언제 1등하냐~