이전 알고리즘 스터디세션에서 풀었던 백준의 브루트포스 문제이다.
정말 여러가지 방식을 시도해봤고, 각각 시도해본 방식들마다 배운점을 정리하려고 한다.
첫번째 시도 : 수학적 계산법 시도해보기
기본적인 아이디어는 아래와 같았다.
자리수마다 가장 가까운 숫자를 찾고, 다음 자릿수에서는 앞자리수에서 선택한 값을 고려해서 가장 가까운 숫자를 찾고, 이를 반복해보자.
로직이 좀 복잡한데, 정리하면 아래와 같다.
1. 매번 자리수에서, 누를 수 있는 가장 가까운 수를 찾는다.
2. 만약 아래위로 거리가 같은 숫자가 있다면 (ex. 목표가 5고 5,6을 누를 수 있을 때) 두번째 자리수에서 누를 수 있는 숫자가 5보다 작을 때는 더 작은 수 선택 (52면 5선택, 58이면 6선택)
3. 만약 아래위로 거리가 다르다면, 아래위로 가능한 숫자중에서 먼저 가능한 숫자를 그냥 할당한다. (ex. 목표가 5고, 아래에서는 4가되고 위에서는 7이된다면 그냥 4 선택)
package prob14;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class DayProb14 {
private static int[] remote = new int[10];
private static String goal;
public static void main(String[] argv) throws IOException {
for (int i = 0; i < 10; i++){
remote[i] = i;
}
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
goal = br.readLine();
int goalInt = Integer.parseInt(goal);
int N = Integer.parseInt(br.readLine());
if (N > 0){
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++){
int broken = Integer.parseInt(st.nextToken());
remote[broken] = 10;
// System.out.println(broken);
}
}
// 그냥 시작이 100인 경우
if (goalInt == 100) {
System.out.println("0");
} else {
String result = minClick(0);
int resultLen = result.length();
int resultInt = Integer.parseInt(result);
System.out.println(resultLen + Math.abs(resultInt - goalInt));
}
}
// 칠 수 있는 제일 가까운 숫자를 찾는 함수
private static String minClick(int cur){
if (cur == goal.length()) {return "";}
int now = goal.charAt(cur) - '0';
for (int i = 0; i < 9; i++){
if (now + i + 1 < 10 && now - i >= 0 && remote[now + i + 1] != 10 && remote[now - i] != 10){
String next = minClick(cur + 1);
if (next != "" && next.charAt(0) != goal.charAt(cur + 1)){
int nextFirst = next.charAt(0) - '0';
if (nextFirst < 5) {
int here = now + i + 1;
return here + next;
}else {
int here = now - i;
return here + next;
}
}
}
if (now - i >= 0 && remote[now - i] != 10) {
return remote[now - i] + minClick(cur + 1);
}
if (now + i + 1 < 10 && remote[now + i + 1] != 10) {
return remote[now + i + 1] + minClick(cur + 1);
}
}
// 이게 나오면 문제가 오류가 있는 경우임. (컴파일을 위해 추가)
return "@";
}
}하지만 이 로직 자체는 그냥 틀린 로직이었다.
- 첫째 자릿수에서 가장 가까운 수를 찾아야되는건 맞는데,
그 다음자릿수도 가장 가까운 수를 찾아야되는건 아님. - 80000 에서, 8이 안되면 7을 찾고 그 다음으로 이동하느데, 그 다음은 그냥 또 0이랑 가까운거를 찾음. -> 앞에 8의 결과와 전혀 무관하게 되버림..
- 98~102 사이고, 직접 입력할 수 없는 경우, 101 은 입력할 수 있는데 100은 못하는 엣지케이스는 고려되지 않았음.
이런방식으로는 풀 수 없다는 것을 깨닫고, 그냥 곱게 브루트포스로 풀기로 했다.
두번째 시도 : 브루트 포스 1
- remote 배열은 유지
- goal 값으로부터 +1, -1을 해나가면서, 해당 숫자들이 remote 배열만으로 만들 수 있는지를 확인
- remote 배열 안에 있는지 확인하는데는 O(1)
- 채널의 최대 자리수는 6
- 가장 가까운 수와의 최대 차이는 500,000
- 2 * 6 * 500,000 만큼의 계산이 필요하며 크진 않은 수치임
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static int[] remote = new int[10];
private static String goal;
public static void main(String[] argv) throws IOException {
for (int i = 0; i < 10; i++){
remote[i] = i;
}
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
goal = br.readLine();
int goalInt = Integer.parseInt(goal);
int N = Integer.parseInt(br.readLine());
if (N > 0){
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++){
int broken = Integer.parseInt(st.nextToken());
remote[broken] = 10;
}
}
if (goalInt == 100) {
System.out.println("0");
} else {
int moveInt = minClick2(goalInt);
String result = moveInt + "";
int resultLen = result.length();
System.out.println(resultLen + Math.abs(moveInt - goalInt));
}
}
private static int minClick2(int goalInt){
int plus = 0;
int minus = 0;
while(true){
if (move(goalInt + plus++)){
return goalInt + (plus - 1);
} else if (goalInt + minus > 0 && move(goalInt + minus--)){
return goalInt + (minus + 1);
}
}
}
private static boolean move(int moved){
String newGoal = moved + "";
for (int i = 0; i < newGoal.length(); i++){
int target = newGoal.charAt(i) - '0';
if (remote[target] == 10) {
return false;
}
}
return true;
}
}분명되야하는데 시간초과가 떴다.
이때 이 문제가 엣지케이스를 아주 치밀하게 고려해야하는 까다로운 문제라는 점을 깨달았다.
[내가 찾은 문제점]
- edge case 1 : 모든 버튼이 고장난 경우 (무한루프를 돌게 됨)
- edge case 2 : 100 - goalInt가 더 작은 경우
- minClick2에서 +1을 먼저함. +1, -1 둘다 가능하지만 자릿수가 더 작아지는 경우에는 해당 값을 리턴해야함.
위 3가지 case 를 고쳐야 함.
세번째 시도 : 엣지케이스 고려
- 모든 버튼이 고장난 경우에는 그냥 바로
100 - goalInt를 반환하게 했다. - 결과 계산값과,
100 - goalInt값중에 더 작은 값을 반환하게 했다.
if (goalInt == 100) {
System.out.println("0");
} else if (N == 10) {
System.out.println(Math.abs(100 - goalInt));
} else {
int moveInt = minClick2(goalInt);
String result = moveInt + "";
int resultLen = result.length();
System.out.println(Math.min(resultLen + Math.abs(moveInt - goalInt), Math.abs(100 - goalInt)));
}- 만약 목표가 1000이고 999, 1001이 가능하다면, 자리수가 더 작은 999를 골라야 하므로, 마이너스 연산을 먼저하도록 바꿨다.
private static int minClick2(int goalInt){
int plus = 0;
int minus = 0;
while(true){
if (goalInt + minus >= 0 && move(goalInt + minus--)){
return goalInt + (minus + 1);
} else if (move(goalInt + plus++)){
return goalInt + (plus - 1);
}
}
}드디어 성공 !
스터디원의 풀이
같이 하는 스터디원의 풀이이다. 배운점이 많아서 정리하려고 한다.
package test;
import java.util.*;
import java.io.*;
public class Main {
// 0~9까지 고장여부
public static boolean[] isBroken = new boolean[10];
public static void main(String args[]) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int M = Integer.parseInt(st.nextToken());
if(M != 0) {
st = new StringTokenizer(br.readLine());
for(int i=0; i<M; i++) {
int btn = Integer.parseInt(st.nextToken());
isBroken[btn] = true;
}
}
// answer의 초기값 : 그냥 + 버튼이나 - 버튼만으로 N까지 가는 횟수
int answer = Math.abs(100 - N);
// 10^6까지 반복하는 이유: 버튼 9빼고 다고장나면
// 500000 을 위해 999999등을 눌러야할수도...
for(int i=0; i<=1000000; i++) {
if(isPossible(i)) {
int press = String.valueOf(i).length();
int move = Math.abs(N-i);
answer = Math.min(answer, press+move);
}
}
System.out.println(answer);
}
public static boolean isPossible(int n) {
if(n==0) {
if(isBroken[0]) return false;
}
while(n>0) {
int k = n%10;
if(isBroken[k]) return false;
n = n/10;
}
return true;
}
}
isPossible코드 자체는 나의move코드를 통해 있는 버튼들로 만들 수 있는 숫자인지를 판별하는 코드로서 거의 똑같은 로직이다.
[ 그렇다면 차이점 ]
- Brute Force 하는 부분이 다르다.
나는 목표 숫자로부터 +-1씩 점점 멀어지면서 가능한 숫자인지 아닌지만 판별한 반면,
친구는 0부터 시작해 100만까지 반복하며 매번 min을 계산해 업데이트 한다. - 불필요하게 더 많이 탐색 할 수 있다는 점 (제일 가까운 숫자부터 시작하는 것이 아닌, 항상 0부터 시작)
- 매번 계산한 cost (채널 이동 비용) 으로 기존값과 비교하여 min 을 매번 업데이트 한다는 점이 다르다. 따라서 친구의 코드는 나보다 조금 더 오래 걸렸다.
[ 친구에게서 배운점 ]
isPossible코드에서 숫자String의 charAt()으로 접근하는 방식이 아닌, 대수적으로 /10과 %10을 통해서 자릿수를 접근했다는 점 → 시간적으로 훨씬 효율적- 컴퓨터 정수 최댓값 : 2^32 → 21억 정도 되는데, 1,000,000번 정도면 생각보다 훨씬 작은 숫자이고, O(n) 시간복잡도의 알고리즘으로는 풀 수 있다라는점.
마지막 시도
접근 방식 자체는 내 접근이 훨씬 더 빠르긴 하나, 아무래도 매번 숫자가 누를 수 있는 숫자인지를 확인하기 위해 String 으로 변환 후, charAt 으로 접근한 후, 다시 Int으로 변환해서 확인하는 부분이 지나치게 비효율적이었던 것 같다.
따라서 아래와 같이 로직을 수정해본다.
String의 charAt으로 접근이 아닌, int 의 %10 연산으로 접근해보기.
private static boolean move(int moved){
if (moved == 0) {return !remote[0];}
int target = moved;
while (target > 0){
if (remote[target%10]) {return false;}
target /= 10;
}
return true;
}결과
확인로직만 바꿨을 뿐인데, 시간이 아주 개선되었따.
🫵 안녕하세요, 백엔드 공부하는 초보개발자 홍대의 입니다!