[algorithm] 방 번호

방 번호

x
// 방 번호는 4자리
// 숫자 세트는 0~9 숫자 하나씩이 한세트다.
// 방 번호를 충족하기 위해서는 몇 세트가 필요한가?
// * 6과 9는 호환 가능하다. (9999인 경우, '9' 2개와 '6' 2개를 사용해 2세트로 완성 가능하다.)

 

이번 문제는 스터디를하면서 풀게 된 문제이다.

갑자기 풀게 된 문제라 그런지 인터넷에서 내가 문제를 골라서 풀 때랑은 아주 다른 느낌이었다.

나는 단순한 사람이므로 그냥 문제 설명을 들은 대로 풀었다.

숫자가 들어있는 세트를 가지고 숫자를 하나씩 꺼내 방 번호를 완성하는 식이었다.

 

xxxxxxxxxx
import java.util.Arrays;
​
class Solution {
    public static int solution(String room) {
        int result = 1;
        int[] setArr = new int[10];
        String[] roomNumber = room.split("");
​
        for (String i : roomNumber) {
            //System.out.println(i);
            int num = Integer.parseInt(i);
​
            if (setArr[num] >= result) {
                if (num == 6 && setArr[9] < result) {
                    setArr[9]++;
                } else if (num == 9 && setArr[6] < result) {
                    setArr[6]++;
                } else {
                    setArr[num]++;
                    result++;
                }
            } else {
                setArr[num]++;
            }
        }
        return result;
    }
}

result는 사용한 세트 수이다. 시작할 때 세트를 하나 가지고 시작한다.

숫자를 하나씩 꺼내 쓰는데, 세트 수만큼 숫자가 사용되었으면 새로운 세트를 꺼내고(result++) 새 세트에서 숫자를 가져온다.

아주 문제에 충실한 풀이..!

 

내 풀이를 설명한 다음, 다른 분이 푼 풀이를 설명을 들었는데

이건 정말 중고등학생 때 풀던 수리 해결 방식이 생각이 난 풀이였다.

그래서 설명을 듣고 내 방식대로 풀어서 작성해보았다.

수학적으로 접근하면 아래와 같겠지.

 

xxxxxxxxxx
import java.util.Arrays;
​
class Solution {
    public static int solution2(String room) {
        int[] setArr = new int[9];
        String[] roomNumber = room.split("");
​
        for (String i : roomNumber) {
            int num = Integer.parseInt(i);
            if (num == 9)   num = 6;
            setArr[num]++;
        }
​
        setArr[6] = Math.round((float) setArr[6] / 2);
        //System.out.println(setArr[6]);
​
        return Arrays.stream(setArr).max().getAsInt();
    }
}

 

일단 숫자가 몇 번 나오는지 모두 센 다음(6과 9는 호환되므로 함께 세고 중복되는 만큼 빠지도록 2로 나누어 올림해주었다.) 가장 큰 숫자를 찾는다.

숫자는 모두 하나 씩 있기 때문에 가장 많이 나온 숫자에 맞추어 세트 수가 정해진다.

 

이렇게 알고리즘을 수학적으로 접근해야하는데 자꾸 단순하게 접근하게 된다.

알고리즘 풀이에 답은 없다지만, 수학적으로 접근할 수록 그 해결 방법은 더 단순해진다는 걸 알기 때문에 더 아쉬워지는 문제였다.