선장 일지

• 생각

끝난 시간이 빠를 수록 다음 시작 시간이 빠르기 때문에 정렬이 필요.

내가 쓴 정렬 방법은 종료시간 정렬 후 종료 시간이 같은 경우에 시작시간에 따라 정렬했다.

• 코드

정답 코드 : 정렬 후 회의실 최대 개수를 구해줌.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static int[][] array;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(ReturnMaxMeetingRoom());
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		N = Integer.parseInt(br.readLine());
		array = new int[N][2];	

		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			array[i][0] = Integer.parseInt(st.nextToken());
			array[i][1] = Integer.parseInt(st.nextToken());
		}
		
        Arrays.sort(array, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                int result = o1[1] - o2[1];
                if (result != 0) return o1[1] - o2[1];	//종료시간에 따라 정렬
                return o1[0] - o2[0];		 //만약 비교하는 값의 종료시간이 같을 경우 시작시간으로 정렬
            }
        });
	}
	
    private static int ReturnMaxMeetingRoom()   {
        int count = 0;    // 최대값 변수 
        int temp = -1;    // 다음시작 시간과 비교할 변수
        for (int i = 0; i < N; i++) {
            //현재 시작시간이 이전 종료시간보다 늦을 경우 
            if (array[i][0] >= temp) {
                temp = array[i][1];
                count++;
            }
        }
        return count;
    }
}

• 생각

ATM의 모든 사람의 대기시간의 합을 구하는 문제이다.

앞에사람의 작업시간이 길어질 수록 총 대기시간이 길어지니 오름차순 정렬을 통해 대기시간을 최소로 해줘야한다.

• 코드

정답 코드 : arrays.sort를 통해 오름차순 정렬을 해준 뒤, 총 대기시간을 구해주었다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static int[] array;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(ReturnWaitingTime());
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		array = new int[N];	
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++)
			array[i] = Integer.parseInt(st.nextToken());
		
		// 오름차순 정렬
		Arrays.sort(array);
	}
	
    private static int ReturnWaitingTime()
    {
    	int sum = 0;
				
		for(int i = 0; i < N; i++) {
			sum += array[i] * (N - i);
		}
    	
        return sum;
    }
}

• 생각

최대공약수를 구해주기만 하면 될듯

• 최대공약수구하는 방법 (재귀)

   private static int GCD(int x, int y)
    {
        if(x % y == 0) return y;
        return GCD(y, x%y);
    }

• 코드

정답 코드 : 단순 수학문제이다. 두 수의 최대공약수를 구해준 뒤 최대공약수로 A, B를 나누어주면 된다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(sb);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		sb = new StringBuilder();		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int A = Integer.parseInt(st.nextToken());
		int B,C;
		for(int i = 0; i < N-1; i++) {
			B = Integer.parseInt(st.nextToken());
			C = GCD(A,B);
			sb.append(A/C + "/"+ B/C + "\n");
		}
	}
	
    private static int GCD(int x, int y)
    {
        if(x % y == 0) return y;
        return GCD(y, x%y);
    }
}

• 생각

-2진법 문제는 그냥 2진법으로 바꾸는 것처럼 풀면 될 것 같다. 단, 나누기와 나머지 연산할 때 -2를 해줘야한다는 것, 또한 나머지 연산할 때는 몫을 버리는 것이 아닌 올림을 해줘야한다.

새로운 방법(클릭하면 링크)

- Math.ceil()

• 코드

정답 코드 : 나머지를 list에 넣어둔 뒤 뒤에서부터 StringBuilder에 append시켜준다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
	static int N;
	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(sb);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		sb = new StringBuilder();
		ArrayList<Integer> list = new ArrayList<>();
        
        if(N==0) { 
            System.out.println(N);
            System.exit(0);
        }
    
        while(N!=0) {
            list.add(Math.abs(N%-2));
            N=(int)Math.ceil((double)N/-2);
        }
        
        for(int i=list.size()-1; i>=0; i--)		// 반복문에서 한번씩 출력해주는 방법보다 빠름
            sb.append(list.get(i));
	}
}

• 생각

해당 숫자가 몇번째의 소수인지 찾으면 되는 문제이다. 소수를 찾는 것은 에라스토테네스의 체를 이용해 찾으면 될 것 같고, 에라스토테네스의 체 내에서 소수가 발견되면 몇번째 소수인지 체크하면서 반복문을 돌면 될 것 같다.

• 코드

정답 코드 : 에라스토테네스의 체를 이용해서 구해주는데, 위의 K 범위만큼 배열을 만들어서 사용하면 100점이 뜨지않는다. 이유는 500000를 입력하면 500000번째 소수를 구하는 것이기 때문에 범위를 더 크게 주어야한다. 점점 늘리면서 채점해봤는데 10000001정도에 100점이 뜬다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static int K;
	static int[] prime;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(prime[K - 1]);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		K = Integer.parseInt(br.readLine());
		prime = new int[10000001];
		boolean[] check = new boolean[10000001];
		int index = 0;

		// 에라스토테네스의 체
		for (int i = 2; i <= 10000000; ++i) {
			if (!check[i]) {
				prime[index++] = i;
				for (int j = i + i; j <= 10000000; j += i) {
					check[j] = true;
				}
			}
		}
	}
}

• 생각

캠핑장을 연속하는 P일 중, L일동안만 사용할 수 있다. 강산이는 이제 막 V일짜리 휴가를 시작했다.

L일 동안 캠핑하고, P-L일 동안 안하고, 이 두 가지 상태가 반복 됌.

• 코드

정답 코드 : V/P (연속일), 연속일 * 연속 최대사용일수(L) => 사용가능 일 수 + 나머지일 수 더해줌. 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int L, P, V, count;
	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(sb);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		sb = new StringBuilder();
		count = 1;

		while (true) {
			st = new StringTokenizer(br.readLine());
			L = Integer.parseInt(st.nextToken());
			P = Integer.parseInt(st.nextToken());
			V = Integer.parseInt(st.nextToken());
			
			if (L == 0)			break;
			// V/P = 연속
			sb.append("Case " + count + ": " + ((V / P) * L + Math.min(L, V % P)) + "\n");
			count++;
		}
	}
}

• 생각

단순 수학문제 배열을 만들어서 해당하는 숫자 1을 1번 2를 2번 ..... 1000번까지 한 뒤, A부터 B까지 더한 값을 출력

• 코드

정답 코드 : 배열을 만들어 A~B 인덱스까지 더해준 숫자를 출력하였다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int A, B, answer;
	static int[] array;

	public static void main(String[] args) throws Exception {
		SetData();
		getSum();
		System.out.println(answer);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		A = Integer.parseInt(st.nextToken());
		B = Integer.parseInt(st.nextToken());
		answer = 0;
		
		int index = 0;
		array = new int[1001];
		for(int i = 1; i < 1001; i++) {
			for(int j = 0; j < i; j++) {
				array[index++] = i;
				if(index > 1000) break;
			}
			if(index > 1000) break;
		}
	}
	
    public static void getSum() {
		for (int i = A - 1; i <= B - 1; i++) {
			answer += array[i];
		}
    }
}

• 생각 

1. stick의 초기 길이(64)에서 반씩 나누어주면서, 길이 X보다 더 작은 값이 나오면
   X 값을 해당 숫자만큼 차감시키고, 차감 횟수를 센다.
2. X 값이 0이 나올때까지 진행한 뒤, 차감 횟수를 출력한다.

• 코드

정답 코드 : 위의 방법대로 짠 코드이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static int X, stick, answer;

	public static void main(String[] args) throws Exception {
		SetData();
		getStick();
		System.out.println(answer);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
        X = Integer.parseInt(br.readLine());
        stick = 64;
        answer = 0;
	}
	
    public static void getStick() {
		while (stick > 0) {
			if (stick <= X) {
				X -= stick;
				answer++;
			}
			if (X == 0) {
				break;
			}
			stick /= 2;
		}
    }
}