Problem

07-counting-elements


배열 안에 있는 임의의 수 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;
    }
}


저작자표시 비영리

'알고리즘 문제 > LeetCode' 카테고리의 다른 글

[LeetCode Easy] Duplicate Zero (Java)  (0) 2020.05.03
[LeetCode Easy] Middle of the Linked List (Java)  (0) 2020.04.09
[LeetCode Easy] Word Pattern (Java)  (1) 2020.04.09
[LeetCode Medium] Coin Change 2 (Java)  (0) 2020.04.09
[LeetCode Easy] Best Time to Buy and Sell Stock II (Java, Kotlin)  (0) 2020.04.05

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;
    }
}


저작자표시 비영리

'알고리즘 문제 > LeetCode' 카테고리의 다른 글

[LeetCode Easy] Middle of the Linked List (Java)  (0) 2020.04.09
[LeetCode] Counting Elements (Java)  (0) 2020.04.09
[LeetCode Medium] Coin Change 2 (Java)  (0) 2020.04.09
[LeetCode Easy] Best Time to Buy and Sell Stock II (Java, Kotlin)  (0) 2020.04.05
[LeetCode Easy] Move Zeroes (Java)  (0) 2020.04.04

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];
    }
}


저작자표시 비영리

'알고리즘 문제 > LeetCode' 카테고리의 다른 글

[LeetCode] Counting Elements (Java)  (0) 2020.04.09
[LeetCode Easy] Word Pattern (Java)  (1) 2020.04.09
[LeetCode Easy] Best Time to Buy and Sell Stock II (Java, Kotlin)  (0) 2020.04.05
[LeetCode Easy] Move Zeroes (Java)  (0) 2020.04.04
[LeetCode Medium] Battleships in a Board (Java)  (0) 2020.03.30

Problem


앞으로의 물건의 예상 가격이 주어 질 때 팔 수 있는 물건의 최대 가격을 구하는 문제입니다.



Solution

Greedy 로 풀면 됩니다.

이 문제에서 중요한 포인트는 물건을 판 당일에 그 물건을 다시 살 수 있다 라는 점입니다.

예를 들어 [1, 5, 7, 6] 이 주어졌을 때 일반적으로 1 에 사서 7 에 파는 게 답이라는 사실을 알 수 있습니다.

하지만 조금 틀어서 생각하면 1 에 사서 5 에 팔고, 다시 5 에 사서 7 에 팔면 동일한 결과가 나옵니다.

즉, 가격에 관계 없이 항상 물건을 사서 다음 날이 비싸면 판다 라는 관점으로 접근하면 됩니다.



Java Code

class Solution {
    public int maxProfit(int[] prices) {
        int sum = 0;

        for (int i = 0; i < prices.length - 1; i++) {
            if (prices[i] < prices[i+1]) {
                sum += prices[i+1] - prices[i];
            }
        }

        return sum;
    }
}

Kotlin Code

class Solution {
    fun maxProfit(prices: IntArray): Int {
        return prices.toList().windowed(2).fold(0) { 
            acc, (l, r) -> acc + maxOf(r-l, 0) 
        }
    }
}
저작자표시 비영리

'알고리즘 문제 > LeetCode' 카테고리의 다른 글

[LeetCode Easy] Word Pattern (Java)  (1) 2020.04.09
[LeetCode Medium] Coin Change 2 (Java)  (0) 2020.04.09
[LeetCode Easy] Move Zeroes (Java)  (0) 2020.04.04
[LeetCode Medium] Battleships in a Board (Java)  (0) 2020.03.30
[LeetCode Easy] Remove All Adjacent Duplicates In String (Java)  (0) 2020.03.25

Problem


주어진 배열에서 0 인 값을 전부 오른쪽 끝으로 보내면 됩니다.

나머지 값은 정렬하는 것이 아니라 원래 있던 순서 그대로 둡니다.

또다른 배열을 만들지 않고 주어진 배열 안에서만 해결해야 합니다. in-place

연산을 최소화 해야 합니다.



Solution

two-pointer 로 간단하게 문제를 풀 수 있습니다.

1. One Loop

값을 갱신할 slow 인덱스와 전체 배열을 훑을 fast 인덱스를 사용합니다.

nums[fast] 에 값이 있는 경우에만 nums[slow] 에 넣어 주면 되는데 주의할 점은 두 인덱스가 같지 않아야 합니다.

즉, fast 인덱스가 말그대로 slow 인덱스보다 큰 상황에서만 갱신해야 합니다. 안그러면 nums[slow] 에는 0 만 들어갑니다.

2. Two Loop

index 변수 하나를 선언하고 0 부터 시작합니다.

일반적인 for 문을 돌면서 num 값이 0 이 아닐 때만 nums[index] 에 넣어줍니다.

지나간 값은 다시 확인할 필요가 없기 때문에 nums 배열 자체에 갱신해주어도 문제가 없습니다.

for 문이 끝났을 때의 index 부터 배열 끝까지 남은 값을 0 으로 채워주면 됩니다.



Java Code

// 1. one loop
class Solution {
    public void moveZeroes(int[] nums) {
        int slow = 0;

        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != 0) {
                if (fast != slow) {
                    nums[slow] = nums[fast];
                    nums[fast] = 0;
                }

                slow++;
            }
        }
    }
}

// 2. two loop
class Solution {
    public void moveZeroes(int[] nums) {
        int index = 0;

        for (int num : nums) {
            if (num != 0) {
                nums[index++] = num;
            }
        }

        while (index < nums.length) {
            nums[index++] = 0;
        }
    }
}
저작자표시 비영리

'알고리즘 문제 > LeetCode' 카테고리의 다른 글

[LeetCode Medium] Coin Change 2 (Java)  (0) 2020.04.09
[LeetCode Easy] Best Time to Buy and Sell Stock II (Java, Kotlin)  (0) 2020.04.05
[LeetCode Medium] Battleships in a Board (Java)  (0) 2020.03.30
[LeetCode Easy] Remove All Adjacent Duplicates In String (Java)  (0) 2020.03.25
[LeetCode Medium] Sort Colors (Java)  (0) 2019.12.12

Problem


보드판이 주어졌을 때 배틀쉽의 갯수를 구하는 문제입니다.


배틀쉽은 X 로 이루어져 있고 빈 공간은 . 으로 이루어져 있습니다.


배틀쉽은 가로와 세로의 길이 중 하나가 무조건 1 이어야 합니다.


배틀쉽은 서로 딱 붙어있는 경우는 없고 무조건 한 칸 이상 거리를 두어야 합니다.


이 문제는 Example 과 다르게 십자가 모양은 테스트케이스로 주어지지 않습니다.



Solution 1

이 문제의 핵심은 십자가 모양이 주어지지 않는다는 점입니다.


그렇다면 invalid 한 케이스는 없기 때문에 단순하게 배틀쉽 개수만 카운팅 해주면 됩니다.


원래라면 방문체크를 하면서 확인을 했겠찌만 O(1) extra memory 만 사용하라는 조건이 있기 때문에 다른 방법을 생각해야 합니다.


배틀쉽의 첫 X 를 기준으로 카운팅 해줍니다.


만약 board[i][j] 가 X 라고 할 때, board[i-1][j] 나 board[i][j-1] 이 X 라면 이전에 카운팅 했던 배틀쉽이라고 확신할 수 있습니다.


위 조건을 만족하지 않는 경우에만 count++ 해주면 정답을 구할 수 있습니다.



Java Code 1

class Solution {
    public int countBattleships(char[][] board) {
        int n = board.length;
        int m = board[0].length;
        int count = 0;
        
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                if (board[i][j] == 'X') {
                    if (i > 0 && board[i-1][j] == 'X') continue;
                    if (j > 0 && board[i][j-1] == 'X') continue;
                    count++;
                }
            }
        }
        
        return count;
    }
}




Solution 2

만약 십자가 모양도 테스트 케이스로 주어진다고 한다면 모든 케이스를 생각해야합니다.


다음 Follow up 과 같은 제약이 없다면 BFS 를 이용하여 풀 수 있습니다.



Follow up:
Could you do it in one-pass, using only O(1) extra memory and without modifying the value of the board?



보드판 전체를 돌면서 값이 X 인 좌표를 만나면 BFS 를 돌면서 모든 X 를 . 으로 바꿔줍니다.


BFS 를 순회할 때 x, y 좌표가 둘 다 시작점과 다르다면 모양이 십자가 모양이기 때문에 유효하지 않은 배틀쉽입니다.



Java Code 2

class Solution {
    public int countBattleships(char[][] board) {
        int n = board.length;
        int m = board[0].length;
        int count = 0;
        
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                if (board[i][j] == 'X') {
                    count += bfs(i, j, board);
                }
            }
        }
        
        return count;
    }
    
    public int bfs(int x, int y, char[][] board) {
        boolean isBattleShip = true;
        int[] dx = {0, 0, -1, 1};
        int[] dy = {1, -1, 0, 0};
        
        Queue<Dot> q = new LinkedList<>();
        board[x][y] = '.';
        q.add(new Dot(x, y));
        
        while (!q.isEmpty()) {
            Dot dot = q.poll();
            
            if (dot.x != x && dot.y != y) {
                isBattleShip = false;
            }
            
            for (int i=0; i<4; i++) {
                int nx = dot.x + dx[i];
                int ny = dot.y + dy[i];
                
                if (0 <= nx && nx < board.length && 0 <= ny && ny < board[0].length) {
                    if (board[nx][ny] == 'X') {
                        board[nx][ny] = '.';
                        q.add(new Dot(nx, ny));
                    }
                }
            }
        }
        
        return isBattleShip ? 1 : 0;
    }
    
    private class Dot {
        int x, y;
        
        Dot(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}


저작자표시 비영리

'알고리즘 문제 > LeetCode' 카테고리의 다른 글

[LeetCode Easy] Best Time to Buy and Sell Stock II (Java, Kotlin)  (0) 2020.04.05
[LeetCode Easy] Move Zeroes (Java)  (0) 2020.04.04
[LeetCode Easy] Remove All Adjacent Duplicates In String (Java)  (0) 2020.03.25
[LeetCode Medium] Sort Colors (Java)  (0) 2019.12.12
[LeetCode Easy] Reverse Linked List (Java, Kotlin)  (0) 2019.12.12

Problem


난이도 Easy 문제입니다.


문자열이 주어졌을 때 이웃해있는 두 문자가 같은 문자면 제거해야합니다.


만약 제거한 후의 문자열에서 같은 케이스가 발견되면 계속 삭제합니다.


최종적으로 이웃하면서 중복된 문자가 없을때까지 반복해줍니다.



Solution 1

문자열 S 의 길이는 최대 20,000 이기 때문에 O(n) 시간복잡도로 푸는게 좋습니다.


일반적으로 풀면 S 한번 쭉 보면서 중복 제거, 다시 또 한번 보면서 중복 제거.. 이러면 O(n^2) 입니다.


시간을 줄이는 핵심적인 방법은 문자 두개를 제거했을 때


그 자리에 바로 이웃한 중복된 문자가 생기는지 확인하면 됩니다.


removed 배열을 하나 선언하여 문자열이 삭제되었는지 아닌지 체크합니다.


for 문을 돌면서 before 인덱스를 하나 선언한 뒤, 이웃한 두 문자를 삭제


이후 before--; i++; 로 그 다음으로 이웃한 두 문자를 계속 삭제하면 됩니다.



Java Code 1

class Solution {
    public String removeDuplicates(String S) {
        boolean[] removed = new boolean[S.length()];
        
        for (int i = 1; i < S.length(); i++) {
            int before = i-1;
                        
            while (!removed[before] && !removed[i] && S.charAt(before) == S.charAt(i)) {
                removed[before] = true;
                removed[i] = true;
                
                while (before > 0 && removed[before]) {
                    before--;
                }
                
                while (i < S.length()-1 && removed[i]) {
                    i++;
                }
            }
        }
        
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < S.length(); i++) {
            if (!removed[i]) {
                sb.append(S.charAt(i));
            }
        }
        
        return sb.toString();
    }
}




Solution 2

Stack 으로 간단하게 푸는 방법도 있습니다.


for 문 돌면서 stack.peek() 값과 같으면 바로 이전에 있던 문자와 같은 문자이기 때문에 pop() 해줍니다.


만약에 같지않으면 그냥 push() 만 하면 됩니다.



Java Code 2

class Solution {
    public String removeDuplicates(String S) {
        Stack<Character> stack = new Stack<>();
                
        for (char c : S.toCharArray()) {
            if (!stack.isEmpty() && stack.peek() == c) {
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        
        StringBuilder sb = new StringBuilder();
        
        for (char c : stack) {
            sb.append(c);    
        }
        
        return sb.toString();
    }
}

저작자표시 비영리

'알고리즘 문제 > LeetCode' 카테고리의 다른 글

[LeetCode Easy] Move Zeroes (Java)  (0) 2020.04.04
[LeetCode Medium] Battleships in a Board (Java)  (0) 2020.03.30
[LeetCode Medium] Sort Colors (Java)  (0) 2019.12.12
[LeetCode Easy] Reverse Linked List (Java, Kotlin)  (0) 2019.12.12
[LeetCode Easy] Single Number (Java, Kotlin)  (0) 2019.12.11

Problem


난이도 Medium 문제입니다.


빨간색, 파란색, 하얀색이 각각 0, 1, 2 로 주어지고 이 숫자들을 정렬하는 문제입니다.


단, 라이브러리에서 제공하는 정렬 함수를 사용하면 안됩니다.



Solution

문제에서는 Counting Sort 로 O(2n) 만에 풀 수 있다고 언급했습니다.


0, 1, 2 의 갯수를 센 다음에 0, 0, 1, 1, .. 이렇게 주르륵 나열하면 됩니다.


O(n) 시간복잡도와 O(1) 공간복잡도로 문제를 풀려면 문제에 제시된 조건을 파악해야합니다.


이 문제는 단 세가지 숫자 0, 1, 2 만으로 이루어져 있습니다.


포인터 세개를 이용하여 양 끝에 두개의 포인터를 두고 나머지 하나는 증가시키면서 0 과 2를 양끝으로 보내면 됩니다.


0 을 만나면 왼쪽으로, 2를 만나면 오른쪽으로 보내고 1은 신경쓰지 않습니다.


0과 2가 다 보내지고 나면 1은 자동으로 가운데에 남아있게 됩니다.


그리고 증가하던 i 포인터가 right 포인터와 만나면 더이상 swap 할 게 없기 때문에 종료합니다.


포인터의 위치를 신경쓰며 구현만 잘 해주면 풀 수 있습니다.



Java Code

class Solution {
    public void sortColors(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        
        for (int i=0; i<=right; i++) {
            if (nums[i] == 0) {
                swap(nums, i, left++);
            }
            
            if (nums[i] == 2) {
                swap(nums, i--, right--);
            }
        }
    }
    
    public void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}


저작자표시 비영리

'알고리즘 문제 > LeetCode' 카테고리의 다른 글

[LeetCode Medium] Battleships in a Board (Java)  (0) 2020.03.30
[LeetCode Easy] Remove All Adjacent Duplicates In String (Java)  (0) 2020.03.25
[LeetCode Easy] Reverse Linked List (Java, Kotlin)  (0) 2019.12.12
[LeetCode Easy] Single Number (Java, Kotlin)  (0) 2019.12.11
[LeetCode Easy] Maximum Depth Of Binary Tree (Java, Kotlin)  (0) 2019.12.02

+ Recent posts

티스토리툴바