기억하고싶은것들

Given an integer array nums,

move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

integer 배열 nums가 주어진다. 

0을 배열의 맨뒤로 옮겨라, 단 0이 아닌 배열의 숫자 순서는 유지해야 한다.

주의 : 주어진 배열을 그대로 사용해야 한다. 다른 배열을 선언해서는 안된다.

두 개의 포인터를 이용하여서 배열의 맨 앞을 가리키도록 하여

하나는 값이 0인 배열의 인덱스를 가리키고

다른 하나는 0이 아닌 배열의 인덱스를 찾아 서로 위치를 바꾸어주도록 문제를 풀어보자 

    public void moveZeroes(int[] nums) {
        int idx = 0; // 0을 가르키는 포인터

        for (int i = 0; i < nums.length; i++) { // 0이 아닌 값을 찾는 포인터 
            if (nums[i] != 0) {
                swap(nums, i, idx);
                idx++;
            }
        }
    }

만약 배열의 첫 인덱스가 0이 아닌 경우에는 아래 for문에서 0을 가리키는 idx의 값이 ++ 되므로 0을 찾을 때까지 

idx, i가 같이 ++된다. 

    private void swap(int[] nums, int i, int idx) {
        int tmp = nums[i];
        nums[i] = nums[idx];
        nums[idx] = tmp;
    }

문제출처 : 

https://leetcode.com/problems/move-zeroes/

704. Binary Search

Given an array of integers nums which is sorted in ascending order, and an integer target, 

write a function to search target in nums. 

If target exists, then return its index. Otherwise, return -1.
You must write an algorithm with O(log n) runtime complexity.

오름차순으로 정렬된 integer 배열과 타깃 integer가 주어진 상황에서 

타깃을 배열에서 찾는 코드를 작성하여라

타깃이 존재한다면 해당 숫자가 들어있는 배열의 인덱스를 반환하고, 없다면 -1을 반환하라

반드시 시간 복잡도가 O(log n)인 알고리즘으로 작성하라

정렬된 배열에서 값을 찾는 문제로 시간 복잡도가 O(log n)인 알고리즘을 사용해야 한다. 

Binary Search를 이용하여 문제를 해결하도록 하자.

    public int search(int[] nums, int target) {

        int left = 0;
        int right = nums.length - 1;
        int pivot = 0;

        while (left <= right) {
            pivot = (left + right) / 2;

            if (target == nums[pivot]) {
                return pivot;
            } else if (nums[pivot] < target) {
                left = pivot + 1;
            } else {
                right = pivot - 1;
            }
        }
        return -1;
        
    }

먼저 left, right 인덱스를 지정하고,

해당 인덱스들을 기반으로 while loop의 조건을 지정한다.

Binary Search의 경우에는 left 인덱스가 right 인덱스보다 큰 경우에는 타깃으로 하는 값이 없는 경우이므로 해당 조건이 while loop에 들어가게 된다. 

Binary Search에서는 각각의 left, right 인덱스의 중간값을 pivot으로 설정하고 

해당 값을 기준으로 다음 조건의 인덱스를 지정한다.

pivot 인덱스의 배열값이 타깃보다 작은 경우에는 left 인덱스를 pivot 다음 인덱스로 지정

pivot 인덱스의 배열값이 타깃보다 큰 경우에는 right 인덱스를 pivot 이전 인덱스로 지정

문제 출처

https://leetcode.com/problems/binary-search/

Given an integer array nums and an integer k, return the k most frequent elements.

You may return the answer in any order.

입력값으로 integer 배열과 integer k를 받는다. 가장 많이 등장하는 k개의 요소들을 반환하라.

어떠한 순서로 반환해도 상관없다.

가장 큰 값이나, 가장 작은 값을 찾는 문제와 비슷하게 가장 많이 등장하는 k개의 요소를 찾는 문제이므로

Heap을 이용하는 Priority Queue를 사용해서 찾으면 될 것이다.

Priority Queue를 구성하기 전에 비교하는 값이 등장하는 횟수이므로, 횟수를 비교 가능한 Map을 구성한 후에 Heap에 요소로 사용해보자.

    public static int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>(); // 등장 횟수 Count
        for (int i : nums) {
            map.put(i, map.getOrDefault(i, 0) + 1);
        }

        PriorityQueue<Map.Entry<Integer, Integer>> queue = 
            new PriorityQueue<>((a, b) -> b.getValue() - a.getValue()); // 내림차순
        queue.addAll(map.entrySet());

        int[] rst = new int[k];
        for (int i = 0; i < k; i++) {
            rst[i] = queue.poll().getKey();
        }
        return rst;
    }

먼저 Map을 이용하여 주어진 Nums의 요소들이 등장하는 횟수를 카운트 해준다.

후에, 해당 Map을 기준으로 Priority Queue를 구성해준다.

Queue의 비교대상은 Map의 Key가 아닌 Value이다. ( 등장 횟수 )

이제 Priority Queue가 등장 횟수 순으로 정렬이 되었으므로, 입력값이 k만큼 Queue에서 Poll 해주면 된다.

There are n rooms labeled from 0 to n - 1 and you start in the room 0.

All the rooms labeled from 1 to n are initially locked and you cannot enter a locked room without having its key.

When you visit a room, you may find a set of distinct keys in it

and you can use them to open locked rooms and enter them.

You can visit the same room any number of times and the goal is to visit all the nrooms.

Given an array rooms where rooms [i] is the set of keys that you can obtain if you visited room i,

return true if you can visit all the rooms, or falseotherwise.

0부터 n-1까지의 이름 지어진 방이 있고, 0번째 방부터 시작된다.

1부터 n까지의 모든 방은 초반에 잠겨 있고, 열쇠가 없이는 들어갈 수 없다.

특정 방에 방문했을 때, 열쇠 꾸러미를 발견할 수 있고 그 열쇠 꾸러미를 이용해 잠긴 방을 방문할 수 있다.

방문했던 방에는 몇 번이고 중복해서 방문할 수 있고, 최종 목표는 모든 방에 방문하는 것이다.

방들의 배열이 주어지고, 해당 방에는 열쇠 꾸러미 정보를 가지고 있다.

만약 주어진 정보로 모든 방들을 방문할 수 있으면 true를 반환하고 그렇지 않으면 false를 반환하라.

주어진 방들과 열쇠들의 정보는 tree 형태로 형상화할 수 있다.

주어진 트리를 방문하며, 방문한 방들의 정보를 저장하고 모든 트리의 노드를 순회했을 때 저장한 방문한 방들의 모든 정보가 주어진 방들의 길이와 같으면 모든 방을 방문한 것이다.

recursive 한 형태로 순환을 하고, Depth First Search를 이용하여 tree를 방문하여 보자.

    public boolean canVisitAllRooms(List<List<Integer>> rooms) {

        List<Integer> visited = new ArrayList<>(); // 방문한 방들의 정보를 저장

        recursiveVisit(visited, rooms, 0); // 0번 방부터 시작

        if (visited.size() == rooms.size()) { // 주어진 방의 갯수와 방문한 방의 갯수 비교 
            return true;
        }
        return false;
    }

    private void recursiveVisit(List<Integer> visited, List<List<Integer>> rooms, int i) {

        visited.add(i);
        List<Integer> list = rooms.get(i);

        for (int idx : list) {
            if (!visited.contains(idx)) { // 이미 방문한 방은 다시 방문할 필요가 없다
                recursiveVisit(visited, rooms, idx);
            }
        }
    }