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

비기너

문제

29701번: 모스 부호

#문자열 # 맵

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

풀이

모스부호 변환 표를 맵에 저장한다.

주어진 문자열을 split() 메서드를 이용하여 공백을 기준으로 분할하여 문자열 배열로 만든다.

맵을 이용해서 문자열 배열의 모스부호를 문자로 변환한다.

일일이 맵에 모스부호를 넣는 작업이 귀찮은 문제였다.

코드

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());
		String[] a = br.readLine().split(" ");
		HashMap<String, String> mp = new HashMap<>();
		mp.put(".-", "A");
		mp.put("-...", "B");
		mp.put("-.-.", "C");
		mp.put("-..", "D");
		mp.put(".", "E");
		mp.put("..-.", "F");
		mp.put("--.", "G");
		mp.put("....", "H");
		mp.put("..", "I");
		mp.put(".---", "J");
		mp.put("-.-", "K");
		mp.put(".-..", "L");
		mp.put("--", "M");
		mp.put("-.", "N");
		mp.put("---", "O");
		mp.put(".--.", "P");
		mp.put("--.-", "Q");
		mp.put(".-.", "R");
		mp.put("...", "S");
		mp.put("-", "T");
		mp.put("..-", "U");
		mp.put("...-", "V");
		mp.put(".--", "W");
		mp.put("-..-", "X");
		mp.put("-.--", "Y");
		mp.put("--..", "Z");
		mp.put(".----", "1");
		mp.put("..---", "2");
		mp.put("...--", "3");
		mp.put("....-", "4");
		mp.put(".....", "5");
		mp.put("-....", "6");
		mp.put("--...", "7");
		mp.put("---..", "8");
		mp.put("----.", "9");
		mp.put("-----", "0");
		mp.put("--..--", ",");
		mp.put(".-.-.-", ".");
		mp.put("..--..", "?");
		mp.put("---...", ":");
		mp.put("-....-", "-");
		mp.put(".--.-.", "@");
		for (String s : a)
			bw.write(mp.get(s));
		bw.flush();
		bw.close();
	}
}

미들러

문제

24444번: 알고리즘 수업 - 너비 우선 탐색 1

# bfs

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

풀이

그래프를 인접 리스트로 저장한다.

순회할 때 인접 정점을 오름차순으로 방문한다고 했으므로 각 정점의 연결 리스트를 오름차순으로 정렬한다.

시작 정점에서 bfs를 진행하고 정점의 방문 순서를 배열에 기록한다.

코드

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

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

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

	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());
		r = Integer.parseInt(st.nextToken());
		for (int i = 0; i <= n; i++)
			adj.add(new ArrayList<>());
		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			adj.get(u).add(v);
			adj.get(v).add(u);
		}
		for (int i = 1; i <= n; i++)
			Collections.sort(adj.get(i));
		visited = new boolean[n + 1];
		ans = new int[n + 1];
		bfs(r);
		for (int i = 1; i <= n; i++)
			bw.write(ans[i] + "\n");
		bw.flush();
		bw.close();
	}
}

챌린저

문제

2457번: 공주님의 정원

# 그리디 # 정렬

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

풀이

3월 1일부터 11월 30일까지 매일 적어도 하나의 꽃이 피어있도록 꽃을 선택하는데 선택한 꽃의 최소 개수를 구하는 문제이다.

우선 개화 날짜가 3월 1일 이하인 꽃들 중에서 하나를 선택해서 심어야 한다.

심는 꽃의 수를 최소화해야 하기 때문에 심을 수 있는 꽃 중에서 지는 날짜가 가장 큰 것을 택하면 된다.

해당 과정을 반복하여 꽃이 지는 날짜가 11월 30일보다 커지면 그때까지 심은 꽃의 수를 출력하면 된다.

꽃을 저장하기 위해 꽃의 개화 날짜와 지는 날짜를 가진 Flower 클래스를 정의하고 Flower 배열로 꽃을 관리한다.

해당 배열을 꽃의 개화 시기를 기준으로 오름차순으로 정렬한다.

날짜를 저장할 때 MMDD 이런 형식의 정수로 저장하면 대소를 쉽게 비교할 수 있다.

기준 날짜보다 개화 날짜가 이른 꽃들 중에서 가장 지는 날짜가 큰 꽃을 선택해야 하는데 최댓값을 효율적으로 찾기 위해 우선순위 큐를 이용한다.

우선순위 큐를 통해 꽃이 지는 날짜의 최댓값을 얻었으면 꽃의 수를 하나 증가시키고 기준 날짜를 해당 날짜로 변경한다.

기준 날짜가 11월 30일을 넘어가면 반복을 종료하고 꽃의 수를 출력하면 된다.

반복문 도중에 우선순위 큐가 비어있다면 심을 수 있는 꽃이 없는 것이므로 0을 출력하면 된다.

(C++는 pair를 지원해서 이를 사용하면 간단하게 정렬이나 저장을 할 수 있는데 자바는 없어서 좀 불편한 것 같다.)

코드

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

class Flower {
	int s, e;

	public Flower(int s, int e) {
		this.s = s;
		this.e = e;
	}
}

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());
		Flower[] a = new Flower[n];
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int sm, sd, em, ed;
			sm = Integer.parseInt(st.nextToken());
			sd = Integer.parseInt(st.nextToken());
			em = Integer.parseInt(st.nextToken());
			ed = Integer.parseInt(st.nextToken());
			a[i] = new Flower(sm * 100 + sd, em * 100 + ed);
		}

		Arrays.sort(a, new Comparator<Flower>() {
			@Override
			public int compare(Flower f1, Flower f2) {
				return Integer.compare(f1.s, f2.s);
			}
		});

		int s = 301, e = 1130, ans = 0, idx = 0;
		while(s <= e) {
			PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
			while(idx < n && a[idx].s <= s) 
				pq.add(a[idx++].e);
			if(pq.isEmpty()) {
				bw.write("0");
				bw.flush();
				bw.close();
				return;
			}
			int mx = pq.poll();
			ans++;
			s = mx;
		}
		
		bw.write(ans + "");
		bw.flush();
		bw.close();
	}
}