Repository

바보같이 너무 많이 생각해서 어려웠던 문제였습니다.

문제자체는 단순합니다.

parent 값들을 주고 해당 값으로 생성된 node들 중 하나를 삭제하고, 이후 leaf의 갯수를 알아내면 되는 문제입니다.

parent와 index값을 저장을 하고,

index를 부모로 가지는 node들을 child로 저장,

삭제된 노드들의 정보를 가지게 된다면 간단하게 해결할 수 있는 문제입니다.

다만 주의할 점은 현재 삭제된 노드들만 가지고 있는 노드 또한 leaf라는 점입니다.

이점은 코드를 확인해보며 찾아보시기 바랍니다.

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[] parents = new int[N];
        boolean[] isDeleted = new boolean[N];
        List<List<Integer>> graph = new ArrayList<>();

        for(int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }

        int root = -1;
        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i = 0; i < N; i++) {
            parents[i] = Integer.parseInt(st.nextToken());
            if(parents[i] == -1) {
                root = i;
            } else {
                graph.get(parents[i]).add(i);
            }
        }
        int deleteNode = Integer.parseInt(br.readLine());
        if(parents[deleteNode] > -1) {
            delete(graph.get(parents[deleteNode]), isDeleted, deleteNode);
        } else {
            isDeleted[root] = true;
        }
        bw.write(countLeafNode(graph, isDeleted, root) + "");
        bw.flush();
        br.close();
        bw.close();
    }

    public static void delete(List<Integer> graph, boolean[] isDeleted, int node) {
        for(int child : graph) {
            if(child == node) {
                isDeleted[child] = true;
                return;
            }
        }
    }

    public static int countLeafNode(List<List<Integer>> graph, boolean[] isDeleted, int node) {
        if(isDeleted[node]) return 0;
        if(graph.get(node).isEmpty()) return 1;
        int count = 0;

        for(int child : graph.get(node)) {
            count += countLeafNode(graph, isDeleted, child);
        }

        return count == 0 ? 1 : count;
    }
}

문제를 보면 모든 노드들은 연결이 되어있고, 모든 노드들을 돌아볼 때 가장 적은 종류의 비행기( 간선 정보 )를 타고 움직이는 수를 알아내야하는 것이 문제의 의도 입니다.

이때 우리는 모든 노드가 연결되어있고, 최소한의 경로로 모든 노드를 방문해야한다는 조건에서 최소신장 트리를 떠올릴 수 있어야 합니다.

최소신장 트리의 모든 노드를 연결하면서 가중치의 합을 구하면 되겠는데, 이때 값은 N - 1로써 가장 간단하게 구할 수 있습니다.

(N은 노드 수입니다.)

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

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            for (int i = 0; i < m; i++) {
                br.readLine();
            }
            sb.append(n - 1).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        br.close();
        bw.close();
    }

}

• 시간복잡도: O(1)
• 공간복잡도: O(1)

입력 예제를 확인해보면 N개의 노드와 N - 1개의 간선 정보가 주어지는 것을 확인해 볼 수 있습니다.

그림으로 표현하면 위와 같이 표현할 수 있으며, 해당 정보를 통해 2번부터 N번 까지 노드들의 부모정보를 출력하면 되는 문제입니다.

즉 2번의 부모 4, 3번의 부모 6, 4번의 부모 1, 5번의 부모 3, 6번의 부모 1, 7번의 부모 4번 해서 결과는 4, 6, 1, 3, 1, 4가 나오면 되는 것 입니다.

여기서 주의해야하는 점은 해당 트리는 자식 노드가 최대 2개가 주어진다는 말이 없으니 일반 트리이며, 자식 노드는 N개가 될 수 있다는 말입니다.

문제 풀이는 생각보다 간단합니다. 

문제에서 트리의 루트를 1번으로 잡는다 하였으니, 1번의 자식들의 부모를 Bfs 탐색을 통해 확인한 다음 2번노드 부터 부모 번호를 출력해주면 됩니다.

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;

        List<Integer>[] arr = new List[N + 1];
        for( int i = 1; i <= N; i++ ) {
            arr[i] = new ArrayList<>();
        }

        for (int i = 1; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            arr[from].add(to);
            arr[to].add(from);
        }

        int[] parent = new int[N + 1];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        parent[1] = 1;

        while (!queue.isEmpty()) {
            int current = queue.poll();
            for(int child: arr[current]){
                if (parent[child] == 0) {
                    parent[child] = current;
                    queue.add(child);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 2; i <= N; i++) {
            sb.append(parent[i]);
            sb.append("\n");
        }
        System.out.println(sb);
    }
}

• 시간복잡도: O(N)
• 공간복잡도: O(N)

모스 부호 문제입니다.

매우 간단한 문제이며, 우선 시간제한과 메모리 제한을 확인해 보겠습니다.

입력 예제를 보면  N은 최대 100 이하의 개수가 주어진다 합니다.

그럼 이 문제를 접할 때 최악의 경우 모스부호 100개를 문자열로 변환해야 하는 문제라고 볼 수 있습니다.

예제로 준 모스 부호표를 보면 41개를 명시한 표를 통해 답을 만들 수 있습니다.

최악의 경우 100개의 모스 부호를 41개 중 찾기 위해 반복문을 돌린다 하면 4100번 돌려 해결을 할 수 있습니다.

다만, 4100번 돌려 답을 찾는 것은 O(n)의 복잡도를 가지게 되지만 41이란 상수는 빅오표기법상 표기를 안 하니 딱히 효율적인 알고리즘은 아니라 생각합니다.

거기서 우리는 Map이라는 자료구조를 활용하여 O(1) 시간복잡도로 모스 부호를 검색할 수 있는 방법을 떠올릴 수 있습니다.

public class Problem29701 {

    public static Map<String, String> initMorseCodeMap() {
        Map<String, String> morseCodeMap = new HashMap<>();
        morseCodeMap.put(".-", "A");
        morseCodeMap.put("-...", "B");
        morseCodeMap.put("-.-.", "C");
        morseCodeMap.put("-..", "D");
        morseCodeMap.put(".", "E");
        morseCodeMap.put("..-.", "F");
        morseCodeMap.put("--.", "G");
        morseCodeMap.put("....", "H");
        morseCodeMap.put("..", "I");
        morseCodeMap.put(".---", "J");
        morseCodeMap.put("-.-", "K");
        morseCodeMap.put(".-..", "L");
        morseCodeMap.put("--", "M");
        morseCodeMap.put("-.", "N");
        morseCodeMap.put("---", "O");
        morseCodeMap.put(".--.", "P");
        morseCodeMap.put("--.-", "Q");
        morseCodeMap.put(".-.", "R");
        morseCodeMap.put("...", "S");
        morseCodeMap.put("-", "T");
        morseCodeMap.put("..-", "U");
        morseCodeMap.put("...-", "V");
        morseCodeMap.put(".--", "W");
        morseCodeMap.put("-..-", "X");
        morseCodeMap.put("-.--", "Y");
        morseCodeMap.put("--..", "Z");
        morseCodeMap.put(".----", "1");
        morseCodeMap.put("..---", "2");
        morseCodeMap.put("...--", "3");
        morseCodeMap.put("....-", "4");
        morseCodeMap.put(".....", "5");
        morseCodeMap.put("-....", "6");
        morseCodeMap.put("--...", "7");
        morseCodeMap.put("---..", "8");
        morseCodeMap.put("----.", "9");
        morseCodeMap.put("-----", "0");
        morseCodeMap.put("--..--", ",");
        morseCodeMap.put(".-.-.-", ".");
        morseCodeMap.put("..--..", "?");
        morseCodeMap.put("---...", ":");
        morseCodeMap.put("-....-", "-");
        morseCodeMap.put(".--.-.", "@");
        return morseCodeMap;
    }

    public static void main(String[] args) throws IOException {
        Map<String, String> morseCodeMap = initMorseCodeMap();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        StringBuilder sb = new StringBuilder();
        while(N-- > 0) {
            String morseCode = st.nextToken();
            sb.append(morseCodeMap.get(morseCode));
        }
        System.out.println(sb);
    }
}

• 시간 복잡도: O(n)
• 공간 복잡도: O(n)

이번 문제 또한 매우 간단한 문제입니다.

N명의 학생이 존재하고, 3번째 줄부터 N개 나오는 학생들 이름을 가지고 인기도를 측정하여 출력하면 되는 문제입니다.

우선 여기서 봐야 할 점은 인기도 측정 방식과 정렬인데요.

인기도 측정 방식은 그냥 나오는 학생 이름들을 전부 인기도에 반영하면 되는 간단한 문제이고,

정렬은 주어진 조건에 맞춰 정렬하면 됩니다.

정렬의 경우 저는 Stream의 sorted함수를 사용하였는데요. 이때, sort조건을 커스텀함으로써 간단하게 정렬하였습니다.

이후 reduce를 활용하여 StringBuilder에 값들을 담게 했는데요, 이는 String과 달리 StringBuilder는 불변성이 아니어서 메모리 활용 측면에서 훨씬 효율적이라 판단하여 사용하였습니다.

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Map<String, Integer> map = new HashMap<>();
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i = 0; i < N; i++) {
            map.put(st.nextToken(), 0);
        }

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            while (st.hasMoreTokens()) {
                String to = st.nextToken();
                map.put(to, map.get(to) + 1);
            }
        }

        StringBuilder answer = map.entrySet().stream().sorted((prev, now) -> {
            if(prev.getValue() != now.getValue()) return now.getValue() - prev.getValue();
            return prev.getKey().compareTo(now.getKey());
        }).reduce(new StringBuilder(),(sb, entry) -> sb.append(entry.getKey()).append(" ").append(entry.getValue()).append("\n"),StringBuilder::append);
        System.out.println(answer);
    }
}

• 시간복잡도: O(n)
•  공간복잡도: O(n)

이번 문제는 고민 했던 것보다 꽤 쉽게 풀어져 가져와보았습니다.

위와 같이 문제가 주어졌습니다.

쉽게 생각해보면 점이 n개 주워졌을 때 x나 y에 평행이 되는 선의 갯수를 구하라는 뜻인데,

여기서 살짝 생각해보면 좋은 점은 x와 y에 평행이 되려면 어떤 조건을 가져야하는가 입니다.

x에 평행이 되려면 두 점의 y좌표는 동일해야할 것이고, y에 평행이 되려면 x좌표가 동일해야할 것 입니다.

즉, x점을 기준으로 묶은 자료와 y점을 기준으로 묶은 자료만 있다면 쉽게 문제를 풀 수 있는 것입니다.

public class Main {

    static Map<Integer, Integer> xLineMap = new HashMap<>();
    static Map<Integer, Integer> yLineMap = new HashMap<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        for(int i = 0; i < n; i++) {
            String[] strs = br.readLine().split(" ");
            int x = Integer.parseInt(strs[0]);
            int y = Integer.parseInt(strs[1]);
            xLineMap.put(x, xLineMap.getOrDefault(x, 0) + 1);
            yLineMap.put(y, yLineMap.getOrDefault(y, 0) + 1);
        }
        int answer = 0;
        for (int count : xLineMap.values()) {
            if (count > 1) {
                answer++;
            }
        }
        for (int count : yLineMap.values()) {
            if (count > 1) {
                answer++;
            }
        }
        System.out.println(answer);
    }
}

위 문제를 확인해보면 2초의 시간초가 주어지고, n은 최대 100,000이라고 합니다.

이를 통해보면 알고리즘은 O(n)의 성능을 가지고 있도록 작성하는 것이 합리적이라 생각합니다.

위 알고리즘을 보면 n을 받아 n번 반복함으로 O(n)의 시간복잡도를 가지고 있다고 볼 수 있습니다.

또한, n을 받아 사용하는 데이터들을 보면 n개의 데이터들만을 활용하는 것을 볼 수 있어 공간복잡도 또한 O(n) 혹은 O(2n)의 복잡도를 가지고 있습니다.

• 시간 복잡도: O(n)
• 공간 복잡도: O(n)