이것저것 개발 블로그

https://www.acmicpc.net/problem/2751

풀이)

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main_BJ_2751_수정렬하기2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        int n = sc.nextInt();
        ArrayList<Integer> arr = new ArrayList<>();
        for(int i=0; i<n; i++)
            arr.add(sc.nextInt());
        Collections.sort(arr);

        for(int i=0; i<n; i++){
            if(i == 0)
                sb.append(arr.get(i) + "\n");
            else if(arr.get(i-1) != arr.get(i))
                sb.append(arr.get(i) + "\n");
        }
        System.out.println(sb);
    }
}

Arrays.sort는 퀵소트, Collections.sort는 타임소트라는 것을 처음 알게 해준 문제여따...

항상 참고하기 좋은 블로그...

https://st-lab.tistory.com/106

https://www.acmicpc.net/problem/2407

풀이)

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

public class Main_BJ_2407_조합 {
    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 m = Integer.parseInt(st.nextToken());

        BigInteger sum = BigInteger.ONE;
        BigInteger div = BigInteger.ONE;

        for(int i=0; i<m; i++){
            sum = sum.multiply(new BigInteger(String.valueOf(n-i)));
            div = div.multiply(new BigInteger(String.valueOf(i+1)));
        }

        BigInteger ans = sum.divide(div);
        System.out.println(ans);
    }//main
}

단순히 BigInteger만 쓰면 해결되는 문제였다.

BigInteger에서 .ONE을 사용하는 경우를 알게된 경험이었다.

조합은 간단하게 nCr = n! / (n-r)! * r!을 이용하면 된다.

코드에 적용하면 n부터 거꾸로 m의 개수까지 곱한 것을 r!로 나누면 된다는 의미!

https://www.acmicpc.net/problem/13549

풀이)

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main_BJ_13549_숨바꼭질3 {
    static int MAX = 100000;
    static boolean[] visited = new boolean[MAX+1];
    static class location{
        int x;
        int cnt;

        public location(int x, int cnt){
            this.x = x;
            this.cnt = cnt;
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        PriorityQueue<location> pq = new PriorityQueue<>(new Comparator<location>() {
            @Override
            public int compare(location o1, location o2) {
                return o1.cnt - o2.cnt;
            }
        });
        visited[n] = true;
        pq.offer(new location(n, 0));
        int min = Integer.MAX_VALUE;

        while(!pq.isEmpty()){
            location cur = pq.poll();
            visited[cur.x] = true;

            if(cur.x == m){
                min = Math.min(min, cur.cnt);
            }

            if(cur.x-1 >= 0 && !visited[cur.x-1])
                pq.offer(new location(cur.x-1, cur.cnt+1));

            if(cur.x+1 <= MAX && !visited[cur.x+1])
                pq.offer(new location(cur.x + 1, cur.cnt + 1));

            if(cur.x * 2 <= MAX && !visited[cur.x * 2])
                pq.offer(new location(2 * cur.x, cur.cnt));

        }//while

        System.out.println(min);
    }//main
}

이 문제는 Priority Queue + BFS로 풀 수 있는 문제였다!

처음에는 pq에 comparator로 Math.abs(현재 좌표 - 목표 좌표)로 해서 가까운 순으로 체크하려 했는데, 이러면 안됐고,,,

대신 pq에 시간 기준으로 가장 적은 순으로 넣으면 된다.

대신 pq에 삽입할 때 범위를 체크한 후 삽입해야한다.

또한, bfs로 visited를 체크할 때 pq에서 뽑았을 때 해야한다는 주의점이 있다. (pq에 넣을 때 순서 의존도가 생기기 때문에..)

pq, bfs까지도 잡았는데 visited에서 잘 생각하지 못한 부분이 아쉽다.

https://www.acmicpc.net/problem/15657

풀이)

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

public class Main_BJ_15657_N과M8 {

    static int n, m;
    static int[] arr;
    static int[] ans;
    static boolean[] visited;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

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

        Arrays.sort(arr);
        visited = new boolean[n];
        ans = new int[m];
        perm(0, 0);
    }
    private static void perm(int index, int cnt){
        if(cnt == m){
            for(int i=0; i<m; i++)
                System.out.print(ans[i] + " ");
            System.out.println();
            return;
        }

        for(int i=index; i<n; i++){
            ans[cnt] = arr[i];
            perm(i, cnt+1);
        }
    }//perm
}

전의 문제와 딱히 달라질 것은 없는 문제였다.

다음으로 넘길 때 i를 넘겨야 한다는 점만 잊지 말기!

https://www.acmicpc.net/problem/14938

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main_BJ_14938_서강그라운드 {
    static int[] item;
    static ArrayList<Node>[] adj;
    static int n, m, r, max;
    static int[][] dijkstra;
    static class Node{
        int to;
        int w;

        public Node(int to, int w) {
            this.to = to;
            this.w = w;
        }
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken()); // 지역 개수
        m = Integer.parseInt(st.nextToken()); // 수색 범위
        r = Integer.parseInt(st.nextToken()); // 길의 개수

        item = new int[n+1];
        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=n; i++)
            item[i] = Integer.parseInt(st.nextToken());

        adj = new ArrayList[n+1];
        for(int i=1; i<=n; i++)
            adj[i] = new ArrayList<Node>();

        for(int i=0; i<r; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            adj[a].add(new Node(b, w));
            adj[b].add(new Node(a, w));
        }

        dijkstra = new int[n+1][n+1];
        for(int i=1; i<=n; i++)
            Dijkstra(i);

        System.out.println(max);
    }//main
    private static void Dijkstra(int start){
        PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.w - o2.w;
            }
        });
        int[] dist = new int[n+1];

        for(int i=1; i<=n; i++)
            dist[i] = Integer.MAX_VALUE;
        pq.offer(new Node(start, 0));
        dist[start] = 0;

        while(!pq.isEmpty()){
            Node cur = pq.poll();

            if(dist[cur.to] < cur.w)
                continue;

            for(int i=0; i<adj[cur.to].size(); i++){
                Node next = adj[cur.to].get(i);

                if(dist[next.to] > cur.w + next.w){
                    dist[next.to] = cur.w + next.w;
                    pq.offer(new Node(next.to, dist[next.to]));
                }
            }
        }//while

        int sum = 0;
        for(int i=1; i<=n; i++){
            if(m >= dist[i])
                sum += item[i];
        }
        max = Math.max(sum, max);
    }//dijkstra
}

다익스트라를 이용해서 각 노드에서 모든 노드로의 최소 거리를 구한다.

그리고 최대 탐색할 수 있는 거리보다 작거나 같다면 item을 더해주면 된다!!

간단하다고 할 수 있는데 다익스트라 때문에 잘 못푼문제ㅠ

https://www.acmicpc.net/problem/15654

풀이)

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

public class Main_BJ_15654_N과M5 {
    static int n, m;
    static int[] arr, ans;
    static boolean[] visited;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = new int[n];
        ans = new int[m];
        visited = new boolean[n];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);

        perm(0);
    }//main
    private static void perm(int cnt){
        if(cnt == m){
            for(int i=0; i<m; i++){
                System.out.print(ans[i]+ " ");
            }
            System.out.println();
            return;
        }


        for(int i=0; i<n; i++){
            if(visited[i])
                continue;

            visited[i] = true;
            ans[cnt] = arr[i];
            perm(cnt+1);
            visited[i] = false;
        }
    }//perm
}

다시 찾아온 N과 M 시리즈~~

이번에도 순열인데, 대신 처음 수를 정렬을 해야했다.

따라서 입력 받은 수들을 따로 받고, 이를 정렬해줬다.

하지만, 방문처리한 순서대로 출력해버리면 무조건 작은 수부터 출력이 되기 때문에 중복이 생겨버린다!

따라서 선택한 순열을 따로 받을 배열을 받아서 저장해두고 출력!

https://www.acmicpc.net/problem/15652

풀이)

import java.util.Scanner;

public class Main_BJ_15652_N과M4 {
    static int n, m;
    static int[] arr;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        arr = new int[m];

        perm(0, 0);
    }//main
    private static void perm(int cnt, int index){
        if(cnt == m){
            for(int i=0; i<m; i++)
                System.out.print(arr[i]+" ");
            System.out.println();
            return;
        }

        for(int i=index; i<n; i++){
            arr[cnt] = i+1;
            perm(cnt+1, i);
        }
    }//perm
}

이번에는 중복 순열 문제! 단, 비내림차순으로 정렬해야한다.

순열로 푸는 문제와 거의 동일하다.

이때, 차이점은 visited 배열이 필요 없는 대신, 수열을 저장할 배열을 선언해야한다.

또한, 재귀 호출할때 현재 위치를 보내줘야 한다는점!

안 그러면 비내림차순이 되지 않는다.

https://www.acmicpc.net/problem/5639

풀이)

풀이1

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main_BJ_5639_이진검색트리 {
    static class Node{
        int num;
        Node left, right;

        public Node(int num) {
            this.num = num;
        }

        public Node(int num, Node left, Node right) {
            this.num = num;
            this.left = left;
            this.right = right;
        }

        void insert(int n){
            if(n < this.num){
                if(this.left == null)
                    this.left = new Node(n);
                else this.left.insert(n);
            }
            else{
                if(this.right == null)
                    this.right = new Node(n);
                else this.right.insert(n);
            }
        }//insert
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Node root = new Node(Integer.parseInt(br.readLine()));
        while(true){
            String str = br.readLine();
            if(str == null || str.equals(""))
                break;
            int node = Integer.parseInt(str);
            root.insert(node);
        }
        postorder(root);
    }//main

    private static void postorder(Node node){
        if(node == null)
            return;

        postorder(node.left);
        postorder(node.right);
        System.out.println(node.num);
    }//postorder
}

첫 번째는 Node 클래스를 선언해서 순서대로 담고, postorder 순으로 출력하기!!

가장 흔히 생각할 수 있는 방법이다.

풀이2)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main_BJ_5639_이진검색트리2 {
    static ArrayList<Integer> tree;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        tree = new ArrayList<>();
        while(true){
            String str = br.readLine();
            if(str == null || str.equals(""))
                break;

            tree.add(Integer.parseInt(str));
        }
        postorder(0, tree.size()-1);
    }//main
    private static void postorder(int index, int end){
        if(index > end)
            return;

        int mid = index+1;
        while(mid<=end && tree.get(mid) < tree.get(index))
            mid++;
        postorder(index+1, mid-1);
        postorder(mid, end);
        System.out.println(tree.get(index));
    }//postorder
}
/*
50
30
24
5
28
45
98
52
60

index: 0  end: 8  mid: 6
index: 1  end: 5  mid: 5 (left)
index: 2  end: 4  mid: 4 (left)
index: 3  end: 3  mid: 4 (left)
index: 4  end: 3 (left)
index: 4  end: 3 (right)
print tree(index) = 5
index: 4  end: 4  mid: 5 (right)
index: 5  end: 4 (left)
index: 5  end: 4 (right)
print tree(index) = 28
print tree(index) = 24
index: 6  end: 5 (left)
print tree(index) = 45
...
 */

ArrayList 또는 배열에 차례대로 담고, subtree를 구분하기 위해 중간 지점을 찾아가며 postorder 순으로 출력!

왼쪽 subtree, 오른쪽 subtree 순으로 찾고, 본인을 출력하면 된다.

• 깨달은 점
  
  • 입력이 어느정도인지 정해지지 않은 경우 null이나 ""과 같을 경우를 사용하면 된다.
  • Scanner는 hasNext()를 사용하면 된다
• 잘 못했던 점
  • 트리를 탐색할 때 중간 지점을 찾아 subtree를 재귀로 탐색하는 방법 -> 헷갈려서 일일히 디버깅하면서 쳐봄..ㅠ

막상 풀어보니 별거 아닌것 같은데 헷갈렸던 문제였다.

다시 풀어봐야지!

참고한 블로그

https://girawhale.tistory.com/59

https://www.acmicpc.net/problem/15650

 
 
 
풀이)

import java.util.Scanner;

public class Main_BJ_15650_N과M2 {
    static int n;
    static boolean[] visited;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int m = sc.nextInt();
        visited = new boolean[n];

        permutation(0, 0, m);
    }//main
    private static void permutation(int cnt, int cur, int m){
        if(cnt == m){
            for(int i=0; i<n; i++){
                if(visited[i])
                    System.out.print(i+1 + " ");
            }
            System.out.println();
            return;
        }


        for(int i=cur; i<n; i++){
            if(visited[i])
                continue;

            visited[i] = true;
            permutation(cnt+1, i, m);
            visited[i] = false;
        }
    }//permutation
}

순열로 풀면 되는 문제다!
n, m은 전역으로 선언하면 더 편한데 어쩌다보니 그냥 m은 들고다니게 됐다.
 
visited라는 전역 boolean 배열을 이용해 수를 선택했는지 안 했는지 확인한다!
이때, 중복은 안 되므로 방문한 것은 건너뛰는 작업이 필요하다.
 
방문하지 않았다면, 방문처리를 해주고 몇 개의 수를 선택했는지(cnt + 1), 현재 위치는 어디인지(cur)를 표시해주고, 다시 재귀호출한다.
재귀가 끝났다면 방문처리를 다시 없애줘야 다음 수열을 고를 때 영향을 받지 않을 수 있다!
 
마지막으로 cnt가 m과 같다면 수를 모두 선택한 것이므로 방문처리된 수들을 출력해준다.
나는 0부터 시작하여 선택할때마다 넘겼으므로 m과 같으면 0~m-1개를 택했으므로 m개가 맞는데,
1부터 시작했다면 m+1로 재조정해야한다.
 
순열을 다시 생각해볼 수 있는 간단한 문제!

https://www.acmicpc.net/problem/2609

풀이)

import java.util.Scanner;

public class Main_BJ_2609_최대공약수와최소공배수 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();

        System.out.println(gcd(a, b));
        System.out.println(a*b/gcd(a,b));
    }
    private static int gcd(int a, int b){
        if(a%b == 0)
            return b;
        return gcd(b, a%b);
    }
}

유클리드 호제법 안 잊어버리려고 한 번 풀어봤다.