[백준] 리모컨 1107번 (🥇 골드5)

사이트

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

문제

 

분석

서론

오랜만에 풀어보는 코테이다! 지난 시험기간 및 동아리 활동때문에 많이 못했다. 
이번 문제는 브로보토스 알고리즘이다. 
설계하는데 시간을 좀 애먹었다.  
 

풀이

사용가능한 번호를 조합을 해서 그 번호가 최종 n이랑 유사해야된다. 
그러기 위해서는 필자는 재귀함수를 사용했다. 

5457
3
6 7 8

 
입력은 위와 같다고 가정 하겠다. 

min = Math.abs(100 - n);

if (100 == n) {
    System.out.println(cnt);
} else {
    solution(0);
    System.out.println(min);
}

 
입력을 하고나서 위와 함수를 들어갈때 위와 같이 작업을 해줘야 된다.
 
맨 첫번째 줄 코드 의미는 번호를 조합했을때 보다 더 버튼을 적게 누를 경우의 수를 대비해서이다.
예를 들어서 n이 101이고 8번을 제외한 모든 번호가 고장나서 8번만 사용할 수 있다고 해보자.
그럼  88 888 이렇게 눌러도 그냥 101 번에서 - 버튼을 누르느게 더 빠르다! 그래서 위와 같이 설정을 해두었다. 
 
또한 n이랑 채널이 같을때를 생각하고 재귀함수로 가게 된다. 
 

private static void solution(int level) {


    if (level != 0 && (sb.toString().length() == String.valueOf(n).length() ||
            sb.toString().length() == String.valueOf(n).length() - 1)) {
        channel = Integer.parseInt(sb.toString());
        cnt = sb.toString().length();
        cnt += Math.abs(n - channel);

        min = Math.min(cnt, min);
    }

    if (sb.toString().length() == String.valueOf(n).length() + 1) {
        channel = Integer.parseInt(sb.toString());
        cnt = sb.toString().length();
        cnt += Math.abs(n - channel);
        min = Math.min(cnt, min);
        return;
    }

    for (int i = 0; i < visit.length; i++) {
        if (!visit[i]) {
            if (level != 0 || i != 0 || String.valueOf(n).length() == 1 || String.valueOf(n).length() == 2) {
                sb.append(i);
                solution(level + 1);
                sb.deleteCharAt(sb.length() - 1);

            }
        }
    }

}

 
여기가 재귀함수 부분이다. 차근차근 보자
 
 
일단 만약 내가 가야되는 채널이 1555 이고, 사용할 수 있는 버튼은 2번하고 8번으로 가정을 해보자 
그럼 2222 또는 888이다. 즉 채널의 경우에 따라서 채널이 5자리 이면 4자리, 3자리도 경우의 수에 포함을 시켜야된다! 
 

if (level != 0 && (sb.toString().length() == String.valueOf(n).length() ||
        sb.toString().length() == String.valueOf(n).length() - 1)) {
    channel = Integer.parseInt(sb.toString());
    cnt = sb.toString().length();
    cnt += Math.abs(n - channel);

    min = Math.min(cnt, min);
}

 
그래서 위 코드가  그것이다. 즉 입력을 아까처럼 했을때 채널은 5457 즉 4자리수 이다. 
level이 0일때를 제외하고 즉 첫번째 실행만 제외하고 두번째 실행부터 sb가 3자리이거나 4자리일때
위 코드를 실행하게 된다.
 

if (sb.toString().length() == String.valueOf(n).length() + 1) {
    channel = Integer.parseInt(sb.toString());
    cnt = sb.toString().length();
    cnt += Math.abs(n - channel);
    min = Math.min(cnt, min);
    return;
}

 
여기서는 이제 5자일때 실행이 된다. 이 코드는 위와 동일하면 단지 return 이 있다. 즉 재귀함수를 끝내기 위함이다. 
 

for (int i = 0; i < visit.length; i++) {
    if (!visit[i]) {
        if (level != 0 || i != 0 || String.valueOf(n).length() == 1 || String.valueOf(n).length() == 2) {
            sb.append(i);
            solution(level + 1);
            sb.deleteCharAt(sb.length() - 1);

        }
    }
}

 
여기서는 if문을 주의를 해야된다. 0일때의 가능성이 있으므로 위와 같이 진행을 해주었다. 
level != 0  i !=0 이거는 0054 00054 이런것을 막기 위함이다. 즉 조금이라도 시간을 벌게...
 
또한 String.valueof(n).length()==1 또는 2 는 원하는 채널이 한자릿수 이거나 두자릿수 일때 0이 필요할 수 있기 때문이다.
 
 

문제점1

그렇게 모든 경우의수를 안고 테스트코드가 다 맞았다.
근데 NullPointer가 84퍼센트에서 뜨는것이다 ㅡㅡㅡㅡㅡㅡ 

m = Integer.parseInt(br.readLine());
if (m != 0) {
    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i = 0; i < m; i++) {
        visit[Integer.parseInt(st.nextToken())] = true;
    }
}

 
입력을 받을 때 위와 같이 작업을 해줘야 된다고 한다. 
왜냐하면 M이 0일때 실행이 되면 애초에 br.readline이 널인 상태로 받아오기 때문에 오류가 난거라고 ... 

 
 
 
처리 시간이 너무 오래걸려서 시간이 남을 때 리펙토링을 좀 해줘야겠다. 
 
 

 

전체코드

package bra;

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

public class Bra1107 {

    static int n;

    static int m;

    static boolean[] visit;

    static int cnt = 0;
    static StringBuilder sb = new StringBuilder();

    static int channel;

    static int min;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        visit = new boolean[10];

        m = Integer.parseInt(br.readLine());
        if (m != 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < m; i++) {
                visit[Integer.parseInt(st.nextToken())] = true;
            }
        }
        min = Math.abs(100 - n);

        if (100 == n) {
            System.out.println(cnt);
        } else {
            solution(0);
            System.out.println(min);
        }

    }

    private static void solution(int level) {


        if (level != 0 && (sb.toString().length() == String.valueOf(n).length() ||
                sb.toString().length() == String.valueOf(n).length() - 1)) {
            channel = Integer.parseInt(sb.toString());
            cnt = sb.toString().length();
            cnt += Math.abs(n - channel);

            min = Math.min(cnt, min);
        }

        if (sb.toString().length() == String.valueOf(n).length() + 1) {
            channel = Integer.parseInt(sb.toString());
            cnt = sb.toString().length();
            cnt += Math.abs(n - channel);
            min = Math.min(cnt, min);
            return;
        }

        for (int i = 0; i < visit.length; i++) {
            if (!visit[i]) {
                if (level != 0 || i != 0 || String.valueOf(n).length() == 1 || String.valueOf(n).length() == 2) {
                    sb.append(i);
                    solution(level + 1);
                    sb.deleteCharAt(sb.length() - 1);

                }
            }
        }

    }
}

 

결과

 

느낀점

 
경우의 수가 너무 많아서 좀 힘들었다 그래서 정답률이 23프로..... 하 그래도 마지막에 다했는데 그놈의 m !=0  때문에
시간을 좀 날렸다....