99클럽 코테 스터디 24일차 TIL

비기너

문제

1417번: 국회의원 선거

# 우선순위 큐

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

풀이

n명의 후보를 찍으려는 사람의 수가 주어졌을 때 1번 후보가 당선되려면 매수해야 하는 사람의 수의 최솟값을 구하는 문제이다.

효율적으로 사람을 매수하려면 가장 찍으려는 사람이 많은 후보에게서 1명씩 매수하면 된다.

따라서 우선순위 큐를 이용해서 맥스힙을 구현하고 찍으려는 사람이 가장 많은 후보의 사람을 1명씩 매수하면 된다.

다른 후보를 찍으려는 사람의 최댓값이 1번 후보를 찍으려는 사람보다 적을 때까지 반복한다.

코드

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
		int x = Integer.parseInt(br.readLine());
		for (int i = 1; i < n; i++)
			pq.add(Integer.parseInt(br.readLine()));

		int ans = 0;
		while (!pq.isEmpty() && pq.peek() >= x) {
			x++;
			pq.add(pq.poll() - 1);
			ans++;
		}

		bw.write(ans + "");
		bw.flush();
		bw.close();
	}
}

미들러

문제

전력망을 둘로 나누기

# 완전탐색 # dfs

https://school.programmers.co.kr/learn/courses/30/lessons/86971

프로그래머스

풀이

n개의 송전탑이 전선을 통해 트리 형태로 연결되어 있을 때 전선 하나를 끊어서 전력망 네트워크를 2개로 분할할 때 두 전력망의 송전탑 개수의 차이의 최솟값을 구하는 문제이다.

전선이 최대 99개이므로 각 전선을 끊었을 때 두 전력망의 송전탑 개수 차이를 모두 구하고 비교해주면 된다.

두 전력망의 송전탑 개수는 dfs를 통해 구한다.

코드

import java.util.*;

class Solution {
    boolean[] visited;
    ArrayList<ArrayList<Integer>> adj;
    
    int dfs(int x) {
        visited[x] = true;
        int cnt = 1;
        for (int nx : adj.get(x)) {
            if (visited[nx])
                continue;
            cnt += dfs(nx);
        }
        return cnt;
    }
    
    public int solution(int n, int[][] wires) {
        int ans = 1000000000;
        
        for (int i = 0; i < n - 1; i++) {
            adj = new ArrayList<>();
            for (int j = 0; j <= n; j++) 
                adj.add(new ArrayList<>());
            for (int j = 0; j < n - 1; j++) {
                if (i == j)
                    continue;
                adj.get(wires[j][0]).add(wires[j][1]);
                adj.get(wires[j][1]).add(wires[j][0]);
            }
            
            visited = new boolean[n + 1];
            int tmp = 0;
            for (int j = 1; j <= n; j++) {
                if (!visited[j]) {
                    if(tmp == 0)
                        tmp = dfs(j);
                    else
                        tmp = Math.abs(tmp - dfs(j));
                }
            }
            ans = Math.min(ans, tmp);
        }
        
        return ans;
    }
}

챌린저

문제

2437번: 저울

# 그리디

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

풀이

n개의 추가 주어졌을 때 이 추들로 측정할 수 없는 무게 중 최솟값을 구하는 문제이다.

추를 사용해서 측정하는 무게를 작은 것부터 구하기 위해 추의 무게를 오름차순으로 정렬한다.

추 n개 중에 k개로 표현할 수 있는 무게가 1 ~ m이라고 하자.

이때 다음 추의 무게가 x라면 x를 추가해서 표현할 수 있는 무게는 1 ~ m과 x ~ m + x이다.

따라서 x가 m + 1보다 크다면 m + 1은 표현하지 못한다.

정렬된 추의 무게 배열을 순회하면서 해당 추들로 표현할 수 있는 최대 무게 + 1보다 다음 추의 무게가 더 크다면 최대 무게 + 1이 표현하지 못하는 무게이다.

코드

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		int[] a = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++)
			a[i] = Integer.parseInt(st.nextToken());
		Arrays.sort(a);

		int ans = 0;
		for (int i = 0; i < n; i++) {
			if (ans + 1 < a[i])
				break;
			else
				ans += a[i];
		}

		bw.write((ans + 1) + "");
		bw.flush();
		bw.close();
	}
}