[google codejam 2019 QR] P1 Foregone Solution

문제 해석

코드잼 로또 당첨자에게 수표를 발행해줘야 하는데 수표 프린터기의 키보드중에 숫자 4가 고장났음.

예를 들어서 당첨금 40,000,000 원을 수표에 출력해야하는데 불가능한 상황

그래서 당첨금을 숫자 4가 포함되지 않은 금액으로 나눠서 두 장의 수표를 출력하고 싶음

 

입력으로 주어지는 당첨금에는 최소 한 개 이상의 숫자 4가 항상 포함되어있음

 

당첨금을 숫자 4가 포함되지 않는 두 개의 금액으로 나눠서 출력하는 문제

 

어떻게 나누든 숫자 4만 없으면 됨

 

입력

Test set1과 Test set 2는 최대 10^9이기때문에 상관없지만 Test set 3의 경우 10^100 (101자리숫자) 이므로 primitive type(long 등) 으로 숫자를 읽어들이면 문제를 풀 수 없음

 

문제의 특성상 당첨금을 문자열로 읽어들여도 해결 가능함

 

풀이

간단한 구현은

 

1) 주어진 숫자를 둘로 나눠 저장할 버퍼를 준바함 ( va = [], vb = [])

2) 문자열로 읽어들인 숫자의 각 위치에 대해서 ( n := "39384928282")

3) 각 위치의 문자('0'~'9')를 숫자로 변환해서 ( n[i] - '0' ) 반으로 나눈 후

4) 양쪽 버퍼에 저장해줌 va += half[0], vb += half[1]

 

여기서 반으로 나눌때 4가 나오는 경우는 아래의 세가지가 존재함

 

7 => [3, 4]

8 => [4, 4]

9 => [4, 5]

 

위의 두가지 경우에 대해서는 아래와 같이 4를 회피하도록 보정해줌

 

7 => [3-1, 4+1] => [2, 5]

8 => [4-1, 4+1] => [3, 5]

9 => [4-1, 5+1] => [3, 6]

 

* 쪼갠 두 숫자중에 4가 등장하면 왼쪽값을 1 줄이고 오른쪽값을 1 늘려줌

 

그리고 va, vb로 쪼개서 숫자(처럼 생긴 문자)들을 담을때 맨 앞자리에 0이 쌓일 수 있음.

 

N := "116744" := ["003222", "113522"]

 

va, vb에 대해서 맨 앞의 0 들을 제거해준 후 출력함

 

show >>

public class Solution { static String[] divide(String N) { StringBuilder a = new StringBuilder(); StringBuilder b = new StringBuilder(); int len = N.length(); for(int i = 0 ; i < len ; i ++) { char c = N.charAt(i); int v = c - '0'; int va = v/2; int vb = v - va; if ( va == 4 || vb == 4) { va --; vb ++; } a.append(va); b.append(vb); } while ( a.length()>0 && a.charAt(0) == '0') { a.delete(0, 1); } while ( b.length() > 0 && b.charAt(0) == '0') { b.delete(0, 1); } return new String[] {a.toString(), b.toString()}; } }