[백준] java 알고리즘 스터디 1주차 - 정렬

1931 회의실 배정

📌문제 링크

https://www.acmicpc.net/problem/1931

💡 문제 풀이

끝나는 시간을 기준으로 오름차순, 끝나는 시간이 같을 경우 시작하는 시간을 기준으로 오름차순으로 정렬한다.
정렬한 순서대로 시작하는 시간이 바로 전에 시작한 회의의 끝나는 시간과 겹치지 않는 회의의 개수를 센다.
시작하는 시간에 대해 정렬하지 않을 경우 (2,3) (2,2)의 회의가 있을 때 둘 다 사용할 수 있음에도 count되지 않을 수 있다!

📋코드

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk;
		int N = Integer.parseInt(br.readLine());
		int[][] arr = new int[N][2];
		
		for (int i = 0; i < N; i++) {
			stk = new StringTokenizer(br.readLine());
			arr[i][0] = Integer.parseInt(stk.nextToken()); 
			arr[i][1] = Integer.parseInt(stk.nextToken());
		}
		
        // 정렬
		Arrays.sort(arr, (a1, a2) -> { 
        		// 종료 시간이 같다면 시작시간 오름차순 정렬
				if (a1[1] == a2[1]) return a1[0] - a2[0];
                // 종료 시간 오름차순 정렬
				else return a1[1] - a2[1]; 
			});
	
    	// 가장 최근 선택한 가능한 회의
		int last = arr[0][1];
		int cnt = 1;
		
		for (int i = 1; i < N; i++) {
			if (arr[i][0] < last) continue;
			else {
				cnt++;
				last = arr[i][1];
			}
		}
		
		System.out.println(cnt);
	}

}

⏱ 시간 복잡도

입력 : O(N)
정렬 : O(NlogN) (퀵 정렬)
가능한 회의 개수 계산 : O(N)
-> 시간복잡도 : O(NlogN)

2108 통계학

📌문제 링크

https://www.acmicpc.net/problem/2108

💡 문제 풀이

• 평균값 : 전체 수를 더하고 N으로 나눔
• 중앙값 : 정렬한 배열의 N/2번째 인덱스 값 (N이 홀수이므로 N/2자리가 중앙값)
• 최빈값 : 숫자의 빈도를 세는 cnt배열을 만들어 확인함 (숫자의 범위만큼 배열의 크기를 설정하고, 인덱스에 해당하는 숫자가 얼마나 등장했는지 count)
• 범위 : 정렬한 배열의 처음 값과 끝 값의 차이

📋코드

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		int[] cnt = new int[8001]; // 숫자 빈도 cnt 배열. 수의 범위 : -4000~4000
		
		int avg = 0, mode_max = 0;
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
			avg += arr[i]; // 평균값 계산을 위한 누적합
			cnt[arr[i]+4000]++; // 숫자 빈도 +1
			
            // 최빈값 갱신
			if (mode_max < cnt[arr[i]+4000]) {
				mode_max = cnt[arr[i]+4000];
			}
			
		}
		
        // 숫자 개수가 1일 경우
		if(N == 1) {
			for (int i = 0; i < 3; i++) {
				System.out.println(arr[0]);
			}
			System.out.println(0);
			return;
		}
		
        // 평균값
		System.out.printf("%d\n", Math.round((double) avg / N));
        
        // 중앙값
		Arrays.sort(arr);
		System.out.println(arr[N/2]);
		
        // 최빈값
		ArrayList<Integer> modelist = new ArrayList<>();
		for (int i = 0; i < 8001; i++) {
			if (cnt[i] == mode_max) modelist.add(i-4000);
		}
		
		if (modelist.size() > 1) System.out.println(modelist.get(1));
		else System.out.println(modelist.get(0));
		
        // 범위
		System.out.println(arr[N-1] - arr[0]);

	}

}

⏱ 시간 복잡도

입력 : O(N)
정렬 : O(NlogN)
최빈값 구하기 : O(1)
-> 시간복잡도 : O(NlogN)

18870 좌표 압축

📌문제 링크

https://www.acmicpc.net/problem/18870

💡 문제 풀이

📋코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk;
		HashMap<Integer, Integer> hm = new HashMap<>();
		
		int N = Integer.parseInt(br.readLine());
		stk = new StringTokenizer(br.readLine());
		
		int[] arr = new int[N]; // 입력받을 숫자 원본 배열
		int[] sorted = new int[N]; // 입력받을 숫자를 정렬할 배열
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(stk.nextToken());
			sorted[i] = arr[i];
		}
		
        // 정렬
		Arrays.sort(sorted);
		
		int rank = 0;
		for (int num : sorted) {
			if(!hm.containsKey(num)) {
				hm.put(num, rank);
				rank++;
			}
		}
		
		StringBuilder sb = new StringBuilder();
		for (int num : arr) {
			sb.append(hm.get(num)).append(" ");
		}
		
		System.out.println(sb);
		
	}

}

⏱ 시간 복잡도

입력 : O(N)
정렬 : O(NlogN)
좌표 압축 : O(N)
출력 : O(N)
-> 시간 복잡도 : O(NlogN)

1946 신입 사원

📌문제 링크

https://www.acmicpc.net/problem/1946

💡 문제 풀이

📋코드

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk;
		
		int T = Integer.parseInt(br.readLine());
		
		for (int test_case = 0; test_case < T; test_case++) {
			int N = Integer.parseInt(br.readLine());
			
			int[][] arr = new int[N][2];
			
			for (int i = 0; i < N; i++) {
				stk = new StringTokenizer(br.readLine());
				arr[i][0] = Integer.parseInt(stk.nextToken());
				arr[i][1] = Integer.parseInt(stk.nextToken());
			}
			
			Arrays.sort(arr, new Comparator<int[]>() {

				@Override
				public int compare(int[] o1, int[] o2) {
					return o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0];
				}
			});
			
			int max = arr[0][1], cnt = 0;
			for (int[] is : arr) {
				if (is[1] <= max) {
					cnt++;
					max = is[1];
				}
			}
			
			System.out.println(cnt);
		}

	}

}

⏱ 시간 복잡도

입력 : O(N)
정렬 : O(NlogN)
선발할 사원 count : O(N)
-> 시간 복잡도 : O(NlogN)

2470 두 용액

📌문제 링크

https://www.acmicpc.net/problem/2470

💡 문제 풀이

📋코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk;
		
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		
		stk = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(stk.nextToken());
		}
		
		Arrays.sort(arr);
		
		int left = 0;
		int right = N-1;
		int min = Integer.MAX_VALUE;
		int min_left = -1, min_right = -1;
		
		while (left < right) {
			int sum = arr[left] + arr[right];
			if (Math.abs(sum) < min) {
				min = Math.abs(sum);
				min_left = left;
				min_right = right;
			}
			
			if (sum == 0) break;
			else if (sum < 0) left++;
			else right--;
		}
		
		System.out.printf("%d %d\n", arr[min_left], arr[min_right]);

	}

}

⏱ 시간 복잡도

입력 : O(N)
정렬 : O(NlogN)
탐색 : O(N) (투포인터)
-> 시간 복잡도 : O(NlogN)