방 번호 문제

import java.util.*;

class Main {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int num = sc.nextInt();
		int n = 0;
		int[] numSet = new int[11];
		Arrays.fill(numSet, 1);
        
	/* 목표 숫자의 범위를 지정 */
		if(num == 1000000) n = 1000000;
		else if(num >= 100000) n = 100000;
		else if(num >= 10000) n = 10000;
		else if(num >= 1000) n = 1000;
		else if(num >= 100) n = 100;
		else if(num >= 10) n = 10;
		else n=1;
		
		for(int i = 1; i <= n; i*=10) {
			pickSet(numSet, num, i);
		}
		System.out.println(numSet[10]);  // 보충한 횟수를 출력
	}
	
    /* 숫자카드 1세트를 추가한다 */
	public static void addNewSet(int[] arr) {
		for(int i = 0; i < arr.length-1; i++) {
			arr[i]++;
		}
		arr[arr.length-1]++;
	}
	/* 원하는 숫자를 만들기 위해서 가지고 있는 숫자카드 중에서 한 장을 고른다*/
	public static void pickSet(int[] arr, int num, int N) {
		int next = num/N%10, rep=0;
			
		if(next == 6) rep = 9;
		else if(next == 9) rep = 6;
		
		if(arr[next] < 1) {
			if((next == 6 || next == 9 ) && (arr[rep] > 0)) arr[rep]--; //대체카드로 성공
			else { //실패
				addNewSet(arr);
				pickSet(arr, num, N);
			}
		}
		else arr[next]--; //성공
	}
}

 

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

1. 개요

10장의 숫자카드를 가지고 목표 숫자를 완성하는 문제입니다.

저는 숫자카드 중 특별한 규칙을 만족하면서 한 장을 선택하는 메서드와

숫자카드가 떨어졌을때 보충하는 메서드를 이용해 문제를 해결하였습니다.

2. 고난과 역경

처음에는 numSet 에 지금처럼 카드의 장수를 저장하지 않고

0~9를 그냥 때려박았습니다. 카드가 사용되면 -1을 대입하고, 카드가 부족할 때는 배열을 초기상태로 되돌리면서 그 횟수를 저장하는 방식이었습니다.

그래서  '111666' 과 같이 입력이 주어진 경우, (정답은 3)

새로운 카드 3세트를 추가(1116) 하고 이전의 2세트는 버리고 새로 2세트(66)를 더 추가하기 때문에 5가 출력되었습니다. 

이걸 해결하고자 pickSet 이 spare 배열을 생성한 뒤 남은 카드를 담아서 반환하고 그럼 다시 spare에 대해서 pickSet을 수행하는 쓸데없이 복잡한 코드를 마구 써갈기다가 spare 배열을 어떻게 관리해야 할 것인가? 연결리스트를 써볼까 하는 고민을 계속 하다가 포기하고 양치를 하던 도중

유레카!

그냥 카드 장수를 저장하면 되는 것이었구나 하는 깨달음을 얻었습니다. 어느 한 카드가 떨어지면 그냥 전체 카드를 한 장씩 추가해주면 되는 일이었습니다.

단순하게 생각하면 될 것을 왜 자꾸 복잡한 길로 가게 되는 걸까요?

3. 대안

카드를 뽑고 채워넣고 할 필요없이

역으로 목표 숫자를 분석해서 각 숫자카드가 몇 장씩 필요한 지를 카운트합니다.

가장 많이 필요한 카드가 곧 필요한 세트의 수가 되겠지요.

대체가능한 관계에 있는 6, 9의 경우는 더한 다음 2로 나누어 줍니다.

4. 반성

위 문제와 같이 입력받은 숫자를 분해해야 하는데, 그 범위가 클 때는 문자열의 toCharArray() 메서드를 이용하는 게 좋을 듯 합니다.

ascii 코드표상에서 '0'의 ascii 값은 48입니다. 입력문자열에서 변환된 char에다가 48을 빼주면 0이라는 ascii 값을 얻을 수 있습니다.

문제를 보면 가장 먼저 떠오르는 직관적이고 무식한 방법으로 차근차근 풀어보려는 경향이 있습니다.

대부분 코딩테스트는 시간제한이 있으므로 이렇게 코드가 길어지고 시간이 오래걸리는 방법이 맞는 것인가 고민하게 됩니다.

조금만 문제를 잘 해석한다면 위와 같이 간단한 해결방법이 도출될텐데... 그게 어렵네요.