[자바] 백준 5671 - 호텔 방 번호 (java)

 문제 : boj5671

---

 

필요 알고리즘 개념

• 브루트 포스
  
  • 모든 경우의 수를 다 살펴보는 것을 뜻한다. 다른 말로 완전탐색 이라 한다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  우선 입력 개수가 주어지지 않은 상태에서 자바에서는 어떻게 입력을 받을 수 있는지부터 살펴보자. BufferedReader를 사용해 받는다고 할 때, EOF(End of file)까지 입력받을 경우 BufferedReader의 readLine 함수에서 null을 리턴해준다. 따라서 아래와 같이 입력받으면 된다. 참고로 IDE 콘솔에서도 EOF를 넣어볼 수 있다. 인텔리제이의 경우엔 ctrl+d를 눌러주면 된다.

while ((s = br.readLine()) != null) {
	...
}

 

 

  그럼 n과 m을 입력받는데 문제가 없었다는 가정하에, n부터 m까지의 모둔 수를 살펴보면서 동일한 숫자가 하나라도 있는지 판단만 해주면 된다. 동일한 숫자가 존재하는지 판단하기 위해 내 경우엔 chk[10] 배열을 선언했다. 숫자 0부터 숫자 9까지가 나온 횟수를 카운팅해주는 배열이라 생각하면 된다. 만약 535 라는 숫자라면, chk[3]은 1이 될 것이고, chk[5]는 2가 될 것이다. 그럼 0<=x<=9에 대해 하나라도 chk[x]가 2가 되는 경우, 중복된 숫자가 존재한 것이라 볼 수 있다.

if (++chk[num%10] == 2)
	return false;

 

 

  그럼 특정 숫자 num에 대해 한 숫자씩 어떻게 뽑아낼 수 있을까? num%10을 해주면 1의 자리의 숫자를 알 수 있다. 그리고 num = num/10을 해주게되면, 봤던 1의 자리숫자를 지워버리고 원래 10의 자리에 있던 수가 1의 자리로 내려오게 된다. 즉 다음 로직으로 해주면 된다.

 

1. chk[num%10] 을 1 증가시켜준다. 2가 되었다면 중복된 수가 있는 것이다.

2. num = num/10을 해준다.

 

1과 2를 num이 0이될때까지 진행해주면 된다.

while (num != 0) {
    if (++chk[num%10] == 2)
        return false;
    num /= 10;
}

 

---

 

코드 : github

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

public class Main {
    private boolean chk(int num) {
        int[] chk = new int[10];
        while (num != 0) {
            if (++chk[num%10] == 2)
                return false;
            num /= 10;
        }
        return true;
    }
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = "";
        StringBuilder sb = new StringBuilder();
        while ((s = br.readLine()) != null) {
            StringTokenizer st = new StringTokenizer(s);
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            int cnt = 0;
            for (int num = n; num <= m; num++) {
                if (chk(num))
                    cnt++;
            }
            sb.append(cnt).append('\n');
        }
        System.out.print(sb);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}