Skip to main content Link Menu Expand (external link) Document Search Copy Copied
Hepheir

1288. 새로운 불면증 치료법

Code Battle (`23 동계 대학생 S/W 알고리즘 특강 기초학습 문제)

본 게시글은 개인 학습 용도로 작성한 게시글입니다.

(문제 출처: SW Expert Academy)

  • 시뮬레이션 (+비트연산)
  • 0~9까지의 숫자의 등장여부를 기록해야 한다.
    • 배열: 10칸의 크기를 갖는 배열의 각 원소에 0~9를 대응시켜서 기록 할 수 있다. 모든 숫자가 등장 했는지 검사하는데 소요되는 시간은 $T(10)$이다.
    • 비트: $2^{10}$ 이상의 표현 범위를 갖는 어떤 값의 각 비트를 0~9를 대응시켜서 기록 할 수 있다. 모든 숫자가 등장 했는지 검사하는데 소요되는 시간은 $T(1)$이다.
  • 비트 연산을 사용하여 각 숫자별 등장여부를 검사한다면 시・공간 자원을 절약할 수 있다.
    • 각 비트에 한 숫자씩 대응시킨다면, 필요한 총 비트 수는 $2^{10}$개로, short 혹은 int 자료형으로 여유있게 커버할 수 있다.
  • 어떤 수 $N$의 각 자리 수를 하나 씩 비교하려면 $T(\log_{10}N)$의 시간이 소요된다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.function.Consumer;

public class Solution {
    public static void main(String[] args) throws Exception {
        // System.setIn(new FileInputStream("sample_input.txt"));
        new Solution();
    }

    private BufferedReader bufferedReader;
    private BufferedWriter bufferedWriter;

    private Solution() throws IOException {
        bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
        solve();
        bufferedReader.close();
        bufferedWriter.close();
    }

    private void solve() throws IOException {
        int T = Integer.parseInt(bufferedReader.readLine());
        for (Integer testCaseNo = 1; testCaseNo <= T; testCaseNo++) {
            bufferedWriter.write("#"+testCaseNo+" "+solveTestCase()+"\n");
        }
    }

    private Integer solveTestCase() throws IOException {
        return solveTestCase(Integer.parseInt(bufferedReader.readLine()));
    }

    private Integer solveTestCase(Integer number) {
        return solveTestCaseViaBitmasking(number);
    }

    private int bitmaskedVisitedDigits;

    private int solveTestCaseViaBitmasking(int baseNumber) {
        clearBitsOfDigit();
        int currentNumber = 0;
        while (!isAllBitsOfDigitSet()) {
            currentNumber += baseNumber;
            forEachDigit(currentNumber, this::setBitOfDigit);
        }
        return currentNumber;
    }

    private void clearBitsOfDigit() {
        bitmaskedVisitedDigits = 0b0000000000;
    }

    private void forEachDigit(int n, Consumer<Integer> callback) {
        while (n > 0) {
            callback.accept(n % 10);
            n /= 10;
        }
    }

    private void setBitOfDigit(int digit) {
        bitmaskedVisitedDigits |= 1 << (digit % 10);
    }

    private boolean isAllBitsOfDigitSet() {
        return (bitmaskedVisitedDigits ^ 0b1111111111) == 0;
    }
}

Back to top