프로그래머를 위한 문제

프로그래머라면 알쏭달쏭한 논리적인 문제를 좋아하는 편인 것 같다. 답이 팍~ 나오는 문제보다 역량에 따라 코드의 아름다움이 달라지는 것을 추구하는 프로그래머라면 더욱 그렇다.

문제: 1부터 1만까지 8은 모두 몇 개가 나오나?

문제는 쉽다. 1부터 1만까지 8이라는 문자 개수만 카운팅하면 된다. 그런데 이렇게 간단한 문제를 코딩해 놓고 보면 맘에 안든다. 더 짧게…. 아래의 문제를 각 언어별로 풀어보았는데, 바이트 수는 캐러지 리턴(carriage return) 문자를 모두 제거한 바이트 수이다.

참고로, 이 문제는 ‘닷넷(.NET) 프로그래머 모임’ 에서 처음 본 문제인데, 오래 전의 일이라 게시글의 링크를 도저히 찾기가 힘들어서 링크를 남기지 못했다.

여러분 중 문제를 풀어보려고 한다면, 바로 아래에 답이 있으니 브라우저를 먼저 종료하길 바란다.

파이썬(python)

파이썬을 배운지 얼마 안되던 때에 이 문제를 만나서 파이썬으로 풀어보았다. 누가 짜도 최종적으로 아래의 코드가 될거다. 처음에는 이렇게 짧게 가능한 파이썬이 맘에 안들었지만, 이제는 맘에 든다. ㅋ;

더 이상은 짧게 안되지 싶다.

# 총 38 바이트   
(str(list(range(1,10001))).count('8'))  

C#

C# 코드로 짜면 아래처럼 된다. 아래의 코드는 확장 메서드와 람다 표현식이 전부다.

혹시나 요걸 비트 연산으로 풀어봤는데, 아래 코드보다 길어지더라. 뭐 내가 짠 코드라 길어질 수도 있겠다.

// 총 84 바이트  
Console.WriteLine(Enumerable.Range(1,10000).Sum(o=>o.ToString().Count(n=>n=='8')));   

Java

Java 8 정식이 나오면 Lambda 지원. 다만 C#의 확장 메서드를 언어상 지원하지 않으므로 Where, Select, Take, Skip 과 같은 확장 메서드는 사용하지 못할 것 같다. 어쨋든 Java 로 이 문제를 짧게 풀수 있는 경쟁력이 없으므로 패스!

C++ Update - 2013-07-04

C++에 대해 조예가 깊지 않아서 내 머리로는 더 짧게 안된다. 이 코드는 위의 파이썬과 C#과는 알고리즘(?)이 좀 틀리다. 어쩔 수 없다. 짧게 하려면…

// 총 146 바이트  
vector<int> v(10000);  
auto n=1,s=0;  
generate(v.begin(),v.end(),[&n, &s](){  
auto m=to_string(n);  
s+=count(m.begin(),m.end(),'8');  
return n++;});  
cout<<s;

아래 댓글에 더 짧은 C++ 코드를 올려주신 HATENA [링크] 님께서 올려주신 코드 입니다. Update - 2013-07-04

// 총 94 바이트
int c=0;
for(int i=1;i<10001;i++){
auto s=to_string(i);
c+=count(s.begin(),s.end();'8');}
cout<<c;

JavaScript - Update 2013-07-03

본 코드는 아래 댓글의 ddd 님께서 작성하신 자바스크립트 코드 입니다.

// 총 94 바이트  
var a=[];
for (var i=1;i<10001;i++)
a[i]=i;
console.info(a.join("").replace(/[^8]/gi,"").length);
저작자 표시 비영리 동일 조건 변경 허락
신고
Posted by 땡초 POWERUMC

댓글을 달아 주세요

  1. 황정현 2013.07.02 09:33 신고 Address Modify/Delete Reply

    예전에 자바스크립트로 한번 풀어봤었네요... 근데 너무 길어요...
    for(var i = 0, len = 10000, count = 0, tmp = ""; i < len; i++){
    var arr = [];
    tmp = (""+i);
    for (var j = 1, len2 = tmp.length; j <= len2; j++)
    {
    arr[j] = tmp.substring((j - 1), j);
    if(arr[j].indexOf("8";) > -1) count++;
    }
    }
    console.log(count);

  2. ddd 2013.07.03 17:53 신고 Address Modify/Delete Reply

    javascript 는 이정도 면 될듯한데
    var a = [];
    for (var i = 1; i < 10001; i++)
    a[i] = i;
    alert(a.join("";).replace(/[^8]/gi, "";).length);

    javascript 는 반복문 안쓸수 없나요 ㄷㄷ

    • 엄준일 2013.07.04 10:28 신고 Address Modify/Delete

      댓글로 적어주신 소스 코드를 제 포스트에 업데이트 했습니다.
      ddd 님 사이트 링크를 남기고 싶었는데,
      링크가 없어서 아쉽네요 ㅠ

  3. HATENA 2013.07.04 11:27 신고 Address Modify/Delete Reply

    항상 블로그 잘 보고 갑니다.
    C++은 vector, generate 안써도 쉽게 풀릴거같은데요 ㅎㅎ.

    int c=0;
    for(int i=1;i<10001;i++){
    auto s=to_string(i);
    c+=count(s.begin(),s.end();'8');}
    cout<<c;

    요거면 100byte 이내로 끝날거같습니다.
    파이선 코드길이 ㅎㄷㄷ하내요 ㄷㄷㄷ

  4. java론 2014.01.07 15:46 신고 Address Modify/Delete Reply

    자바로는 아래처럼....
    int a=0;
    for(int i=0;i<10001;i++) {
    a+=(""+i).replaceAll("[^8]","";).length();
    }

  5. 김인혜 2014.04.06 03:56 신고 Address Modify/Delete Reply

    마이너한 스크립트 언어입니다.
    AutoHotkey

    Loop 10000
    _ .= A_Index
    Msgbox % RegExReplace( _, "8", "", @ ) ? @ :

  6. 지나가다 2015.12.15 15:03 신고 Address Modify/Delete Reply

    만들고 나니 위분거랑 같네요 ㅡㅡ;
    int result = 0;
    for (int i=0; i<=10001; i++) {
    result += String.valueOf(i).replaceAll("[^8]", "";).length();
    }
    return result;

  7. 행인 2016.11.20 15:28 신고 Address Modify/Delete Reply

    Acm 문제에서 간간히 등장하는 유형이네요.
    그 당시 풀때 속도 문제 때문에 reject떠서 수학적으로
    규칙을 찾아서 accept 받았던 기억이 나네요

  8. 재밌네요 2016.11.29 16:02 신고 Address Modify/Delete Reply

    Javascript 좀더 짧게~
    --------------------------------------
    var i,s,r; for (i = 1; i < 10001; i++) s += '' + i; r = s.split('8').length-1;
    console.log(r);