Problem

• 문제 링크

주어진 배열의 값을 비교하여 순위를 매긴 배열을 리턴하는 문제입니다.

Solution

배열을 복사한 뒤에 정렬합니다.

배열의 값과 순위를 저장할 HashMap 을 선언합니다.

복사한 copyed 배열을 정렬한 다음에 순위를 넣습니다.

동점인 경우 값을 갱신하지 않기 위해 putIfAbsent 메소드를 사용합니다.

arr 배열을 다시 순회하면서 copyed 배열을 랭크값으로 갱신해주면 됩니다.

Java Code

class Solution {
    public int[] arrayRankTransform(int[] arr) {
        Map<Integer, Integer> map = new HashMap<>();    // value, rank
        int[] copyed = Arrays.copyOf(arr, arr.length);
        Arrays.sort(copyed);
        
        for (int value : copyed) {
            map.putIfAbsent(value, map.size());
        }
        
        for (int i = 0; i < arr.length; i++) {
            copyed[i] = map.get(arr[i]) + 1;
        }
        
        return copyed;
    }
}

Problem

• 문제 링크

주어진 nums 에서 val 원소를 지우는 문제입니다.

nums 배열 값을 직접 변화시키면 되며, 리턴값은 배열의 길이입니다.

Solution

단순하게 val 값이 아닐때에만 값을 넣어주고 인덱스를 증가시켜주면 됩니다.

Java Code

class Solution {
    public int removeElement(int[] nums, int val) {
        int index = 0;
        
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[index++] = nums[i];
            }
        }
        
        return index;
    }
}

Problem

• 문제 링크

배열에 0 이 존재하면 0 인덱스부터 오른쪽 쉬프트 합니다.

모든 쉬프트를 하고난 뒤의 배열의 모습을 구하면 됩니다.

Solution

투 포인터로 풀 수 있습니다.

0 의 갯수를 미리 카운트합니다.

추가 공간을 사용하지 않고 배열을 덮어써야 하기 때문에 마지막 인덱스부터 시작합니다.

zeroCount 는 쉬프트 횟수와 같기 때문에 arr[i + zeroCount] = arr[i] 로 값을 갱신해줍니다.

단 i + zeroCount 인덱스가 배열의 길이보다 작아야 합니다.

만약 arr[i] 가 0 이라면 그 즉시 arr[i + zeroCount] 에 0 을 넣고 인덱스를 하나 당겨줍니다.

시간복잡도는 O(n) 입니다.

Java Code

class Solution {
    public void duplicateZeros(int[] arr) {
        int zeroCount = 0;
        
        for (int a : arr) {
            if (a == 0) zeroCount++;
        }
        
        int n = arr.length;
        
        for (int i = n-1; i >= 0; i--) {
            int j = i + zeroCount;
            
            if (arr[i] == 0) {
                if (j < n) arr[j] = 0;
                zeroCount--;
                j--;
            }
            
            if (j < n) arr[j] = arr[i];
        }
    }
}

Problem

• 문제 링크

Singly Linked List 가 주어지면 리스트의 가장 중간부터 끝까지를 리턴하면 됩니다.

만약 List 의 길이가 짝수라면 뒤의 절반을 리턴합니다.

Solution

간단하게 two pointer 로 해결할 수 있습니다.

slow 는 한번, fast 는 두번 씩 전진하면 fast 가 끝에 도달했을 때 slow 의 위치가 List 의 중간입니다.

Java Code

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        return slow;
    }
}

Problem

배열 안에 있는 임의의 수 n 에 대해서 n+1 가 배열 안에 존재한다면 그 갯수를 전부 카운트해서 응답하는 문제입니다.

Solution 1

HashSet 을 선언하여 배열 안의 값을 전부 담아둡니다.

다시 for 문을 돌며 num + 1 값이 Set 에 존재한다면 갯수를 세줍니다.

Java Code 1

class Solution {
    public int countElements(int[] arr) {
        Set<Integer> set = new HashSet<>();
        
        for (int num : arr) {
            set.add(num);
        }
        
        int sum = 0;
        
        for (int num : arr) {
            if (set.contains(num + 1)) {
                sum++;
            }
        }
        
        return sum;
    }
}

Solution 2

0 <= arr[i] <= 1000 조건을 이용하여 배열의 각 숫자들의 갯수를 담아두고 더해주는 방법도 있습니다.

counting[i+1] > 0 이라면i+1 인 숫자가 존재한다는 뜻이므로 i 의 갯수인 counting[i] 를 전부 더해줍니다.

Java Code 2

class Solution {
    public int countElements(int[] arr) {
        int[] counting = new int[1002];
        
        for (int num : arr) {
            counting[num]++;
        }
        
        int sum = 0;
        
        for (int i=0; i<=1000; i++) {
            if (counting[i+1] > 0) {
                sum += counting[i];
            }
        }
        
        return sum;
    }
}

Problem

• 문제 링크

pattern 과 str 이 주어질 때 두 문자열의 패턴이 일치해야 합니다.

예시로 abba 가 주어지면 str 은 아래의 규칙을 가지면 됩니다.

1. 네 개의 단어로 이루어진다
2. 맨 앞과 맨 끝의 단어가 똑같다 (a)
3. 가운데의 두 단어가 똑같다 (b)

Solution

String[] words = str.split(" ") 코드로 문자들을 나누고 시작합니다.

pattern 의 길이와 words 배열의 길이는 같아야 합니다.

각 패턴 c 와 각 문자열 word 를 키값으로 하는 HashMap 을 각각 선언하여 담아둡니다.

만약 c 키값이 존재하는데 map 에 있는 map.get(c) 와 현재 위치의 word 가 일치하지 않는다면 패턴 불일치입니다.

pattern = "abba", str = "dog dog dog dog" 으로 주어지는 케이스가 있기 때문에 word 를 키값으로 한 HashMap 에서도 한번 더 검사해줍니다.

Java Code

class Solution {
    public boolean wordPattern(String pattern, String str) {
        Map<Character, String> charMap = new HashMap<>();
        Map<String, Character> strMap = new HashMap<>();
        String[] words = str.split(" ");
        
        if (pattern.length() != words.length) return false;
        
        for (int i=0; i<words.length; i++) {
            char c = pattern.charAt(i);
            String word = words[i];
            
            if (charMap.containsKey(c) && !charMap.get(c).equals(word)) {
                return false;
            }
            
            if (strMap.containsKey(word) && strMap.get(word) != c) {
                return false;
            }
            
            charMap.put(c, word);
            strMap.put(word, c);
        }
        
        return true;
    }
}

Problem

• 문제 링크

동전의 리스트가 주어지면 합이 amount 가 되는 경우의 수를 구하는 문제입니다.

Solution

dp 문제입니다.

dp[i] 는 i 원까지 동전의 경우의 수 입니다.

dp[i] += dp[i - coin] 식은 j 원이 되기 위해서 추가되는 동전의 수라고 생각하며 됩니다.

예를 들어 j 가 10 이고 동전 1, 2, 5 를 갖고 있을 때 경우의 수는

1. dp[9] + 1 원
2. dp[8] + 2 원
3. dp[5] + 5 원

이렇게 세가지 경우의 수가 됩니다.

dp[9], d[8], dp[5] 또한 각각 해당 인덱스까지의 모든 경우의 수 이기 때문에 전부 더해주면

dp[10] 의 총 경우의 수가 됩니다.

Java Code

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount+1];
        
        dp[0] = 1;
        
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        
        return dp[amount];
    }
}