[백준, Java] 14369번, 전화번호 수수께끼 (Small)(백트래킹)

문제 링크

14369번: 전화번호 수수께끼 (Small)

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

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

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 전화번호에 대해서 각 자리를 영어단어로 바꾸고 섞은 값이 주어집니다.

2. 문자열은 대문자로만 이루어져있으며, 유일한 해답이 존재한다.

3. 전화번호는 오름차순으로 정렬되어 있습니다.

4. 영어단어에 대한 전화번호를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 영어 단어에 사용된 알파벳을 기준으로 숫자를 순차적으로 탐색하여 사용된 번호를 찾습니다.

 

3. 찾은 번호를 오름차순 정렬해서 결과로 출력합니다.

 

 

전화번호 탐색(백트래킹)

 

숫자를 대문자 영단어로 표현하면 아래와 같다.

 

0	1	2	3	4	5	6	7	8	9
ZERO	ONE	TWO	THREE	FOUR	FIVE	SIX	SEVEN	EIGHT	NINE

 

영어 단어가 모두 전화번호가 되려면 모든 대문자가 숫자로 변경할 때 이용되어야 합니다.

 

예를 들어,

 

NEO 이라는 단어가 존재할 때

 

N : 1개, E : 1개, O : 1개를 사용해야 합니다.

 

위 3가지를 1개씩 쓰는 영단어는 "1"으로 해당 영단어를 1으로 변경할 수 있습니다.

 

위 같이 영어 단어에서 사용되는 알파벳의 개수를 저장하여 0 ~ 9까지 숫자들을 매칭시켜보면서 영어 단어에 존재하는 모든 알파벳을 사용할 때의 번호 조합을 구해야 하는 것입니다.

 

※예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

 

예제입력 1.

TestCase 1번에 대한 과정을 살펴보겠습니다.

 

1. 입력된 정보를 저장합니다.

 

 

제공한 문자

OZONETOWER

 

 

2. 영어 단어에 사용된 알파벳을 기준으로 숫자를 순차적으로 탐색하여 사용된 번호를 찾습니다.

 

OZONETOWER의 존재하는 알파벳

 

E	N	O	R	T	W	Z
2	1	3	1	1	1	1

 

 

 

해당 알파벳을 모두 사용하는 숫자 조합 탐색(백트래킹)

 

1번째 숫자 0을 사용하였을 때

 

ZERO : (Z = 1, E = 1, R = 1, O = 1)으로써 사용할 수 있습니다.

 

 

현재 사용 숫자 : 0

E	N	O	R	T	W	Z
1	1	2	0	1	1	0

 

2번째 숫자 0 사용하기

 

ZERO : (Z = 1, E = 1,  R = 1, O = 1)으로써 사용할 수 없다.

 

→ Z, R의 개수가 존재하지 않기 때문입니다.

 

2번째 숫자 1 사용하기

 

ONE : (O = 1, N = 1, E = 1)으로써 사용할 수 있다.

 

현재 사용 숫자 : 0, 1

 

E	N	O	R	T	W	Z
0	0	1	0	1	1	0

 

3번째 숫자 0 사용하기

 

ZERO : (Z = 1, E = 1,  R = 1, O = 1)으로써 사용할 수 없다.

 

→ Z, R의 개수가 존재하지 않기 때문입니다.

 

3번째 숫자 1 사용하기

 

ONE : (O = 1, N = 1, E = 1)으로써 사용할 수 없다.

 

→ N, E의 개수가 존재하지 않기 때문입니다.

 

3번째 숫자 2 사용하기

 

TWO : (T = 1, W = 1, O = 1)으로써 사용할 수 있다.

 

현재 사용 숫자 : 0, 1, 2

 

E	N	O	R	T	W	Z
0	0	0	0	0	0	0

 

모든 알파벳을 사용했으므로 해당 영어 단어에 대해서 사용되는 숫자를 모두 탐색하였습니다.

 

→ 탐색 종료!

 

 

 

위 과정처럼 다른 테스트 케이스에 대해서도 백트래킹을 통해서 사용되는 숫자의 조합을 찾습니다.

 

 

 

 

3. 찾은 번호를 오름차순 정렬해서 결과로 출력합니다.

 

영어 단어를 만드는 데 사용한 숫자 : 0, 1, 2

 

오름차순 정렬 진행 : {0, 1, 2}

 

012 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• 영어 단어에 들어가는 알파벳의 개수를 계산합니다.
• seach()을 통해 영어 단어를 만들 수 있는 숫자의 조합을 구합니다.
• 조합에 대해서 오름차순으로 정렬되도록 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• search 함수는 백트래킹을 이용해서 0~9까지 숫자들을 사용하여 영어 단어에 대한 숫자 조합을 탐색합니다.
• reduceAlphabetCount 숫자를 사용하였을 때 알파벳 개수를 줄이는 과정을 진행합니다.
• rollbackAlphabetCount 숫자를 사용한 내역을 취소하는 과정을 진행합니다.
• decodingCompleteCheck 영어 단어에 대한 모든 알파벳을 사용하였는지 확인합니다.

결과코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    // 0 ~ 9 알파벳 대문자 정보
    static final String[] stringOfNumber = {"ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN", "EIGHT", "NINE"};
    //numberCount : 영어 단어 숫자 사용 개수
    //alphabetCount : 영어 단어에 남은 알파벳 개수
    static int[] numberCount, alphabetCount;
    //탐색 종료 관련 Flag 변수
    static boolean endFlag;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        //각 테스트 케이스 진행
        for(int tc=1;tc<=N;tc++){
            String secret = br.readLine();
            alphabetCount = new int[26];
            //영어 단어에 대한 알파벳 개수 계산
            for(int i=0;i<secret.length();i++){
                alphabetCount[secret.charAt(i)-'A']++;
            }
            endFlag = false;
            numberCount = new int[10];
            //백트래킹으로 영어 단어를 만드는 숫자 조합 탐색
            search();
            bw.write(String.format("Case #%d: ", tc));
            //탐색으로 얻은 숫자 조합을 오름차순으로 BufferedWriter 저장
            for(int i=0;i<10;i++){
                for(int j=0;j<numberCount[i];j++){
                    bw.write(String.valueOf(i));
                }
            }
            bw.newLine();
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //백트래킹을 통해서 영어 단어를 만들 수 있는 숫자 조합 탐색
    static void search(){
        //영어 단어를 만들 수 있는 조합인 경우
        if(decodingCompleteCheck()){
            endFlag = true;
            return;
        }
        //0 ~ 9까지 사용해보기
        for(int num=0;num<10;num++){
            if(endFlag){
                return;
            }
            //현재 숫자 사용해보기
            if(reduceAlphabetCount(num)){
                numberCount[num]++;
                search();
                if(endFlag){
                    return;
                }
                numberCount[num]--;
            }
            //현재 숫자 사용한 것 취소
            rollbackAlphabetCount(num);

        }
    }
    //숫자 사용해보기(true : 감소 가능, false : 감소 불가능)
    static boolean reduceAlphabetCount(int num){
        boolean flag = true;
        for(int i=0;i<stringOfNumber[num].length();i++){
            alphabetCount[stringOfNumber[num].charAt(i)-'A']--;
            if(alphabetCount[stringOfNumber[num].charAt(i)-'A'] < 0){
                flag = false;
            }
        }
        return flag;
    }
    //숫자 사용한 정보 되돌리기
    static void rollbackAlphabetCount(int num) {
        for (int i = 0; i < stringOfNumber[num].length(); i++) {
            alphabetCount[stringOfNumber[num].charAt(i) - 'A']++;
        }
    }
    //영어 단어 모든 알파벳 사용하였는지 확인하는 함수
    static boolean decodingCompleteCheck(){
        for(int i=0;i<26;i++){
            if(alphabetCount[i] > 0){
                return false;
            }
        }
        return true;
    }
}