문제 해석

코드잼 로또 당첨자에게 수표를 발행해줘야 하는데 수표 프린터기의 키보드중에 숫자 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 >>

'Dev' 카테고리의 다른 글

[google codejam 2019 QR] P2 You Can Go Your Own Way  (0) 2019.04.11
[google codejam 2019 QR] P1 Foregone Solution  (0) 2019.04.11
PingBot Architecture  (0) 2014.05.04
[ Mybatis ] DB 설정 정보 분리  (0) 2014.05.03
Posted by yeori

댓글을 달아 주세요

나의이름 패스워드

홈페이지 비밀글