[알고리즘-자바] 백준 1475번 방 번호

문제

https://www.acmicpc.net/problem/1475

1475번: 방 번호

언어

자바 Java

로직

문제의 핵심포인트는 6과 9를 고려하여 문제를 풀어야 합니다. 6의 경우에 뒤집으면 9가 되고, 9의 경우에 뒤집으면 6이 됩니다. 따라서 66이라는 숫자를 만들기 위해서는 1개의 세트만 있으면 됩니다. 1개의 세트에는 0부터 9까지의 숫자가 들어있고 6과 9를 1개씩 사용하면 66을 만들 수 있기 때문입니다.

 

숫자 저장

0부터 9까지의 숫자를 1개씩 저장합니다.

private static int[] nums = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1};

숫자가 부족할 때

방 번호를 만들기 위한 숫자가 부족한 케이스입니다. 이 경우에는 아래의 2가지 케이스가 있습니다.

1. 6 또는 9가 부족할 때
2. 6과 9가 아닌 숫자가 부족할 때

첫 번째의 경우 6이 부족하다면 9를 가져와서 쓸 수 있고, 9가 부족하다면 6을 가져다가 쓸 수 있습니다. 그렇다고 무작정 가져다 쓸 수 있는 것은 아니고 뒤집은 숫자가 존재해야 사용할 수 있습니다. 

두 번째의 경우에는 1개의 세트를 추가하여 사용할 수 있습니다. 세트를 추가한다는 의미는 0부터 9까지의 숫자를 모두 1개씩 추가한다는 의미입니다.

// 아스키 코드 -> 정수로 변환
int num = Character.getNumericValue(c);

// 숫자가 부족할 때
if (nums[num] == 0) {
	// 6 또는 9
    if (num == 6 || num == 9) {
    	// 6이 부족한 경우
        if (num == 6) {
        	// 9가 존재하는 경우
            if (nums[9] != 0) {
                nums[9] -= 1;
            } 
            // 9가 존재하지 않은 경우
            else {
                fillNum();
                count += 1;
                nums[num] -= 1;
            }
        } 
        // 9가 부족한 경우
        else {
        	// 6이 존재하는 경우
            if (nums[6] != 0)
                nums[6] -= 1;
            // 6이 존재하지 않은 경우
            else {
                fillNum();
                count += 1;
                nums[num] -= 1;
            }
        }
    } 
    // 6과 9가 아닌 숫자
    else {
        fillNum();
        count += 1;
        nums[num] -= 1;
    }
}

숫자가 부족하지 않을 때

가지고 있는 숫자를 바로 사용할 수 있습니다.

else {
    nums[num] -= 1;
}

1세트 추가하기

0부터 9까지의 모든 숫자를 1개씩 추가합니다.

private static void fillNum() {
    for (int i = 0; i <= 9; i++)
        nums[i] += 1;
}

---

코드

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

public class Main {
    private static int[] nums = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1};

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

        String n = br.readLine();

        int count = 1;
        char[] cArr = n.toCharArray();
        for (char c : cArr) {
            int num = Character.getNumericValue(c);
            if (nums[num] == 0) {
                if (num == 6 || num == 9) {
                    if (num == 6) {
                        if (nums[9] != 0) {
                            nums[9] -= 1;
                        } else {
                            fillNum();
                            count += 1;
                            nums[num] -= 1;
                        }
                    } else {
                        if (nums[6] != 0)
                            nums[6] -= 1;
                        else {
                            fillNum();
                            count += 1;
                            nums[num] -= 1;
                        }
                    }
                } else {
                    fillNum();
                    count += 1;
                    nums[num] -= 1;
                }
            } else {
                nums[num] -= 1;
            }
        }

        System.out.println(count);
    }

    private static void fillNum() {
        for (int i = 0; i <= 9; i++)
            nums[i] += 1;
    }
}