google Job interview Q.1에서 1000사이중에 8은 몇번이 있을까?

구글 인터뷰는 악명높기로 유명하다.

카페에서 우연히 눈에띄는 문제가 있어 생각해보고 간단한 프로그래밍으로 답을 찾아보았다. (사실 이런문제는 인터뷰 문제로 적합하지 않다고 봄)

8, 18, 88, 80.. 888..  오 쉽지않겠는데?

1 – 10 사이에는 1 번 (8)

10- 100 사이에는 : 19번 ( 18, 28.. 98 + 80, 81, 82.. 88, 89 )

100 – 1000 사이에는 : ???

답은 300 번입니다.

방법) integer 숫자를 string 으로 바꿔서 해당 char를 toCharArray로 저장하면서 ‘8’(char)과 같으면 카운팅합니다.

따라서 88이나 888 같은 경우는 카운팅이 2번 혹은 3번됩니다. (이 부분이 질문자의 의도겠죠?)

/**
 * @author comeddy@gmail.com
 * 
 */
public class FindNum {
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// 구글문제중 1에서 1000사이에 8은 몇번 있을까?
		
		// 숫자 8나오면 카운팅할 변수 
		int eight = 0;
		long starttime = System.currentTimeMillis();
		for(int i = 1; i < 1000; i++) 
		{
			
			for(char c: String.valueOf(i).toCharArray()) {
				if(c == '8') {
					eight++;
					System.out.println("count : "+ eight );
				}
			}
			
		}
		long endtime = System.currentTimeMillis();
		long durationtime = endtime - starttime;
		System.out.println("cal duration time : " + durationtime + " millisecond");
	}

}

결과는

(중략)

count : 297

count : 298

count : 299

count : 300

cal duration time : 16 millisecond

만약? 1에서 10000 사이에 8이 몇번이 있을까라고 했다면?

크리스마스 아침에 이런 글이나 남기고 나도 참.. 죄송~ 메리크리스마스 되시구요.

광고

google Job interview Q.1에서 1000사이중에 8은 몇번이 있을까?”에 대한 1개의 생각

  1. 안녕하세요. ^^
    잉여잉여하다 만난 오래된 글에 이렇게 댓글을 남기는 것도 좀 그렇긴한데…

    이 문제는 얼마나 효율적인 방법을 사용하느냐를 보려고 하는 것 같구요,
    그런 측면에서 보면 인터뷰 문제로 적절치 못할 것도 없다고 생각합니다.

    아래와 같이 해결하면 자리수에 대하여 O(n)이 되죠.
    1 부터 1000 사이에서 8을 찾으라고 하면 반복은 세 번입니다.

    // get the appearance of the digit between 1 and the number
    long getAppearance(long number, int digit) {
    int n = 0;
    long count = 0;
    long xh = number;
    long xl = 0;
    int d = digit == 0 ? 10 : digit;

    while(xh >= d) {
    n++;
    int xi = xh % 10;
    xl = number – xh * (long)pow(10.0, (double)(n – 1));
    xh = xh / 10;
    count += (xh + (xi > d ? 1 : 0)) * (long)pow(10.0, (double)(n – 1)) + (xi == d ? xl + 1 : 0);
    }
    return count;
    }

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중