문제 해석
코드잼 로또 당첨자에게 수표를 발행해줘야 하는데 수표 프린터기의 키보드중에 숫자 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 들을 제거해준 후 출력함
'Dev' 카테고리의 다른 글
[google codejam 2019 QR] P2 You Can Go Your Own Way (0) | 2019.04.11 |
---|---|
PingBot Architecture (0) | 2014.05.04 |
[ Mybatis ] DB 설정 정보 분리 (0) | 2014.05.03 |