[코딩 도장] 1에서 10000까지 숫자 8 갯수 세어보기

코딩 도장(http://codingdojang.com/) 사이트에서 구글 입사 문제 중 하나로 아래와 같은 문제가 있어 풀어보았다.

1부터 10000까지 8이라는 숫자는 총 몇 번 나오는가? 8이 포함되어 있는 숫자의 갯수를 카운팅 하는 것이 아니라 8이라는 숫자를 모두 카운팅 해야 한다. (예를 들어 8808은 3, 8888은 4로 카운팅 해야 한다.)

문제에 나오는 숫자 정보를 상수가 아닌 변수로 가정했다.

• 시작 숫자: 1(from)
• 끝 숫자: 10000(to)
• 찾고자 하는 숫자: 8(findingNum)

일단 모든 수에 대해서 찾고자 하는 숫자(이하 findingNum)가 몇 개 있는지 카운팅 해 보는 방법으로 접근해 보았다.

• from ~ to 까지 모든 수를 반복하여 체크한다.
1. 체크 대상 숫자를 10으로 나누어 나머지가 findingNum과 같다면 count + 1을 한다.
2. 체크 대상 숫자를 10으로 나눈 몫이 0이 아니라면 체크 대상 숫자/10을 체크 대상 숫자로 설정하고 1번을 다시 수행한다.
3. 만약 몫이 0이라면 체크를 종료한다.
• from ~ to 까지 체크한 count 값을 합산한다.

Java로 구현한 코드는 아래와 같다.

public class NCounter {     private final int findingNum;     public NCounter(int findingNum) {         this.findingNum = findingNum;     }     public int countN(int from, int to) {         if (from > to) {             return 0;         }         int count = 0;         for (int i = from; i <= to; i++) {             count += getCountN(i);         }         return count;     }     /**      * TODO num에 대한 결과값 캐싱(성능향상)      * @param num 대상 숫자      * @return 찾고자 하는 숫자 갯수      */     private int getCountN(int num) {         int count = 0;         do {             if (num % 10 == this.getFindingNum()) {  //마지막 자리가 8인지 체크                 count++;             }             num /= 10;         } while (num > 0);         return count;     }     public int getFindingNum() {         return findingNum;     } }

@RunWith(Parameterized.class) public class NCounterTest {     @Parameterized.Parameters     public static Collection<Object[]> parameters() {         return Arrays.asList(new Object[][]{                 {1, 10, 8, 1},                 {1, 100, 8, 20},                 {1, 1000, 8, 300},                 {1, 10000, 8, 4000}         });     }     private int from;     private int to;     private int findNum;     private int expectedCount;     public NCounterTest(int from, int to, int findNum, int expectedCount) {         this.from = from;         this.to = to;         this.findNum = findNum;         this.expectedCount = expectedCount;     }     @Test     public void 숫자_세기() {         NCounter counter = new NCounter(this.findNum);         assertEquals(this.expectedCount, counter.countN(from, to));     } }

* 구현 코드 주석에도 언급을 하였지만 메모리 공간을 좀 더 사용하더라도 체크 성능을 높이고자 한다면 countN(num) 함수의 결과를 캐싱하여 do ~ while문의 반복을 줄일 수 있는 방법도 있을 것 같다.

문제를 좀 더 쉽게 생각하면 다른 방법도 있을 것 같다.

만약 1 ~ 10000처럼 to의 값이 10, 100, 1000, 10000 등의 10의 배수라면 아래와 같이 생각해 볼 수 있다.

1~10

8 한 가지 뿐이다.

1~100

1의 자리가 8인 경우는 10가지(8, 18, 28, 38, 48, 58, 68, 78, 88, 98)가 있다.

10의 자리가 8인 경우는 10가지(80, 81, 82, 83, 84, 85, 86, 87, 88, 89)가 있다.

1~1000

1의 자리가 8인 경우는 100가지가 있다.

008 ~ 998까지가 될 수 있는데, 1의 자리를 8로 고정하고 10, 100의 자리에 위치할 수 있는 숫자의 종류는 각각 0~9까지 10 * 10이 될 수 있다.

10의 자리가 8인 경우도 1의 자리와 유사하다.

080 ~ 980까지 될 수 있는데, 이 또한 10의 자리를 8로 고정하고 1, 100의 자리에 위치할 수 있는 숫자의 종류는 각각 0~9까지 10 * 10이 될 수 있다.

이제 1~10000을 생각해보자.

10000까지라 해도 10000은 8이 없으므로 제외하고 4자리 수(9999)까지만 생각하면 된다.

1, 10, 100, 1000의 자리에 8이 올 수 있는 갯수는 그 자리에 8을 고정하고 나머지 숫자가 0~9까지 10 * 10 * 10으로 각각 1000가지이다.

따라서 4000가지가 될 수 있다.

이를 수식으로 작성하면 아래와 같이 될 것이다.

to - 1의 자릿수를 N이라고 할 때, 경우의 수 = N * 10 ^ (N - 1)

이 처럼 to가 10의 배수라는 가정하에 문제를 풀어보면 위에서 도출한 수식으로 쉽게 해결 할 수 있다.

/** * 1 ~ to까지 findingNum의 갯수를 카운팅 할 때, to 변수가 10의 배수라고 가정하면... * * @param to 10의 배수 * @return findingNum 갯수 */ public int countN(int to) {     int posNum = 0;     while (to > 0) {    //to 자릿 수 계산         if (to % 10 == 0) {             posNum++;         }         to /= 10;     }     return posNum * (int)Math.pow(10, posNum - 1); }

@Test public void 숫자_세기_10의_배수인_경우() {     NCounter counter = new NCounter(this.findNum);     assertEquals(this.expectedCount, counter.countN(to)); }

또 다른 방법

https://github.com/KimMinJoo/AlgorithmStudy/tree/master/src/google

위 링크는 알고리즘 스터디에 참여하는 다른 분의 해결책이다. 이 방법이 제일 정답에 근접한 것이 아닌가 생각된다.

전체 수를 다 체크해야 하는 로직은 O(n)의 시각복잡도를 가지나 위 방법은 O(logn)의 시간 복잡도를 가진다.

각 수에서 8을 체크하는 것이 아니라 각 자리마다 8이 나올 수 있는 수를 계산하는 방식이다.

핵심은 아래와 같다.

예를 들어 0~896이라는 범위가 주어지고 8을 찾아야 할때    최소 등장 보장  추가 등장 계산  일의 자리 계산  (896 / 10) * 1 = 89  일의 자리가 6이므로 등장 0  십의 자리 계산  (896 / 100) * 10 = 80  십의자리가 9 이므로 80번대가 지남. 즉 10번이 더 등장. 10  백의 자리 계산  (800 / 1000) * 100 = 0  백의 자리가 8이므로 8이 등장. 근데 뒤의 숫자가 96, 즉 800~896까지 97번 더 등장. (공식.2) 위의 계산을 보면 총 89 + 90 + 97 = 276번이 등장하게 됩니다.

1~10000 처럼 10의 지수승까지 라면 추가 계산이 필요하지 않다. 하지만 10의 지수승이 아닌 숫자까지 처리하고자 추가 등장 계산을 수행하는 것이다.

이 알고리즘을 적용하여 나도 구현해 보았다.(코드는 아래 github 링크에 countNV2()에서 확인할 수 있다.) 

코드는 아래 github에서 확인할 수 있습니다.

https://github.com/tomining/AlgorithmStudy/blob/master/src/main/java/com/algorithm/coding/dojang/NCounter.java

https://github.com/tomining/AlgorithmStudy/blob/master/src/test/java/com/algorithm/coding/dojang/NCounterTest.java

---

참고

• http://codingdojang.com/scode/393?answer_mode=hide