Page tree
Skip to end of metadata
Go to start of metadata
  1. 타임아웃..

    public int firstBadVersion(int n) {
    		final Boolean[] booleans = IntStream.rangeClosed(1, n)
                    .mapToObj(i -> isBadVersion(i))
                    .toArray(Boolean[]::new);
            
            return Arrays.binarySearch(booleans, false);
        }
    
    
    // 회고  13 ms, faster than 37.95%
    
    public int firstBadVersion(int n) {
            int left = 1;
            int right = n;
    
            while (left <= right) {
                int mid = (left + right) >>> 1;
    
                if (isBadVersion(mid)) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            return left;
        }
    
    
  2. 회고  (Runtime0 ms, faster than 100.00% of Java online submissions)

    public int[] searchRange(int[] nums, int target) {
            int start = leftSearch(nums, target);
            int end = rightSearch(nums, target);
    
            if (start > end) {
                return new int[]{-1, -1};
            }
            return new int[]{start, end};
        };
    
        private int leftSearch(int[] nums, int target) {
            int left = 0;
            int right = nums.length - 1;
    
            while (left <= right) {
                int mid = (left + right) >>> 1;
                if (target > nums[mid]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            return left;
        }
    
        private int rightSearch(int[] nums, int target) {
            int left = 0;
            int right = nums.length - 1;
    
            while (left <= right) {
                int mid = (left + right) >>> 1;
                if (target >= nums[mid]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            return right;
        }
  3. 회고..(fail)

    @Test
        void test() {
            int[][] a = {{2,1,1}, {2,3,1}, {3,4,1}};
    
            networkDelayTime(a, 4, 2);
        }
    
        Map<Integer, Integer> dist = Collections.EMPTY_MAP;
        public int networkDelayTime(int[][] times, int N, int K) {
            for (int i = 1; i <= N; i++) {
                dist.put(i, Integer.MAX_VALUE);
            }
            
            Map<Integer, List<int[]>> graph = new HashMap<>();
    
            for (final int[] time : times) {
                int e = time[0];
                if (!graph.containsKey(e)) {
                    graph.put(e, new ArrayList<>());
                }
    
                graph.get(e)
                        .add(new int[]{time[2], time[1]});
            }
    
            for (final Integer node : graph.keySet()) {
                graph.get(node).sort(Comparator.comparingInt(a -> a[0]));
            }
            
            
            return 1;
        }
    
        private void dfs(Map<Integer, List<int[]>> graph, int node, int value) {
            if (value >= dist.get(node)) {
                return;
            }
            
            dist.put(node, value);
            if (graph.containsKey(node)) {
                for (final int[] ints : graph.get(node)) {
                    dfs(graph, ints[1], value + ints[0]);
                }
            }
        }
  • No labels