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

비기너

문제

폰캣몬

# 해시

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

프로그래머스

풀이

n 마리의 포켓몬 중에 n / 2 마리를 선택할 때 포켓몬 종류의 최대값을 구하는 문제이다.

set에 포켓몬을 저장하면 포켓몬 종류의 수를 알 수 있다.

포켓몬 종류의 수보다 n / 2가 더 작으면 최대 n / 2 가지의 포켓몬을 선택할 수 있고 그렇지 않으면 포켓몬의 종류만큼의 포켓몬을 선택할 수 있다. 

코드

import java.util.*;

class Solution {
    public int solution(int[] nums) {
        int ans = nums.length / 2;
        
        HashSet<Integer> s = new HashSet<>();
        for (int i : nums)
            s.add(i);
        
        ans = Math.min(ans, s.size());
        return ans;
    }
}

미들러

문제

18352번: 특정 거리의 도시 찾기

# bfs

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

풀이

가중치가 없는 그래프에서 최단거리를 구하는 문제이므로 bfs를 이용한다.

x에서 bfs를 돌리면 x로부터 각 지점의 최단거리가 구해진다.

그중에서 최단거리가 k인 도시를 출력하면 된다.

참고

https://ward.tistory.com/193

그래프 탐색

코드

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

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

	static void bfs(int x) {
		Queue<Integer> q = new LinkedList<>();
		q.add(x);
		visited[x] = 1;
		while (!q.isEmpty()) {
			x = q.poll();
			for (int nx : adj.get(x)) {
				if (visited[nx] >= 1)
					continue;
				q.add(nx);
				visited[nx] = visited[x] + 1;
			}
		}
	}

	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());
		int m = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int x = 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);
		}

		visited = new int[n + 1];
		bfs(x);

		boolean flag = true;
		for (int i = 1; i <= n; i++) {
			if (visited[i] == k + 1) {
				bw.write(i + "\n");
				flag = false;
			}
		}
		if (flag)
			bw.write("-1");
		bw.flush();
		bw.close();
	}
}

챌린저

문제

1253번: 좋다

# 해시

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

풀이

배열에서 좋은 수의 개수를 출력하는 문제이다.

좋은 수는 다른 두 수의 합으로 표현할 수 있는 수이다.

수의 개수가 최대 2000개이므로 두 수의 조합을 모두 구하여 해당 수가 배열에 있는지 체크하는 코드를 짜면 시간 내에 들어올 것으로 보인다.

처음에는 배열에서 두 수의 합인 수를 빠르게 찾기 위해서 hashSet을 사용해서 풀었는데 틀렸다.

Hashset을 사용하면 걸러내지 못하는 경우가 생겼기 때문이다.

예를 들어 배열에 1이 단 하나라고 하면 0과 연산하면 0 + 1 = 1이 되는데 해당 식은 다른 수 3개가 사용된 것이 아니므로 정답에서 제외되어야 한다.

그런데 배열에 1이 2개 이상이라면 0 + 1(i번째) = 1(j번째)에서 두 1의 위치가 달라 다른 수로 취급되어 정답에 카운팅해주어야한다.

이런 경우를 체크하기 위해서 맵을 이용하여 각 수가 있는지 없는지 뿐만 아니라 개수도 저장해주었다.

맵에서 두 수의 합이 있는 경우 아래의 세 경우를 제외하고 정답 셋에 추가한다.

if (a[i] == tmp && mp.get(a[i]) == 1)
    continue;
else if (a[j] == tmp && mp.get(a[j]) == 1)
    continue;
else if (a[i] == tmp && a[j] == tmp && mp.get(a[i]) == 2)
    continue;

코드

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

		for (int i = 1; i < n; i++) {
			for (int j = 0; j < i; j++) {
				int tmp = a[i] + a[j];
				if (mp.containsKey(tmp)) {
					if (a[i] == tmp && mp.get(a[i]) == 1)
						continue;
					else if (a[j] == tmp && mp.get(a[j]) == 1)
						continue;
					else if (a[i] == tmp && a[j] == tmp && mp.get(a[i]) == 2)
						continue;
					ans.add(tmp);
				}
			}
		}

		int cnt = 0;
		for (int i : a) {
			if (ans.contains(i))
				cnt++;
		}

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