꿀잠

https://leetcode.com/problems/network-delay-time/description/

주어진 노드로 부터 최단 경로를 묻는 다익스트라 알고리즘을 사용하는 문제였다.
예전에 공부했었는데 잘 기억이 나지 않아 복습하며 풀었다. 처음에 오래된 기억으로 더듬 거리며 풀다보니 시간 초과가 나왔다. 복습하며 잘못된 부분들을 해결 하며 풀었다.

다익스트라는 주어진 시작점으로 부터 최단 경로를 기준으로 경로를 이어 나가는 그리디 + DP 형식의 그래프 문제이다. 최단경로를 이어나가기 위해 PriorityQueue 사용했으며, 각 경로의 최소 길이를 배열에 저장하여 DP 배열로 활용하였다.

import java.util.*;  
  
public class Solution {  
    public int networkDelayTime(int[][] times, int n, int k) {  
  
        // node 정보를 담을 List 초기화  
        List<Node>[] nodes = new List[n + 1];  
        for(int i = 0; i < nodes.length; i++){  
            nodes[i] = new ArrayList<>();  
        }  
  
        for(int[] time: times){  
            int from = time[0];  
            int to = time[1];  
            int travel = time[2];  
            // node 정보 List에 담기  
            nodes[from].add(new Node(to, travel));  
        }  
  
        // 다익스트라 알고리즘을 사용하기 위한 pq        
        // 최단경로를 저장하기 위한 travels        
        PriorityQueue<Node> pq = new PriorityQueue<>();  
        int[] travels = new int[n + 1];  
  
        // 최단경로 무한대로 초기화  
        for(int i = 1; i < travels.length; i++){  
            travels[i] = Integer.MAX_VALUE;  
        }  
  
        // 시작지점 처리  
        travels[k] = 0;  
        pq.add(new Node(k, 0));  
  
        while(!pq.isEmpty()){  
            Node cur = pq.poll();  
  
            // 현재 지점까지 최단 경로인지 확인, visited 체크 역할  
            if (cur.travel > travels[cur.node]){  
                continue;  
            }  
  
            // 다음 경로 확인  
            for (Node next : nodes[cur.node]) {  
                int newTravel = cur.travel + next.travel;  
                // 다음 경로중 최단경로인 경우 pq 경로 추가  
                if (newTravel < travels[next.node]) {  
                    travels[next.node] = newTravel;  
                    pq.add(new Node(next.node, newTravel));  
                }  
            }  
        }  
  
        int answer = 0;  
        for(int i = 1; i < travels.length; i++){  
            // 가장 오래 걸린 경우 Network Delay를 마친 시간  
            answer = Math.max(travels[i], answer);  
        }  
  
        // 도달하지 못한경우 초기 거리값을 가지고 있으므로 -1, 아니면 answerreturn answer == Integer.MAX_VALUE ? -1 : answer;  
    }  
  
    private static class Node implements Comparable<Node>{  
        int node;  
        int travel;  
  
        Node(int node, int travel){  
            this.node = node;  
            this.travel = travel;  
        }  
  
        @Override  
        public int compareTo(Node o){  
            return Integer.compare(this.travel, o.travel);  
        }  
    }  
}

https://leetcode.com/problems/subsets/description/

주어진 배열의 모든 subset을 List로 리턴하는 문제이다.
각 요소를 순회하기 위하여 dfs로 백트래킹을 하여 가능하며, 중복 요소를 제거하기 위하여
현재 인덱스 이후 기준으로 dfs 탐색 하였다.

import java.util.*;  
  
public class Solution {  
    public List<List<Integer>> subsets(int[] nums) {  
        List<List<Integer>> answer = new ArrayList<>();  
        List<Integer> cur = new ArrayList<>();  
        boolean[] visited = new boolean[nums.length];  
        dfs(answer, cur, -1, visited, nums);  
  
        return answer;  
    }  
  
    private void dfs(List<List<Integer>> answer, List<Integer> cur, int curidx, boolean[] visited, int[] nums){  
        // Array 의 값을 복사하여 넣어준다.  
        List<Integer> subset = new ArrayList<>(cur);  
        answer.add(subset);  
  
        for(int i = curidx + 1; i < visited.length; i++){  
            if(!visited[i]){  
                cur.add(nums[i]);  
                int curSize = cur.size();  
                visited[i] = true;  
                dfs(answer, cur, i, visited, nums);  
                // 값을 다시 초기화하여 백트래킹 한다.  
                visited[i] = false;  
                cur.remove(curSize - 1);  
            }  
        }  
    }  
}

서브 셋을 추가할 땐 해당 배열을 복사해서 추가해주었다.

List의 참조 값을 바라보므로 해당 시점의 배열 요소로 복사해서 넣어주어야 한다.

https://leetcode.com/problems/binary-tree-level-order-traversal/description/

주어진 커스텀 클래스인 이진트리 노드를 레벨에 따른 중첩 List배열로 반환하는 문제이다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {  
    public List<List<Integer>> levelOrder(TreeNode root) {  
        List<List<Integer>> answer = new ArrayList<>();  
        if (root == null) {  
            return answer;  
        }  
  
        Queue<TreeNode> que = new ArrayDeque<>();  
        que.offer(root);  
  
        while (!que.isEmpty()) {  
            List<Integer> levelList = new ArrayList<>();  
            int queSize = que.size();  
  
            while (queSize-- > 0) {  
                TreeNode node = que.poll();  
                levelList.add(node.val);  
                if (node.left != null) {  
                    que.offer(node.left);  
                }  
  
                if (node.right != null) {  
                    que.offer(node.right);  
                }  
            }  
            if (levelList.size() > 0) {  
                answer.add(levelList);  
            }  
        }  
  
        return answer;  
    }
}

레벨 단위로 처리하기 위해서 Queue를 이용하였다. 하나의 레벨을 Queue 에 넣어 전부 꺼내며 리스트를 완성하고, 전부 꺼내는 동안 다음 레벨의 노드를 Queue에 넣어 순차적으로 레벨 List를 만들어 주었다. 하나의 레벨을 꺼내며 Queue에 새로 넣기 때문에 하나의 레벨을 빼내기 전에 사이즈를 체크해서 꺼내면 된다.

https://leetcode.com/problems/reverse-linked-list/description/

주어진 커스텀 클래스 형태인 Linked List 를 역순으로 생성해서 반환하는 문제이다.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

class Solution {
    public ListNode reverseList(ListNode head) {
		ListNode answer = null;  
		  
		while(head != null){  
		    answer = new ListNode(head.val, answer);  
		    head = head.next;  
		}  
		  
		return answer;
    }
}

문제는 간단하게 헤드를 기준으로 새로운 노드를 만들고 순서대로 이어 붙이면 된다.
문제는 헤드부터 주어진 리스트 노드를 기준으로 새로 노드를 만들면 next에 할당하면 된다. 생성자 및 null 체크를 잘 활용해야 했다.

코딩테스트 문제를 풀 다 시간 초과를 해결했던 경험에 대한 기록이다.

백준의 텀프로젝트 문제를 풀던 중(https://www.acmicpc.net/problem/9466)
내가 작성한 코드가 충분히 최적화 되었다고 생각했음에도 계속 시간 초과가 발생하였다.
관련하여 문제를 찾던 중 자바의 배열 생성이 시간 초과의 원인이 될 수 있다는 글을 발견하고, 해당 부분을 수정하여 통과하였다.

    private static int solution() throws IOException {
        int studentNum = Integer.parseInt(br.readLine());
        int[] team = new int[studentNum + 1];
        String[] input = br.readLine().split(" ");
        for(int i = 1; i <= studentNum; i++){
            team[i] = Integer.parseInt(input[i-1]);
        }

        checked = new boolean[studentNum + 1];
        result = studentNum;

        for(int i = 1; i <= studentNum; i++){
            if(checked[i]) continue;
            // 배열 초기화
            visited = new int[studentNum + 1];
            findTeam(team, i, 1, visited);
        }

        return result;
    }

    private static void findTeam(int[] team, int student, int seq, int[] visited){
        if(checked[student]) return;
        checked[student] = true;
        visited[student] = seq;

        int next = team[student];
        if(visited[next] != 0){
            result -= (seq - visited[next] + 1);
        }else{
            findTeam(team, next, seq + 1, visited);
        }
    }

시간 초과가 나던 시점의 내 코드는 위와 같았으며, 완전 탐색을 위하여 탐색 방문 배열을 new 명령어로 생성하고 있었다. 해당 배열의 크기는 최대 100001의 크기를 갖는 문제이다.

    private static int solution() throws IOException {
        int studentNum = Integer.parseInt(br.readLine());
        int[] team = new int[studentNum + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= studentNum; i++){
            team[i] = Integer.parseInt(st.nextToken());
        }

        checked = new boolean[studentNum + 1];
        int[] visited = new int[studentNum + 1];
        result = studentNum;
        for(int i = 1; i <= studentNum; i++){
            if(checked[i]) continue;
            findTeam(team, i, 0, visited);
        }

        return result;
    }

    private static void findTeam(int[] team, int student, int seq, int[] visited){
        if(checked[student]) return;
        seq++;
        checked[student] = true;
        visited[student] = seq;

        int next = team[student];
        if(visited[next] != 0){
            result -= (seq - visited[next] + 1);
        }else{
            findTeam(team, next, seq, visited);
        }

        // dfs 내부에서 사용후 값 원상복구
        visited[student] = 0;
    }

}

시간 초과를 해결한 코드는 위와 같다. dfs를 반복하기 이전에 생성한 배열의 값을 new 가 아닌 직접 초기화 하여 배열을 사용하였다. 참고한 글(https://okky.kr/questions/1450047)에 따르면 배열을 생성한다는 것은 새로운 객체의 메모리에 할당 받는 부분, java의 경우 해당 배열의 초기 값을 초기화하는 부분 등으로 인하여 런타임 실행 시간이 늘어날 수 있다고 한다. 단순한 코드의 차이였지만 객체 생성의 효율에 대해 고민할 수 있었다.