이것저것 개발 블로그

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/1753

풀이)

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_1753_최단경로 {
    static ArrayList<node>[] graph;
    static int vNum;
    static class node{
        int v;
        int w;

        public node(int v, int w) {
            this.v = v;
            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());
        vNum = Integer.parseInt(st.nextToken()); // 정점 개수
        int eNum = Integer.parseInt(st.nextToken()); // 간선 개수
        int k = Integer.parseInt(br.readLine()); // 시작 정점 번호
        graph = new ArrayList[vNum+1];
        for(int i=1; i<=vNum; i++)
            graph[i] = new ArrayList<>();

        for(int i=0; i<eNum; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken()); // start
            int v = Integer.parseInt(st.nextToken()); // end
            int w = Integer.parseInt(st.nextToken()); // weight

            graph[u].add(new node(v, w));
        }
        dijkstra(k);
    }//main
    private static void dijkstra(int k){
        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[vNum+1];

        // 최소 거리 정보 답을 배열 => 최대값으로 초기화
        for(int i=1; i<=vNum; i++)
            dist[i] = Integer.MAX_VALUE;
        pq.offer(new node(k, 0));
        // 시작 지점은 거리 0
        dist[k] = 0;

        while(!pq.isEmpty()){
            node cur = pq.poll();
            if(dist[cur.v] < cur.w)
                continue;

            for(int i=0; i<graph[cur.v].size(); i++){
                node next = graph[cur.v].get(i);

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

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

대놓고 다익스트라로 풀라는 문제. 그런데 까먹어서 개념정립이 시급...

https://sskl660.tistory.com/59

많이 참고한 블로그!

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

풀이)

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

public class Main_BJ_11053_가장긴증가하는부분수열 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++)
            arr[i] = Integer.parseInt(st.nextToken());

        int[] dp = new int[n];
        for(int i=0; i<n; i++)
            dp[i] = 1;

        // 전체 보자
        for(int i=0; i<n; i++){
            // 이전부터 현재 위치까지
            for(int j=0; j<i; j++){
                //현재 위치보다 작은 애가 있으면
                if(arr[j] < arr[i])
                    //dp에 갱신하며 저장. 이때, 이전의 값보다 큰 값을 저장해야한다
                    dp[i] = Math.max(dp[i], dp[j]+1);
            }
        }

        int ans = -1;
        for(int i=0; i<n; i++){
            ans = Math.max(ans, dp[i]);
        }
        System.out.println(ans);
    }//main
}

이 문제도 시리즈가 여러개 있는 것으로 안다.

하지만 오랜만에 풀어서 틀려버렸지요ㅋㅋㅋㅋㅋ

일단, 이건 완탐이 필요하다.

하지만, 중간부터 시작한 수열이 가장 길 수도 있고, 증가하는 수열이 연달아 나오지 않을 수 있기 때문에 주의해야한다.

따라서, dp[i] : i번째 수열을 포함한 가장 긴 수열

이때, dp배열은 기본 1이다.(가장 짧아도 수열 1개이기 때문!)

여기서 주의할 점은 dp 배열은 어떠한 위치에서 가장 긴 수열을 저장한 것이기 때문에,

꼭 dp 배열에서 가장 큰 값을 찾아야한다!

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

풀이)

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

public class Main_BJ_1991_트리순회 {
    static int[][] tree;
    static int n;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        tree = new int[n+1][2];

        for(int i=1; i<=n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int root = st.nextToken().charAt(0) - 'A' + 1;
            int left = st.nextToken().charAt(0) - 'A' + 1;
            int right = st.nextToken().charAt(0) - 'A' + 1;


            tree[root][0] = left;
            tree[root][1] = right;
        }

        boolean[] visited = new boolean[n+1];
        preorder(1, visited);
        System.out.println();
        visited = new boolean[n+1];
        inorder(1, visited);
        System.out.println();
        visited = new boolean[n+1];
        postorder(1, visited);
    }//main
    private static void preorder(int node, boolean[] visited){
        visited[node] = true;
        System.out.print((char) (node-1+'A'));

        if(tree[node][0]>0 && !visited[tree[node][0]])
            preorder(tree[node][0], visited);

        if(tree[node][1]>0 &&!visited[tree[node][1]])
            preorder(tree[node][1], visited);
    }//preorder
    private static void inorder(int node, boolean[] visited){
        visited[node] = true;

        if(tree[node][0]>0 && !visited[tree[node][0]])
            inorder(tree[node][0], visited);

        System.out.print((char) (node-1+'A'));

        if(tree[node][1]>0 &&!visited[tree[node][1]])
            inorder(tree[node][1], visited);
    }//inorder
    private static void postorder(int node, boolean[] visited){
        visited[node] = true;

        if(tree[node][0]>0 && !visited[tree[node][0]])
            postorder(tree[node][0], visited);

        if(tree[node][1]>0 &&!visited[tree[node][1]])
            postorder(tree[node][1], visited);

        System.out.print((char) (node-1+'A'));
    }//postorder
}

문제에서 친절히 preorder, inorder, postorder의 순서를 알려줘서 재귀는 어렵지 않게 짤 수 있었다.

(출력을 처음, 중간, 마지막 중 하나로 선택하면 되니까!!)

다만, A, B, C와 index에 관련해서 어떻게 처리할지 고민이 있었다.

빨리 정해서 했으면 됐을텐데 밍기적거림..ㅎ

https://velog.io/@gandi0330/Java-%EB%B0%B1%EC%A4%80-%ED%8A%B8%EB%A6%AC-%EC%88%9C%ED%9A%8C-1991%EB%B2%88

이 블로그처럼 class를 따로 만들어 노드를 생성하는 것이 참 깔끔하고 좋은것 같다.

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

풀이)

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

public class Main_BJ_6064_카잉달력 {
    public static void main(String[] args) throws Exception{
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        for(int tc=1; tc<=t; tc++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(st.nextToken());
            int n = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken()) - 1;
            int y = Integer.parseInt(st.nextToken()) - 1;

            boolean check = false;
            for(int i=x; i<(n*m); i+=m){
                if(i%n == y){
                    System.out.println(i+1);
                    check = true;
                    break;
                }
            }
            if(!check)
                System.out.println(-1);

        }//tc
    }//main
}

완전 탐색으로 풀었다.(안 될줄 알았는데 되더라..?)

하지만 다른 방식으로도 풀 수 있는 방법이 대단한 것 같다.

https://zoosso.tistory.com/280

다른 방식으로 푼 블로그 올려두고 가기~

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

풀이)

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

public class Main_BJ_11651_좌표정렬하기2 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        PriorityQueue<int []> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[1] == o2[1])
                    return o1[0]-o2[0];
                return o1[1]-o2[1];
            }
        });

        for(int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            pq.offer(new int[] {x, y});
        }

        for(int i=0; i<n; i++) {
            int[] cur = pq.poll();
            System.out.println(cur[0]+" "+cur[1]);
        }
    }
}

comparator 사용하면 간단한 문제!

프로그래머스에서 이거 언제 다 일일히 치지....?

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

풀이)

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

public class Main_BJ_1389_케빈베이컨의6단계법칙 {
    static int[][] adj;
    static int INF = 10000;
    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());
        adj = new int[n+1][n+1];
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(i==j)
                    adj[i][j] = 0;
                else
                    adj[i][j] = INF;
            }
        }

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

            adj[a][b] = 1;
            adj[b][a] = 1;
        }


        for(int k=1; k<=n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    adj[i][j] = Math.min(adj[i][j], adj[i][k]+adj[k][j]);
                }
            }
        }

        int min = 0;
        int sum = Integer.MAX_VALUE;
        for(int i=1; i<=n; i++){
            int temp = 0;
            for(int j=1; j<=n; j++){
                if(j != i) {
                    temp += adj[i][j];
                }
            }
            if(sum > temp){
                sum = temp;
                min = i;
            }
        }

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

플로이드-워셜로 풀었는데 몇 번의 시도가 실패했다.

첫 번째는, 플로이드 워셜 개념을 다시 상기시켜야 할 필요성...

두 번째는, 큰 값으로 갱신할 때 Integer.MAX_VALUE로 하지 말아야 한다는 것이다.(그냥 충분하게 큰 값이면 된다)

아무 생각 없이 Integer.MAX_VALUE로 했다가 둘이 더해지면 값이 넘어가 음수값이 되어버려서 계산을 할 수 없었다.

(플로이드 워셜은 가중치가 모두 양수여야 하니까!!)

다음엔 한 번에 잘 풀어봤으면 좋겠다.

그리고 당연히 bfs로도 풀 수 있다!!!

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

풀이)

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

public class Main_BJ_5525_IOIOI {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int s = Integer.parseInt(br.readLine());
        String str = br.readLine();
        char[] arr = str.toCharArray();
        int ans = 0;
        int cnt = 0;

        for(int i=1; i<s-1; i++){
            if(arr[i-1] == 'I' && arr[i]=='O' && arr[i+1] == 'I'){
                cnt++;

                if(cnt == n){
                    cnt--;
                    ans++;
                }

                i++;
            }
            else
                cnt = 0;
        }

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

슬라이딩 윈도우로 풀려고 하다가 실패한 문제였다. 사실 슬라이딩 윈도우로 풀기에도 어려운 문제긴 했다.

1. IOI가 반복되므로 한칸씩 이동하면서 본다. 일치한다면, i를 한 번 더 추가하여 2번 이동하게 만든다!

2. IOI가 반복되는 개수를 세고, 이것이 n이 된다면 정답+1 후 탈출!(O의 개수가 n과 같다는 것과 동일)

3. 다르다면 반복되는 개수는 0으로 돌아간다.

참고한 블로그)

https://velog.io/@lifeisbeautiful/Java-%EB%B0%B1%EC%A4%80-5525%EB%B2%88-IOIOI-with-%EC%9E%90%EB%B0%94

추가적으로 보면 좋은 블로그)

https://girawhale.tistory.com/11