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

비기너

문제

27160번:  할리갈리

# 맵

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

풀이

하나 이상의 과일의 수가 5이면 종을 치고 그렇지 않으면 종을 치지 않는다.

과일에 따라 개수를 카운팅해야 하는 문제이다.

과일의 개수를 세기 위해 맵을 사용한다.

개수를 센 후 맵을 순회하며 과일의 수가 5개라면 종을 친다.

코드

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());
		HashMap<String, Integer> mp = new HashMap<>();
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String s = st.nextToken();
			int x = Integer.parseInt(st.nextToken());
			if (mp.containsKey(s))
				mp.put(s, mp.get(s) + x);
			else
				mp.put(s, x);
		}

		for(int i : mp.values()) {
			if(i == 5) {
				bw.write("YES");
				bw.flush();
				bw.close();
				return;
			}
		}
		
		bw.write("NO");
		bw.flush();
		bw.close();
	}
}

미들러

문제

2805번: 나무 자르기

# 이분탐색

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

풀이

M 미터의 나무를 얻기 위해서 설정할 수 있는 절단기 높이의 최댓값을 구하는 문제이다.

절단기 높이는 0 이상 10억 이하이다.

탐색 범위가 크므로 이분탐색을 이용하여 절단기 높이의 최댓값을 구할 수 있다.

절단기로 자른 나무의 길이의 합을 구하는 과정에서 나올 수 있는 값은 최대 10^15이므로 long을 사용해야 한다.

코드

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));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int[] a = new int[n];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++)
			a[i] = Integer.parseInt(st.nextToken());

		int s = 0, e = 1000000000, ans = 0;
		while (s <= e) {
			int mid = (s + e) / 2;
			long sum = 0;
			for (int i : a)
				sum += Math.max(0, i - mid);
			if (sum >= m) {
				ans = mid;
				s = mid + 1;
			} else
				e = mid - 1;
		}

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

챌린저

문제

2458번: 키 순서

#dfs

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

풀이

자신의 키 순서를 알 수 있는 학생의 수를 출력하는 문제다.

문제에서 키의 대소 관계를 방향 그래프로 모델링했으므로 주어진 관계를 인접 리스트로 저장한다.

어떤 학생 x가 자신의 키 순서를 알 수 있으려면 x에서 탐색을 진행했을 때 도달하는 학생의 수와 다른 학생들에서 탐색을 진행했을 때 x에 도달하는 수의 합이 n이 되면 된다.

모든 학생들에게서 dfs를 진행하면서 도달하는 학생의 cnt 수를 1씩 늘려준다.

dfs로 탐색한 학생의 수만큼(자신도 포함) 자신의 cnt를 늘린다.

cnt 값이 n과 동일한 학생의 수를 출력하면 된다.

코드

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

public class Main {
	static int n, m;
	static boolean[] visited;
	static int[] cnt;
	static ArrayList<ArrayList<Integer>> adj = new ArrayList<>();

	static int dfs(int x) {
		int tmp = 1;
		visited[x] = true;
		for (int nx : adj.get(x)) {
			if (visited[nx])
				continue;
			tmp += dfs(nx);
			cnt[nx]++;
		}
		return tmp;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		for (int i = 0; i <= n; i++)
			adj.add(new ArrayList<>());
		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			adj.get(a).add(b);
		}

		cnt = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			visited = new boolean[n + 1];
			cnt[i] += dfs(i);
		}

		int ans = 0;
		for (int i = 1; i <= n; i++) {
			if (cnt[i] == n)
				ans++;
		}
		bw.write(ans + "");
		bw.flush();
		bw.close();
	}
}