Solve004

Sangkyeong Lee·2021년 5월 19일
ps
0

알고리즘 문제풀이

목록 보기
4/6

문제번호: 7662(이중 우선순위 큐)

풀이

큐를 구성하고 D의 값에 따라 최댓값을 빼거나 최솟값을 빼야하므로 우선순위 큐 보다는 TreeMap을 이용한다. 동일한 값이 삽입될 수 있으므로 카운트해줘야 한다.(getOrDefault 사용)

package Solve004;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class boj_7662 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static TreeMap<Integer, Integer> tr;

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++){
            int m = Integer.parseInt(br.readLine());
            tr = new TreeMap<>();
            for (int j = 0; j < m; j++){
                st = new StringTokenizer(br.readLine());
                String inst = st.nextToken();
                String num = st.nextToken();
                if (inst.equals("I")) {
                    tr.put(Integer.parseInt(num), tr.getOrDefault(Integer.parseInt(num), 0) + 1);
                }
                else {
                    if (tr.isEmpty()) {
                       continue;
                    }
                    if (Integer.parseInt(num) == 1) {
                        if (tr.get(tr.lastKey()) == 1) {
                            tr.remove(tr.lastKey());
                        }
                        else {
                            tr.put(tr.lastKey(), tr.get(tr.lastKey()) - 1);
                        }
                    }
                    else {
                        if (tr.get(tr.firstKey()) == 1){
                            tr.remove(tr.firstKey());
                        }
                        else
                            tr.put(tr.firstKey(), tr.get(tr.firstKey()) - 1);

                    }
                }

            }
            if (tr.isEmpty()) {
                System.out.println("EMPTY");
            }
            else
                System.out.println(tr.lastKey() + " " + tr.firstKey());

        }

    }
}

문제번호: 1753(최단 경로)

풀이

  1. 우선순위 큐와 BFS를 사용
  2. 큐에 들어오는 노드들은 가중치를 기준으로 오름차순으로 정렬된다.
  3. 현재 노드에서 갈 수 있는 가장 작은 가중치를 선택하고 노드들을 돌면서 현재 노드해당 노드까지의 가중치를 업데이트 해준다.
  4. 업데이트 해준 노드들을 지속적으로 큐에 넣어주고 끝까지 돈다.
package Solve004;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class boj_1753 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static ArrayList<node>[] arr;
    static int[] result;
    static boolean[] visited;
    static PriorityQueue<node> qu = new PriorityQueue<>();

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        int v = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());

        arr = new ArrayList[v + 1];
        result = new int[v + 1];
        visited = new boolean[v + 1];

        int start = Integer.parseInt(br.readLine());

        for (int i = 0; i < v + 1; i++) {
            arr[i] = new ArrayList<node>();
            result[i] = Integer.MAX_VALUE;
        }
        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            arr[Integer.parseInt(st.nextToken())].add(new node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }
        solution(v, e, start);
    }

    static void solution(int v, int e, int start) {
        qu.add(new node(start, 0));
        result[start] = 0;
        
        while (!qu.isEmpty()) {
            int current = qu.poll().node;
            if (!visited[current]) {
                visited[current] = true;
            }
            else
                continue;
            for (int i = 0; i < arr[current].size(); i++) {
                if (result[arr[current].get(i).node] > result[current] + arr[current].get(i).weight) {
                    result[arr[current].get(i).node] = result[current] + arr[current].get(i).weight;
                    qu.add(new node(arr[current].get(i).node, result[arr[current].get(i).node]));
                }
            }
        }

        for (int i = 1; i < v + 1; i++) {
            if (result[i] == Integer.MAX_VALUE) {
                System.out.println("INF");
            }
            else
                System.out.println(result[i]);
        }
    }
}

class node implements Comparable<node> {
    int node;
    int weight;

    public node(int node, int weight) {
        this.node = node;
        this.weight = weight;
    }

    public int compareTo(node n) {
        return weight - n.weight;
    }
}

문제번호: 11053(가장 긴 증가하는 부분 수열)

풀이

항상 첫번째 입력값은 시작값이므로 두번째 값부터 기준으로 삼아 해당 값 앞에 있는 인덱스들과 비교를 한다.
만약 앞에 값이 작으면 기준값은 증가하는 값이므로 cnt를 올려줘야 하는데 여기에서 무작정 작다고 올려주면 증가하는 이라는 조건을 충족시킬 수가 없다.
따라서 인덱스마다 몇번째 증가하는 값인지 따로 설정을 해줘야 한다.

package Solve004;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class boj_11053 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int[] input;
    static int[] result;

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        input = new int[n];
        result = new int[n];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) {
            input[i] = Integer.parseInt(st.nextToken());
        }
        System.out.println(solution());
    }

    static int solution() {

        result[0] = 1;
        for (int i = 1; i < input.length; i++) {
            result[i] = 1;
            for (int j = 0; j < i; j++) {
                if (input[j] < input[i] && result[i] <= result[j]) {
                    result[i] = result[j] + 1;
                }
            }
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < input.length; i++) {
            if (max < result[i]) {
                max = result[i];
            }
        }
        return max;
    }
}

문제번호: 2407(조합)

풀이

단순 수학 문제다.
BigInteger를 사용해야 한다.

package Solve004;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class boj_2407 {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        BigInteger up = BigInteger.ONE;
        BigInteger down = BigInteger.ONE;
        BigInteger div = BigInteger.valueOf(m);

        for (int i = n; i > n - m; i--) {
            up = up.multiply(BigInteger.valueOf(i));
            down = down.multiply(div);
            div = div.subtract(BigInteger.ONE);
        }

        BigInteger result = up.divide(down);
        System.out.println(result);
    }
}

문제번호: 9465(스티커)

풀이

두줄밖에 없으므로 첫번째줄의 최댓값, 두번째줄의 최댓값을 이용해서 끝까지 갱신해가면서 구하기로하자.
1. 1열의 첫번째 값은 0열의 두번째값을 더한다.
2. 1열의 두번째 값은 0열의 첫번째값과 더한다.
3. 2열부터는 1열까지 존재하는 첫번째줄 가장 큰값을 더한다.

  • 일반화
    n열의 첫번째 값은 n-1열까지의 두번째줄의 값 중에 가장 큰값을 더한다.
    n열의 두번째 값은 n-1열까지의 첫번째줄의 값 중에 가장 큰값을 더한다.
package Solve004;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class boj_9465 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int[][] arr;
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        int t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());

            arr = new int[2][n];

            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < n; j++) {
                arr[0][j] = Integer.parseInt(st.nextToken());
            }

            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < n; j++) {
                arr[1][j] = Integer.parseInt(st.nextToken());
            }

            System.out.println(solution(n));
        }
    }

    static int solution(int length) {
        int firstMax = arr[0][0];
        int secondMax = arr[1][0];
        for (int i = 1; i < length; i++) {
            int nextFirstValue = arr[0][i] + secondMax;
            arr[0][i] += secondMax;

            int nextSecondValue = arr[1][i] + firstMax;
            arr[1][i] += firstMax;

            if (firstMax < nextFirstValue) {
                firstMax = nextFirstValue;
            }

            if (secondMax < nextSecondValue) {
                secondMax = nextSecondValue;
            }
        }

        int max = Integer.MIN_VALUE;
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < length; j++) {
                if (arr[i][j] > max) {
                    max = arr[i][j];
                }
            }
        }
        return max;
    }
}

문제번호: 11725(트리의 부모 찾기)

풀이

어떻게 부모를 알 수 있을까 고민을 많이 했는데 루트 노드부터 연결되어 있는 노드를 찾아가면 부모를 알 수 있다는 것을 깨달았다. 루트 노드를 시작으로 탐색해보자.
1. ArrayList배열을 사용해서 각각의 노드의 숫자를 인덱스 삼아 해당 인덱스 ArrayList에 연결되어 있는 노드를 다 넣는다.
2. 큐를 만들고 루트 노드를 start노드로 정하고 탐색 시작
3. 중복되지 않기 위해 방문한 노드를 판별하고 해당 노드의 ArrayList를 탐색할때 해당 노드가 ArrayList안의 있는 노드들의 부모 노드가 된다.

package Solve004;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// 1부터 탐색
public class boj_11725 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static ArrayList<Integer>[] arr;
    static int[] result;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());

        arr = new ArrayList[n + 1];
        result = new int[n + 1];
        visited = new boolean[n + 1];

        for (int i = 0; i < n + 1; i++) {
            arr[i] = new ArrayList<>();
        }

        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            arr[x].add(y);
            arr[y].add(x);
        }

        solution(1);
    }

    static void solution(int start) {
        Queue<Integer> qu = new LinkedList<>();
        qu.add(start);
        result[start] = 0;
        visited[start] = true;

        while (!qu.isEmpty()) {
            int x = qu.poll();
            for (int i = 0; i < arr[x].size(); i++) {
                int node = arr[x].get(i);
                if (!visited[node]) {
                    result[node] = x;
                    qu.add(node);
                    visited[node] = true;
                }
            }

        }

        for (int i = 2; i < result.length; i++) {
            System.out.println(result[i]);
        }
    }
}

문제번호: 16953(A → B)

풀이

앞 숫자에서 뒤의 숫자로 가는 경우의 수가 너무 많아서 생각을 해봤다. 그러다가 뒤에서 앞으로 가는 경우를 따져보았는데 짝수면 무조건 나누고 일의 자리가 1이라면 1을 빼게되면 최소 경우의 수로 갈 수 있는 것을 알았다.
1. 앞의 숫자를 from 뒤의 숫자를 to라고 하겠다.
2. (예외)to의 일의 자리 수가 1이 아니고 홀수라면 무조건 from으로 도달할 수 없다.
3. to가 from보다 작아질때까지 반복문을 돌면서 만약 to의 길이(문자열로 바꾼후 길이를 받아옴)가 1이 됐는데 홀수인 경우 도달할 수 없다.
1. to가 짝수라면 계속 2로 나눈다.
2. to의 일의 자리가 1이 아니고 홀수라면 더이상 진행 불가하므로 -1을 Return
4. 반복문의 끝에 from과 to를 비교해서 같다면 cnt + 1반환

배운점

String은 불변이므로 StringBuilder로 변환후에 deleteCharAt(index)를 사용하면 문자열에서 문자를 지울 수 있다.
String을 바꿀 경우는 String x = x.(old, new)를 사용
숫자를 문자열로 바꿀때: Integer.toString(int i) 통일
문자열을 숫자로 바꿀때: Integer.parseInt(string) 통일

package Solve004;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class boj_16953 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int cnt = 0;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine(), " ");
        int from = Integer.parseInt(st.nextToken());
        int to = Integer.parseInt(st.nextToken());

        System.out.println(solution(from, to));

    }

    static int solution(int from, int to) {
        String toToString = Integer.toString(to);

        StringBuilder stb = new StringBuilder(toToString);
        int length = stb.length();

        if (toToString.charAt(toToString.length() - 1) != '1' && to % 2 == 1) {
            return -1;
        }

        while (from < to) {
            if (to % 2 == 0) {
                to /= 2;
            }
            else {
                if (stb.length() == 1) {
                    return -1;
                }
                else if (stb.charAt(length - 1) != '1') {
                    return -1;
                }

                stb.deleteCharAt(length - 1);
                to = Integer.parseInt(stb.toString());
            }
            cnt++;

            toToString = toToString.replace(toToString, Integer.toString(to));
            stb = new StringBuilder(toToString);
            length = stb.length();

            if (from == to) {
                return cnt + 1;
            }
        }

        return -1;
    }
}

문제번호: 11660(구간 합 구하기 5)

오답풀이

  • 시간초과
package Solve004;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class boj_11660 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int[][] arr;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        arr = new int[n][n];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int x1 = 0;
        int y1 = 0;
        int x2 = 0;
        int y2 = 0;

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine(), " ");

            x1 = Integer.parseInt(st.nextToken());
            y1 = Integer.parseInt(st.nextToken());
            x2 = Integer.parseInt(st.nextToken());
            y2 = Integer.parseInt(st.nextToken());

            System.out.println(solution(x1, y1, x2, y2));
        }
    }

    static int solution(int x1, int y1, int x2, int y2) {
        int result = 0;

        for (int i = x1 - 1; i <= x2 - 1; i++) {
            for (int j = y1 - 1; j <= y2 - 1; j++) {
                result += arr[i][j];
            }
        }
        return result;
    }

}

풀이

매우매우 개고생을 했다.
DP를 이용해서 풀자.
N * N 배열하나 더 만들어서 해당 좌표까지의 합을 저장한다.

  1. 모든 행의 1열부터 같은 행에 있는 이전 열의 값을 더하면서 N까지 반복한다. (편하게 하기 위해 0행, 0열을 0으로 채웠다.)
  2. 이제 1행부터 같은 열에 있는 이전 행의 값을 더하면서 N까지 반복한다.
  3. 이렇게 되면 해당 좌표값은 문제에서 제시한 것처럼 만약 (2, 2)라면 (0, 1), (0, 2), (1, 1), (1, 2), (2, 1), (2, 2)의 값들을 모두 더한 배열이 완성된다.
  4. 문제에서 제시한 예시중에 (2, 2) (3, 4)가 있는데 (3, 4)좌표와 (2, 2) 좌표를 적절히 섞어서 어떻게 하면 답을 산출할 수 있을까 생각을 해봤다.
  5. (3, 4)에서 x는 3이고 (2, 2)의 y값 2이므로 (3, 1)의 좌표 값을 빼면 일단 한쪽의 값을 제거할 수 있다.
  6. (2, 2)에서 x는 2이고 (3, 4)에서 y값이 4이므로 (1, 4)의 좌표 값을 빼면 남은 한쪽의 값도 제거할 수 있다.
  7. 여기서 (1, 1)의 값이 두번 빼지게 된다. 이 부분은 작은 좌표 (2, 2)에서 x,y를 1씩빼고 (1, 1)을 한번 더해주면 해결된다.
package Solve004;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class boj_11660 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int[][] arr;
    static int[][] sumArr;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        arr = new int[n + 1][n + 1];
        sumArr = new int[n + 1][n + 1];

        int temp = 0;

        for (int i = 1; i < n + 1; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 1; j < n + 1; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                sumArr[i][j] = temp + arr[i][j];
                temp = sumArr[i][j];
            }
            temp = 0;
        }

        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                sumArr[i][j] += sumArr[i - 1][j];
            }
        }

        int x1 = 0;
        int y1 = 0;
        int x2 = 0;
        int y2 = 0;

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine(), " ");

            x1 = Integer.parseInt(st.nextToken());
            y1 = Integer.parseInt(st.nextToken());
            x2 = Integer.parseInt(st.nextToken());
            y2 = Integer.parseInt(st.nextToken());

            System.out.println(solution(x1, y1, x2, y2));
        }
    }

    static int solution(int x1, int y1, int x2, int y2) {
        int result = 0;

        if (x1 == x2 && y1 == y2) {
            result = arr[x1][y1];
        }
        else {
            result = sumArr[x2][y2] - sumArr[x2][y1 - 1] - sumArr[x1 - 1][y2] + sumArr[x1 - 1][y1 - 1];
        }

        return result;
    }

}
profile
Sangkyeong Lee
💻Backend Developer
이전 포스트

Solve003

다음 포스트

Solve005

0개의 댓글