[코딩인터뷰완전분석] 20일차. 수학 및 논리 퍼즐

아리스토테네스의 체

public class SieveOfEratosthenes {
	
	public static void crossOff(boolean[] flags, int prime) {	
		for (int i = prime * prime; i < flags.length; i += prime) {
			flags[i] = false;
		}
	}
	
	public static int getNextPrime(boolean[] flags, int prime) {
		int next = prime + 1;
		while (next < flags.length && !flags[next]) {
			next++;
		}
		return next;	
	}
	
	public static void init(boolean[] flags) {
		flags[0] = false;
		flags[1] = false;
		for (int i = 2; i < flags.length; i++) {
			flags[i] = true;
		}
	}
	
	public static int[] prune(boolean[] flags, int count) {
		int[] primes = new int[count];
		int index = 0;
		for (int i = 0; i < flags.length; i++) {
			if (flags[i]) {
				primes[index] = i;
				index++;
			}
		}
		return primes;
	}
	
	public static boolean[] sieveOfEratosthenes(int max) {
        boolean[] flags = new boolean[max + 1];
        
		init(flags);
        int prime = 2;
        
        while (prime <= Math.sqrt(max)) {       	
    		prime = getNextPrime(flags, prime);
        }
        
        return flags; //prune(flags, count);
	}
	
	public static void main(String[] args) {
		boolean[] primes = sieveOfEratosthenes(4);
		for (int i = 0; i < primes.length; i++) {
			if (primes[i]) {
				System.out.println(i);
			}
		}
	}

}

 

면접 문제 

6.1 무거운 알약

약병 20개가 있다. 이 중 19개에는 1.0그램짜리 알약들이 들어있고, 하나에는 1.1그램짜리 알약들이 들어 있다. 정확한 저울 하나가 주어졌을 때, 무거운 약병을 찾으려면 어떻게 해야할까? 저울은 딱 한번만 쓸 수 있다. 

public class FindHeavyBottle {
    public static void main(String[] args) {
        int[] bottles = new int[20];
        // 19개 약병에는 1.0그램짜리 알약이 들어있음
        for (int i = 0; i < 19; i++) {
            bottles[i] = 1000; // 1.0그램을 밀리그램으로 표현
        }
        // 1개 약병에는 1.1그램짜리 알약이 들어있음
        bottles[19] = 1100; // 1.1그램을 밀리그램으로 표현

        int totalWeight = 0;
        for (int weight : bottles) {
            totalWeight += weight;
        }

        int expectedTotalWeight = (19 * 1000) + 1100; // 기대되는 전체 무게 (19개 * 1.0그램 + 1개 * 1.1그램)

        // 실제 전체 무게와 기대되는 전체 무게를 비교하여 차이를 계산
        int difference = totalWeight - expectedTotalWeight;

        // 차이가 있으면 그 차이가 있는 약병이 무거운 약병
        if (difference > 0) {
            System.out.println("무거운 약병은 " + difference + "밀리그램 무겁습니다.");
        } else {
            System.out.println("모든 약병은 1.0그램짜리 알약입니다.");
        }
    }
}

 

6.2 농구 

농구 골대가 하나 있는데 다음 두 게임 중 하나를 해 볼 수 있다. 
게임1 : 슛을 한 번 쏴서 골대에 넣어야한다.

게임2 : 슛을 세 번 쏴서 두 번 골대에 넣어야한다. 

슛을 넣을 확률이 p라고 했을 때 p가 어떤 값일 때 첫 번째 게임을 혹은 두번째 게임을 선택하겠는가

public class BasketballGame {
    public static void main(String[] args) {
        double p = 0.5; // 슛을 넣을 확률 (0 <= p <= 1)

        // 게임 1에서 승리하는 확률
        double game1WinProbability = p;

        // 게임 2에서 승리하는 확률
        double game2WinProbability = 1 - Math.pow(1 - p, 3);

        if (game1WinProbability > game2WinProbability) {
            System.out.println("게임 1을 선택합니다.");
        } else if (game1WinProbability < game2WinProbability) {
            System.out.println("게임 2를 선택합니다.");
        } else {
            System.out.println("두 게임의 확률이 같으므로 어느 게임을 선택해도 상관 없습니다.");
        }
    }
}