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


괄호가 균형을 제대로 이루는지 확인하는 문제입니다.




Solution

간단한 짝 맞추는 문제입니다.


문제 조건이 복잡해 보이지만 결론은 여는 괄호와 닫는 괄호의 쌍이 일치하는 지 확인하라는 문제입니다.


Stack 자료구조를 이용해서 풀 수도 있고, 간단히 char[] 배열과 cursor 를 이용하여 해결 할 수도 있습니다.


여는 괄호가 들어오면 스택에 넣어두고, 닫는 괄호를 만나면 스택에서 하나 꺼냅니다.


스택에서 꺼낸 여는 괄호와 짝이 맞다면 계속해서 진행하고, 스택이 비어있거나 짝이 맞지 않으면 중지합니다.


속도는 배열을 쓴게 더 빠릅니다.




Java Code 1

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        while (true) {
            String input = br.readLine();

            if (input.equals(".")) {
                bw.flush();
                return;
            }

            bw.write(isBalanced(input));
        }
    }

    // use Stack
    static String isBalanced(String s) {
        Stack<Character> stack = new Stack<>();
        boolean result = true;

        for (char one : s.toCharArray()) {
            if (one == '(' || one == '[') {
                stack.push(one);
            } else if (one == ')') {
                if (stack.isEmpty() || stack.pop() != '(') {
                    result = false;
                    break;
                }
            } else if (one == ']') {
                if (stack.isEmpty() || stack.pop() != '[') {
                    result = false;
                    break;
                }
            }
        }

        if (!stack.isEmpty()) {
            result = false;
        }

        return result ? "yes\n" : "no\n";
    }
}




Java Code 2

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        while (true) {
            String input = br.readLine();

            if (input.equals(".")) {
                bw.flush();
                return;
            }

            bw.write(isBalanced(input));
        }
    }

    // use char[] array and cursor
    static String isBalanced(String s) {
        char[] stack = new char[s.length()];
        int cursor = 0;
        boolean result = true;

        for (char one : s.toCharArray()) {
            switch (one) {
                case '(':
                case '[':
                    stack[cursor++] = one;
                    break;
                case ')':
                    if (cursor == 0 || stack[--cursor] != '(') {
                        return "no\n";
                    }
                    break;
                case ']':
                    if (cursor == 0 || stack[--cursor] != '[') {
                        return "no\n";
                    }
                    break;
            }
        }

        if (cursor > 0) {
            result = false;
        }

        return result ? "yes\n" : "no\n";
    }
}


저작자표시 비영리

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

백준 14954번. Happy Number (Java)  (0) 2020.04.03
백준 13913번. 숨바꼭질 4 (Java)  (1) 2020.03.30
백준 12851번. 숨바꼭질 2 (Java)  (3) 2020.03.29
백준 2293 동전 1 (Java)  (0) 2020.03.28
백준 2437번. 저울 (Java)  (2) 2020.03.17

Problem


숫자가 주어지면 (각 자리수)^2 의 합이 최종적으로 1 이 되는지 아닌지 판단하는 문제입니다.




Solution

n == 1 이 되지 않는 경우는 무한 반복하는 경우입니다.


무한 반복한다는건 싸이클을 형성한다는 뜻이고 싸이클을 찾는지만 확인하면 됩니다.


Floyd's Cycle Detection Algorithm 을 이용하여 싸이클을 찾을 수 있습니다.




Java Code

import java.io.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        System.out.print(isHappy(n) ? "HAPPY" : "UNHAPPY");
    }

    static boolean isHappy(int n) {
        int slow = getDigitSum(n);
        int fast = getDigitSum(getDigitSum(n));
                               
        while (fast != 1 && slow != 1) {
            if (fast == slow) {
                return false;
            }
            
            slow = getDigitSum(slow);
            fast = getDigitSum(getDigitSum(fast));
        }

        return true;
    }
    
    static int getDigitSum(int number) {
        int sum = 0;
        
        while (number != 0) {
            sum += (number % 10) * (number % 10);
            number /= 10;
        }
        
        return sum;
    }   
}


저작자표시 비영리

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

백준 4949번. 균형잡힌 세상 (Java)  (0) 2020.04.03
백준 13913번. 숨바꼭질 4 (Java)  (1) 2020.03.30
백준 12851번. 숨바꼭질 2 (Java)  (3) 2020.03.29
백준 2293 동전 1 (Java)  (0) 2020.03.28
백준 2437번. 저울 (Java)  (2) 2020.03.17

Problem


수빈이는 동생이랑 숨바꼭질을 하고 있습니다.


수빈이는 N 에서 시작하고 동생은 K 에 있습니다.


수빈이는 1초에 +1, -1, *2 위치로 순간이동이 가능합니다.


수빈이가 동생을 찾는 가장 빠른 시간과 이동 경로 를 구하는 문제입니다.



Solution

가장 빠른 시간은 BFS 를 이용해서 구합니다.


time 배열에 각 위치에 도달 했을 때의 시간을 저장하면 됩니다.


한번 방문한 곳은 또 방문할 필요가 없습니다.



이동 경로는 parent 배열을 사용합니다.


현재 위치 A 에서 다음 경로로 가는 방법은 3개여서 저장하기가 애매합니다.


그런데 현재 위치 A 로 이동했던 출발지는 1개입니다.


따라서 parent 배열에는 이전 경로를 저장한 뒤, 최종 도착지인 K 부터 N 까지 다시 거슬러 올라가면 됩니다.



변수설명
time[location]location 에 도달했을 때 시간
parent[location]location 으로 이동하기 직전 위치


Java Code

import java.util.*;
import java.io.*;

class Main {
    static int N, K;
    static int[] parent = new int[100001];
    static int[] time = new int[100001];

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        bfs();

        // 순서대로 구하기 위해 stack 에 담았다가 다시 pop
        Stack<Integer> stack = new Stack<>();
        stack.push(K);
        int index = K;

        while (index != N) {
            stack.push(parent[index]);
            index = parent[index];
        }

        // 최종 출력
        sb.append(time[K] - 1 + "\n");
        while (!stack.isEmpty()) {
            sb.append(stack.pop() + " ");
        }

        System.out.println(sb.toString());
    }

    static void bfs() {
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(N);
        time[N] = 1;

        while (!q.isEmpty()) {
            int now = q.poll();

            if (now == K) return;
            
            for (int i=0; i<3; i++) {
                int next;

                if (i == 0)         next = now + 1;
                else if (i == 1)    next = now - 1;
                else                next = now * 2;

                if (next < 0 || next > 100000) continue;

                if (time[next] == 0) {
                    q.add(next);
                    time[next] = time[now] + 1;
                    parent[next] = now;
                }
            }
        }
    }
}


저작자표시 비영리

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

백준 4949번. 균형잡힌 세상 (Java)  (0) 2020.04.03
백준 14954번. Happy Number (Java)  (0) 2020.04.03
백준 12851번. 숨바꼭질 2 (Java)  (3) 2020.03.29
백준 2293 동전 1 (Java)  (0) 2020.03.28
백준 2437번. 저울 (Java)  (2) 2020.03.17

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


수빈이는 동생이랑 숨바꼭질을 하고 있습니다.

수빈이는 N 에서 시작하고 동생은 K 에 있습니다.

수빈이는 1초에 +1, -1, *2 위치로 순간이동이 가능합니다.

수빈이가 동생을 찾는 가장 빠른 시간과 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 문제입니다.



Solution

백준 1697번 숨바꼭질 문제의 진화형입니다.

최단 시간을 구하라는 점은 똑같지만, 이번에는 최단 시간에 만나는 모든 경우를 구해야 합니다.

그래서 푸는 방법이 조금 다릅니다.


1. BFS 를 종료 기준을 시간으로 탐색

BFS에는 시간이 0 부터 차례대로 쌓입니다.

만약 수빈이가 동생을 2 초에 만났고, BFS 탐색이 3 초를 넘어가면 이미 최단 시간이 아니기 때문에 그 이후는 더 볼 필요가 없습니다.


2. 중복 방문의 허용

수빈이가 최단 시간에 동생을 만나는 방법은 여러 가지가 있을 수 있습니다.

예를 들어 입력으로 1 4 가 주어졌다고 합니다.

그러면 수빈이가 동생을 만나는 최단 루트는 *2, *2 로 1 2 4 입니다.

하지만 +1, *2 로 움직이면 똑같이 1 2 4 루트로 동생을 만날 수 있습니다.

만약 위치 2에서의 중복 방문을 허용하지 않는다면 확인 할 수 없습니다.


3. 그러나 모든 중복을 허용하지 않기

똑같은 위치에 다시 방문했을 때 세가지 경우를 생각해봐야 합니다.


3.1. 이전 방문 시간과 현재 방문 시간이 일치할 때

time[next] == time[now] + 1 인 경우입니다.

동일한 시간에 도착했다면 최종 목적지에 도달하는 시간도 동일할 가능성이 있기 때문에 Queue 에 넣어줍니다.


3.2. 이전 방문 시간이 현재 방문 시간보다 빠른 경우

time[next] < time[now] + 1 인 경우입니다.

현재 방문 시간이 더 느리기 때문에 목적지에 최단 시간으로 도달할 가능성이 없습니다.

제외해줍니다.


3.3. 이전 방문 시간이 현재 방문 시간보다 늦은 경우

time[next] > time[now] + 1 인 경우입니다.

현재 시간이 더 빠르기 때문에 Queue 에 넣어줍니다.

그러나 사실 발생하지 않는 케이스입니다.

BFS 는 시간 순서로 진행되고 있습니다.

1 초에 도달하는 곳을 모두 확인하고 2 초에 도달할 수 있는 곳을 모두 확인하고.. 3초에..

따라서 이전에 방문한 곳이 현재 시간보다 클 가능성은 없습니다.

실제 로직에 영향을 주진 않으므로 Queue 에 넣는 조건으로 사용해도 괜찮습니다.


방금 예시로 든 1 2 4 를 다시 생각해봅니다.

두 경우 다 1초에 2로 이동하기 때문에 중복 방문을 해도 괜찮습니다.

하지만 만약 2에 방문하는 시간이 2초, 3초로 다를 경우, 더 늦은 3초는 볼 필요가 없기 때문에 방문을 허용하지 않습니다.



Java Code

import java.util.*;
import java.io.*;

class Main {
    static int N, K;
    static int[] time = new int[100001];
    static int minTime = 987654321;
    static int count = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        if (N >= K) {
            System.out.println((N-K) + "\n1");
            return;
        }

        bfs();

        System.out.println(minTime + "\n" + count);
    }

    static void bfs() {
        Queue<Integer> q = new LinkedList<Integer>();

        q.add(N);
        time[N] = 1;

        while (!q.isEmpty()) {
            int now = q.poll();

            // now 방문 시간이 최소 시간보다 크면 뒤는 더 볼 필요 없음
            if (minTime < time[now]) return;

            for (int i=0; i<3; i++) {
                int next;

                if (i == 0)         next = now + 1;
                else if (i == 1)    next = now - 1;
                else                next = now * 2;

                if (next < 0 || next > 100000) continue;

                if (next == K) {
                    minTime = time[now];
                    count++;
                }

                // 첫 방문이거나 (time[next] == 0)
                // 이미 방문한 곳이어도 같은 시간에 방문했다면 (time[next] == time[now] + 1)
                // 경우의 수에 추가될 수 있기 때문에 Queue 에 한번 더 넣어줌
                if (time[next] == 0 || time[next] == time[now] + 1) {
                    q.add(next);
                    time[next] = time[now] + 1;
                }
            }
        }
    }
}
저작자표시 비영리

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

백준 14954번. Happy Number (Java)  (0) 2020.04.03
백준 13913번. 숨바꼭질 4 (Java)  (1) 2020.03.30
백준 2293 동전 1 (Java)  (0) 2020.03.28
백준 2437번. 저울 (Java)  (2) 2020.03.17
백준 1912번. 연속합 (Java)  (0) 2019.10.09

Problem


동전의 갯수와 가치가 주어졌을 때 동전의 합이 K 를 이루는 모든 경우의 수를 구하는 문제입니다.




Solution

dp 문제입니다.


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


dp[j] += dp[j - coin[i]]; 식은 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

import java.util.*;
import java.io.*;

class Main {	
	public static void main(String args[]) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        	StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int[] coin  = new int[n];
		int[] dp = new int[k+1];
		
		for(int i=0; i<n; i++) {
			coin[i] = Integer.parseInt(br.readLine());
		}

        	dp[0] = 1;
		
		for(int i = 0; i < n; i++) {
			for(int j = coin[i]; j <= k; j++) { 
				dp[j] += dp[j - coin[i]];
			}
		}
		
		System.out.println(dp[k]);
	}
}


저작자표시 비영리

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

백준 13913번. 숨바꼭질 4 (Java)  (1) 2020.03.30
백준 12851번. 숨바꼭질 2 (Java)  (3) 2020.03.29
백준 2437번. 저울 (Java)  (2) 2020.03.17
백준 1912번. 연속합 (Java)  (0) 2019.10.09
백준 5397번. 키로거 (Java)  (0) 2019.09.24

+ Recent posts

티스토리툴바