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


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


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


Problem

 

무게추의 갯수와 무게가 주어졌을 때 주어진 무게추들로 만들 수 없는 가장 최소무게를 구하는 문제입니다.



Solution

문제 예시 3 1 6 2 7 30 1 를 정렬하면 1 1 2 3 6 7 30 이 됩니다.

반복문으로 정렬한 숫자들을 하나씩 더해가면서 누적합을 구합니다.

만약 다음 원소값이 누적합 + 1 보다 크다면 누적합 + 1은 만들지 못하는 무게입니다.

처음에는 누적합까지의 무게는 전부 다 만들 수 있다는 전제가 어떻게 만들어진지 이해가 되지 않았습니다.

그런데 직접 해보면서 손으로도 따라해보니 어렴풋이 이해가 됩니다.

누적합 이라고 생각하지 말고 주어진 무게추들로 만들 수 있는 최댓값 이라고 생각하면 됩니다.

 

예를 들어 위 예시에서 1 1 2 까지의 누적합은 4 입니다.

1, 2, 3, 4 까지는 주어진 추 세개 1 1 2 로 전부 만들 수 있습니다.

그리고 여기에 새로운 무게추 3 이 추가된다면 누적합은 7 이 됩니다.

4 까지는 전부 만들수 있다는 걸 이전에 확인을 했고

새로운 5, 6, 7 은 각각 2+3, 3+3, 4+3 이 되고 2, 3, 4 는 1 1 2 의 추로 전부 구할 수 있었고 새로 추가된 3 무게추까지 있다면 5, 6, 7을 만들 수 있습니다.

시간복잡도는 정렬이 있기 때문에 O(n * logn) 이고 공간복잡도는 O(n) 입니다.



Java Code

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

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] weight = new int[n];

        for (int i=0; i<n; i++) {
            weight[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(weight);

        int sum = 0;
        for (int i=0; i<n; i++) {
            if (sum + 1 < weight[i]) {
                break;
            }

            sum += weight[i];
        }

        System.out.println(sum + 1);
    }
}

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

백준 12851번. 숨바꼭질 2 (Java)  (3) 2020.03.29
백준 2293 동전 1 (Java)  (0) 2020.03.28
백준 1912번. 연속합 (Java)  (0) 2019.10.09
백준 5397번. 키로거 (Java)  (0) 2019.09.24
백준 2178번. 미로 탐색 (Java)  (0) 2019.09.22

Problem


연속적인 합 중에서 가장 큰 수를 구하는 문제입니다.




Solution

한 가지만 기억하면 됩니다.


이전까지의 합이 음수면 새로 더하는 값은 무조건 현재보다 작다


예를 들어 [A, B, C, D] 가 입력으로 들어옵니다.


A + B + C 가 음수라면 A + B + C + D 는 무조건 D 보다 작겠죠?


어차피 구해야 하는건 최댓값이기 때문에 이전까지의 합은 음수라면 버리고 D 부터 다시 합을 구해나가면 됩니다.




Java Code

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

class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        int[] numbers = new int[n];

        st = new StringTokenizer(br.readLine());

        for (int i=0; i<n; i++) {
            numbers[i] = Integer.parseInt(st.nextToken());
        }

        int max = numbers[0];
        int sum = 0;
        for (int i=0; i<n; i++) {
            sum += numbers[i];
            max = Math.max(max, sum);
            if (sum < 0) sum = 0;
        }

        System.out.print(max);
    }
}


Problem


문자열이 주어지면 알파벳과 특수문자를 조합해 최종적으로 화면에 입력된 문제를 출력하는 문제입니다.



chardescription
>move right
<move left
-back space


Solution

Stack 두 개를 이용하면 풀 수 있습니다.


스택 두개를 이용하여 현재 위치, 즉 커서를 표현합니다.


커서를 기준으로 두고 preFix 스택은 앞의 문자열, postFix 스택은 뒤의 문자열로 사용하면서 커서를 이동할때마다 스택끼리 값을 옮겨줍니다.


예제 1번을 따라가보겠습니다.






<<BP 까지 입력하면 preFix 스택에 아래 그림과 같이 값이 담길겁니다.


1



이 상태에서 한번 더 < 방향으로 이동을 한다면 P 를 오른쪽 스택으로 옮겨줍니다.

커서의 위치는 두 스택의 사이입니다.

2



위 상태에서 새로운 값 A를 추가한다면 왼쪽 스택에 들어갑니다.

문자열은 preFix + postFix 이기 때문에 현재 문자열은 BAP 입니다.

스택 두개를 기준으로 커서를 사용하기 때문에 문자를 추가하거나 뺄 때 O(1) 의 시간밖에 걸리지 않습니다.

3



위 상태에서 > 입력이 들어오면 P 를 왼쪽으로 이동시켜줍니다.

이동하는 이유와 현재 커서의 위치를 짐작할 수 있을겁니다.

왼쪽 스택이 비어있다면 커서의 위치는 맨 앞, 오른쪽 스택이 비어있다면 커서의 위치는 맨 뒤가 되는겁니다.


4


최종 문자열을 출력할 때는 preFix 에 있는 값을 postFix 로 전부 옮긴 후 출력하면 순서대로 나옵니다.

저는 번거로워서 그냥 Deque 썼습니다.



Java Code

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

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());

        for (int i=0; i<n; i++) {
            String s = br.readLine();
            sb.append(getPassword(s));
            sb.append("\n");
        }

        System.out.println(sb);
    }

    static String getPassword(String input) {
        Deque<Character> preFix = new ArrayDeque<>();
        Deque<Character> postFix = new ArrayDeque<>();
        StringBuilder sb = new StringBuilder();

        for (int i=0; i<input.length(); i++) {
            char c = input.charAt(i);

            switch (c) {
                case '<':
                    if (!preFix.isEmpty()) {
                        postFix.addFirst(preFix.pollLast());
                    }
                    break;
                case '>':
                    if (!postFix.isEmpty()) {
                        preFix.addLast(postFix.pollFirst());
                    }
                    break;
                case '-':
                    if (!preFix.isEmpty()) {
                        preFix.pollLast();
                    }
                    break;
                default:
                    preFix.add(c);
            }
        }

        while (!preFix.isEmpty()) {
            sb.append(preFix.pollFirst());
        }

        while (!postFix.isEmpty()) {
            sb.append(postFix.pollFirst());
        }

        return sb.toString();
    }
}


+ Recent posts