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

비기너

문제

31562번: 전주 듣고 노래 맞히기

#맵

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

풀이

저장한 노래의 첫 세 음을 보고 노래를 찾는 문제이다.

노래의 첫 7개의 음을 저장한 문자열을 키로 노래를 맵에 저장한다.

첫 세 음이 주어지면 맵의 keySet에서 첫 세 음이 동일한 것의 개수를 센다.

조건에 따라 정답을 출력한다.

코드

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());
		HashMap<String, String> mp = new HashMap<>();
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			int t = Integer.parseInt(st.nextToken());
			String s = st.nextToken();
			String tmp = "";
			for (int j = 0; j < 7; j++)
				tmp += st.nextToken();
			mp.put(tmp, s);
		}

		while (m-- > 0) {
			String s = br.readLine().replaceAll(" ", "");
			int cnt = 0;
			String tmp = "";
			for (String i : mp.keySet()) {
				if (i.substring(0, 3).equals(s)) {
					tmp = i;
					cnt++;
				}
			}
			if (cnt == 0)
				bw.write("!\n");
			else if (cnt == 1)
				bw.write(mp.get(tmp) + "\n");
			else
				bw.write("?\n");
		}

		bw.flush();
		bw.close();
	}
}

미들러

문제

모음 사전

# 완전탐색

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

프로그래머스

풀이

dfs를 통해 깊이가 5까지 가는 과정에서 모든 단어를 생성할 수 있다.

단어를 생성하는 순서를 cnt에 저장하고 생성된 단어가 주어진 단어와 같다면 해당 cnt 값이 반환값이 된다.

코드

class Solution {
    int cnt = 0, ans = 0;
    char[] vowel = {'A', 'E', 'I', 'O', 'U'};
    
    void go(String s, int depth, String word) {
        if (!s.equals("")) {
            cnt++;
            if(s.equals(word)) {
                ans = cnt;
                return;
            }
        }
        if (depth == 5)
            return;
        for (int i = 0; i < 5;i++)
            go(s + vowel[i], depth + 1, word);
    }
    
    public int solution(String word) {
        go("", 0, word);
        return ans;
    }
}

챌린저

문제

1240번: 노드사이의 거리

# dfs

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

풀이

트리에서 두 노드 사이의 거리를 구하는 문제이다.

인접 리스트로 트리 구조를 저장한다.

출발점에서 dfs를 진행하며 각 edge의 weight를 d에 합산한다.

도착점에 다다르면 거리를 출력한다.

코드

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

class Edge {
	int u, v, w;

	public Edge(int u, int v, int w) {
		this.u = u;
		this.v = v;
		this.w = w;
	}
}

public class Main {
	static ArrayList<Edge> adj = new ArrayList<>();
	static int n, a, b, ans;
	static boolean flag;
	static boolean[] visited;

	static void dfs(int x, int d) {
		if (flag)
			return;
		visited[x] = true;
		if (x == b) {
			ans = d;
			flag = true;
			return;
		}
		for (Edge e : adj) {
			if (e.u == x && !visited[e.v])
				dfs(e.v, d + e.w);
		}

	}

	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());
		for (int i = 0; i < n - 1; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			adj.add(new Edge(u, v, w));
			adj.add(new Edge(v, u, w));
		}

		while (m-- > 0) {
			visited = new boolean[n + 1];
			st = new StringTokenizer(br.readLine());
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			flag = false;
			dfs(a, 0);
			bw.write(ans + "\n");
		}

		bw.flush();
		bw.close();
	}
}