myBlog

문제 설명 보기

>> programmers.co.kr/learn/courses/30/lessons/49189

그래프를 순회하며 가장 비용이 많이 소모된 그래프 노드의 갯수를 반환하는 문제이다.

Node 객체를 구현하여 한번 풀었고, 그래프를 나타내는 이중리스트를 통해 한번 풀어봤다.

> Solution (Node 객체 구현)

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;

class Solution {
    private class Node{
        int val;

        ArrayList<Node> nextNodeList = new ArrayList<>();

        Node(int val){
            this.val = val;
        }
    }

    public int solution(int n, int[][] edge) {
        int answer = 0;
        HashSet<Node> isTraveledSet = new HashSet<>();
        HashMap<Integer, Node> nodeMap = new HashMap<>();
        LinkedList<Node> nextNodeList = new LinkedList<>();

        for(int idx = 1; idx <= n; idx++){
            nodeMap.put(idx, new Node(idx));
        }

        for(int[] intArr : edge){
            nodeMap.get(intArr[0]).nextNodeList.add(nodeMap.get(intArr[1]));
            nodeMap.get(intArr[1]).nextNodeList.add(nodeMap.get(intArr[0]));
        }

        nextNodeList.add(nodeMap.get(1));
        isTraveledSet.add(nodeMap.get(1));

        while(!nextNodeList.isEmpty()){
            answer = nextNodeList.size();
            for(int cnt = 0; cnt < answer; cnt++){
                for(Node node : nextNodeList.pollFirst().nextNodeList){
                    if(isTraveledSet.add(node)){
                        nextNodeList.addLast(node);
                    }
                }
            }
        }
        return answer;
    }
}

> Result

> Solution (Graph를 나타내는 List)

import java.util.*;

class Solution{
    public int solution(int n, int[][] edge) {
        int answer = 0;
        HashSet<Integer> isTraveledSet = new HashSet<>();
        HashMap<Integer, ArrayList<Integer>> graph = new HashMap<>();
        LinkedList<Integer> nextNodeList = new LinkedList<>();

        for(int[] intArr : edge){
            if(!graph.containsKey(intArr[0])){
                graph.put(intArr[0], new ArrayList<>());
            }
            if(!graph.containsKey(intArr[1])){
                graph.put(intArr[1], new ArrayList<>());
            }
            graph.get(intArr[0]).add(intArr[1]);
            graph.get(intArr[1]).add(intArr[0]);
        }
        
        nextNodeList.add(1);
        isTraveledSet.add(1);
        
        while(!nextNodeList.isEmpty()){
            answer = nextNodeList.size();
            for(int cnt = 0; cnt < answer; cnt++){
                for(int node : graph.get(nextNodeList.pollFirst())){
                    if(isTraveledSet.add(node)){
                        nextNodeList.addLast(node);
                    }
                }
            }
        }
        
        return answer;
    }
}

> Result

메모리 사용량과 같은 부분은 확실히 객체를 구현한 방식이 (아주약간)적게 사용되었다.

하지만 효율성에 있어서는 큰 차이를 보여주지 않는다.

문제 설명 보기

>> programmers.co.kr/learn/courses/30/lessons/43238

해당 문제의 핵심은 이것을 이분탐색법을 사용해 해결할 생각을 하는것이다.

문제가 설명한대로 실제 구현을 하게 되면 무조건 time out을 맞게 되어있다.

문제가 원하는 반환값은 시간이며, 시간은 항상 오름차순으로 정렬되어있다고 볼 수 있다.

이분탐색의 핵심인 정렬되어있는 숫자에서 탐색하는 범위를 절반으로 줄여 나가는 방법으로 O(logN)의 시간복잡도로 해결 할 수 있다.

> Solution

class Solution {
    public long solution(int n, int[] times){
        long left = 1;
        long right = (long)1000000000 * (long)1000000000;
        long mid = 0;
        long answer = 1;
        long sum;

        while( right > left ){
            mid = (left + right) / 2;
            sum = 0;
            for(int num : times){
                sum += mid / num;
            }
            if(sum >= n){
                answer = mid;
                right = mid;
            } else if (sum < n){
                left = mid + 1;
            }
        }

        return answer;
    }
}

* right는 입국 심사를 기다리는 10억명이 한명을 심사하는데 10억 분 걸리는 심사관 혼자서 심사하는 경우인, 가질 수 있는 가장 큰 숫자를 지정했다. Long.MAX_VALUE - 1을 사용해보았으나 아무래도 12번째 line에서 overflow가 발생하는 듯 싶어 이와같이 수정하였다.