공부흔적

문제 링크

풀이 )

  전위, 중위, 후위 순회 시 구조를 보고 풀었다.

• 전위: root ( left ) ( right )
• 중위: ( left ) root ( right )
• 후위: ( left ) ( right ) root

  후위 순회 결과의 마지막이 root이고 이를 이용해서 중위 순회에서의 root 위치를 찾아 좌 우를 나눈다.

  중위 순회에서의 root 위치를 빠르게 찾기 위해 index를 저장하는 배열을 만들었다.

import java.io.*;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int[] inOrder;
    static int[] postOrder;

    static int[] index;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        String[] in;

        int n = Integer.parseInt(br.readLine());
        inOrder = new int[n+1];
        postOrder = new int[n+1];
        index = new int[n+1];

        in = br.readLine().split(" ");
        for(int i = 0; i < n; ++i){
            inOrder[i] = Integer.parseInt(in[i]);
            index[inOrder[i]] = i;
        }
        in = br.readLine().split(" ");
        for(int i = 0; i < n; ++i)
            postOrder[i] = Integer.parseInt(in[i]);
        preOrder(0, n-1, 0, n-1);
        bw.flush();
    }

    static void preOrder(int inSrt, int inEnd, int postSrt, int postEnd) throws IOException {
        if(inSrt > inEnd || postSrt > postEnd)
            return;

        int root = postOrder[postEnd];
        bw.write(root+" ");
        int idx = index[root];
        preOrder(inSrt, idx-1, postSrt, postSrt+(idx-1-inSrt));
        preOrder(idx+1, inEnd, postSrt+(idx-inSrt), postEnd-1);
    }
}

주의 )

  인덱스 실수

문제 링크

착오 )

  처음에는 그리디하게 접근하려고 했다.

  입력받은 배열을 정렬한 이후 배열의 앞부터 가장 큰 수와 가장 작은 수를 번갈아가면서 저장하려고했지만 이런 방법으로는 안된다는 것을 반례를 통해 알게되어 다른 방법으로 접근했다.

  이 방법을 좀더 개선한다면 그리디로 풀 수 있을 거라고 생각된다.

풀이 ) 

  입력받은 배열의 모든 순열에 대해서 결과값을 비교하면서 최댓값을 구했다.

  다음 순열에 대해서는 nextPermutation( ) 메서드를 구현해서 사용했다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        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());

        Arrays.sort(arr);
        int ans = -(int)1e7;
        do{
            ans = Math.max(ans, cal(arr));
        } while(nextPermutation(arr));
        System.out.println(ans);
    }

    static boolean nextPermutation(int[] arr) {
        int len = arr.length;
        int i=len-1;
        while( i>0 && arr[i-1] >= arr[i] )
            --i;
        if(i==0)
            return false;

        int j = len-1;
        while(arr[i-1]>=arr[j])
            --j;

        int tmp = arr[i-1];
        arr[i-1] = arr[j];
        arr[j] = tmp;

        int k = len-1;
        while(i<k) {
            tmp=arr[i];
            arr[i++]=arr[k];
            arr[k--]=tmp;
        }
        return true;
    }

    static int cal(int[] arr){
        int len = arr.length;
        int ret = 0;
        for(int i = 1; i < len; ++i)
            ret += Math.abs(arr[i]-arr[i-1]);
        return ret;
    }
}

문제 링크

풀이 )

  처음에는 방문 여부를 나타내는 boolean 2차원 배열 visited를 선언하지 않고 풀려다가 많은 문제가 발생했다.

• 비활성화된 바이러스를 0으로 갱신하고 시작
  • 처음에 다 퍼져있는 경우에 대해서 다른 결과를 출력한다.
• 바이러스가 방문한 곳을 2로 갱신하고, 1이 아닌 곳만 방문
  
  • 큐에 중복 방문으로 인한 메모리 초과
• 바이러스가 방문한 곳을 3으로 갱신하고, 0 2인 곳만 방문
  
  • 비활성화된 바이러스를 벽으로 생각함

  결국 visited 배열을 사용해서 했다.

  자세한 풀이는 아래 주석을 달아두었다.

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

public class Main {
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

    static int n,m;
    static int[][] board;
    static int ans = (int)1e7;
    static ArrayList<Point> virusList = new ArrayList<>();

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

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        board = new int[n][n];
        for(int i = 0; i < n; ++i){
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j < n; ++j){
                board[i][j] = Integer.parseInt(st.nextToken());
                if(board[i][j] == 2){
                    virusList.add(new Point(i, j));
                }
            }
        }
        // 입력 & 비활성화된 바이러스를 list에 저장

        combination(m, new int[m], 0);	// 활성화될 바이러스 선택(조합 - virusList.size() C m)
        if(ans == (int)1e7)
            ans = -1;
        System.out.println(ans);
    }

    static void combination(int toPick, int[] picked, int pos){
        if(toPick == 0){
            bfs(picked);	// 활성화될 바이러스를 시작으로 bfs 탐색
            return;
        }

        for(int i = pos; i < virusList.size(); ++i){
            picked[picked.length-toPick] = i;
            combination(toPick-1, picked, i+1);
        }
    }

    static void bfs(int[] picked){
        int[][] tmp = new int[n][];
        for(int i = 0; i < n; ++i)
            tmp[i] = board[i].clone();	// board 값에 영향을 주지 않기 위한 임시 배열
        boolean[][] visited = new boolean[n][n];	// 방문 여부

        Queue<Point> virusQ = new LinkedList<>();
        for(int i = 0; i < picked.length; ++i){
            Point virus = virusList.get(picked[i]);
            virusQ.offer(virus);
            visited[virus.x][virus.y] = true;
        }	// 활성화될 바이러스를 큐에 집어 넣으면서 방문여부 갱신

        int time = -1;	// 바이러스가 퍼지는데 걸리는 시간
        while(!virusQ.isEmpty()){
            time++;
            boolean flag = false;	// 바이러스가 퍼졌는지 확인할 때 2중 for문을 탈출하기 위한 flag
            for(int i = 0; i < n; ++i){
                for(int j = 0; j < n; ++j)
                    if(tmp[i][j] == 0){
                        flag = true;
                        break;
                    }
                if(flag)
                    break;
            }
            if(!flag){	// 바이러스가 더이상 퍼질 수 없으면 ans를 갱신하고 종료
                ans = Math.min(ans, time);
                return;
            }

            int size = virusQ.size();
            while(size-- > 0){
                Point cur = virusQ.poll();
                int x = cur.x, y = cur.y;
                for(int dir = 0; dir < 4; ++dir){
                    int nx = x+dx[dir], ny = y+dy[dir];
                    if(!isIn(nx, ny) || tmp[nx][ny] == 1 || visited[nx][ny])	// 확산할 수 없는 경우
                        continue;
                    visited[nx][ny] = true;	// 확산할 수 있는 경우 방문 여부와 임시 배열을 갱신하고, 큐에 추가
                    tmp[nx][ny] = 2;
                    virusQ.offer(new Point(nx, ny));
                }
            }
            if(virusQ.isEmpty())
                break;
        }
    }

    static boolean isIn(int x, int y){
        return 0 <= x && x < n && 0 <= y && y < n;
    }
}

주의 )

  처음 ans의 값을 100으로 설정해서 틀렸다.

  초기에 주어진 바이러스가 1개이고 가로세로 50의 ㄹ모양의 연구소가 주어지면 100초 이상 걸리기 때문에 넉넉한 값을 주어야 한다.

문제 링크

풀이 )

  하나의 칸에 여러 나무가 있을 때 나이가 적은 나무부터 양분을 공급한다는 내용을 보고 우선순위큐를 사용했다.

  feed 배열에는 양분을 저장했고, a 배열에는 겨울마다 늘어나는 양분을 저장했다.

  나무의 좌표와 나이를 저장하는 우선순위큐를 만들어서 나이가 낮은 순으로 poll 되도록 구현했다.

  처음에는 우선순위큐 하나만 사용해서 구현하려고했기 때문에 큐의 크기를 먼저 구한 후 큐의 크기만큼만 반복문을 돌렸지만, 이런 경우 중간에 나이가 낮은 나무가 들어오는 경우 의도와 다르게 나오는 경우가 있었기 때문에 다른 우선순위 큐를 선언해서 사용했다.

  나머지는 문제에서 요구하는 순서대로 구현했다.

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

public class Main {
    static int[] dx = {0, 1, 1, 1, 0, -1, -1, -1};
    static int[] dy = {1, 1, 0, -1, -1, -1, 0, 1};

    public static void main(String[] args) throws IOException {
        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());
        int k = Integer.parseInt(st.nextToken());
        int[][] feed = new int[n+1][n+1];
        int[][] a = new int[n+1][n+1];

        PriorityQueue<Info> treeQ = new PriorityQueue<>((o1, o2)->{
            return o1.age-o2.age;
        });
        Queue<Info> dieQ = new LinkedList<>();

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

        for(int i = 0; i < m; ++i){
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int age = Integer.parseInt(st.nextToken());
            treeQ.offer(new Info(x, y, age));
        }
        // 입력

        while(k-- > 0) {
            PriorityQueue<Info> tmp = new PriorityQueue<>((o1, o2)->{
                return o1.age-o2.age;
            });
            int size = treeQ.size();
            while (size-- > 0) {
                Info tree = treeQ.poll();
                int x = tree.x, y = tree.y, age = tree.age;
                if (feed[x][y] >= age) {
                    feed[x][y] -= age;
                    age++;
                    tmp.offer(new Info(x, y, age));
                } else
                    dieQ.offer(new Info(x, y, age));
            }
            treeQ = tmp;
            // 봄

            while (!dieQ.isEmpty()) {
                Info die = dieQ.poll();
                feed[die.x][die.y] += die.age / 2;
            }
            // 여름

            PriorityQueue<Info> tmp2 = new PriorityQueue<>((o1, o2)->{
                return o1.age-o2.age;
            });
            size = treeQ.size();
            while (size-- > 0) {
                Info tree = treeQ.poll();
                tmp2.offer(tree);
                if (tree.age % 5 == 0) {
                    int x = tree.x, y = tree.y;
                    for (int dir = 0; dir < 8; ++dir) {
                        int nx = x + dx[dir], ny = y + dy[dir];
                        if (0 < nx && nx <= n && 0 < ny && ny <= n)
                            tmp2.offer(new Info(nx, ny, 1));
                    }
                }
            }
            treeQ = tmp2;
            // 가을

            for(int i = 1; i <= n; ++i){
                for(int j = 1; j <= n; ++j)
                    feed[i][j] += a[i][j];
            }
            // 겨울
        }
        System.out.println(treeQ.size());
    }

    static class Info{
        int x, y, age;

        public Info(int x, int y, int age) {
            this.x = x;
            this.y = y;
            this.age = age;
        }
    }
}

문제 링크

풀이 )

  서류 성적과 면접 성적 뭐가 되어도 상관 없지만 나는 서류 성적에 대해서 성적이 좋은 순서에서 안좋은 순서로 정렬해줬다.

  1등에 있는 사람은 서류 성적이 누구보다 높기 때문에 항상 뽑힐 수 있다.

  이후에 있는 사람은 1등보다 서류 성적은 떨어지기 때문에 면접 성적은 더 좋아야한다.

  그렇기 때문에 현재의 가장 낮은 면접 성적 커트라인을 cut에 저장하여 커트라인을 통과한다면, 커트라인을 현재 사람의 면접 성적과 비교하여 더 작은 값으로 갱신해주고, 정답을 한명 늘려준다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        String[] in;

        int t = Integer.parseInt(br.readLine());
        while(t-- > 0){
            int n = Integer.parseInt(br.readLine());
            Point[] scores = new Point[n];
            for(int i = 0; i < n; ++i){
                in = br.readLine().split(" ");
                scores[i] = new Point(Integer.parseInt(in[0]), Integer.parseInt(in[1]));
            }
            Arrays.sort(scores, (o1, o2)->
                o1.x-o2.x
            );
            int ans = 0;
            int cut = (int)1e9;
            for(int i = 0; i < n; ++i){
                int cur = scores[i].y;
                if(cur < cut) {
                    ans++;
                    cut = Math.min(cur, cut);
                }
            }
            sb.append(ans).append('\n');
        }
        System.out.print(sb);
    }
}

문제 링크

풀이 ) DFS

  적록색약이 아닌 사람은 R, G, B를 각각 따로 / 적록색약인 사람은 R과G를 구분하지 않고, B만 따로 봐주면 된다.

  각각 다르게 DFS를 구현할 수 있지만 같은 메서드에 대해서 flag를 다르게 넘겨주어 다음 칸이 유효한지 확인하는 부분만 다르게 구현했다.

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

public class Main {
    static int n;
    static char[][] board;
    static boolean[][] visited;

    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

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

        n = Integer.parseInt(br.readLine());
        board = new char[n][];
        for(int i = 0; i < n; ++i)
            board[i] = br.readLine().toCharArray();

        visited = new boolean[n][n];
        int ans = 0;
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                if(!visited[i][j]){
                    dfs(i, j, board[i][j], false);
                    ans++;
                }
            }
        }
        sb.append(ans).append(' ');

        visited = new boolean[n][n];
        ans = 0;
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                if(!visited[i][j]){
                    dfs(i, j, board[i][j], true);
                    ans++;
                }
            }
        }
        sb.append(ans);
        System.out.println(sb);
    }

    static void dfs(int x, int y, char c, boolean flag){
        visited[x][y] = true;
        for(int dir = 0; dir < 4; ++dir){
            int nx = x+dx[dir], ny = y+dy[dir];
            if(!isIn(nx, ny, c, flag) || visited[nx][ny])
                continue;
            dfs(nx, ny, c, flag);
        }
    }

    static boolean isIn(int x, int y, char c, boolean flag){
        if(flag){
            if(c == 'B')
                return 0 <= x && x < n && 0 <= y && y < n && board[x][y] == 'B';
            else
                return 0 <= x && x < n && 0 <= y && y < n && board[x][y] != 'B';
        }
        return 0 <= x && x < n && 0 <= y && y < n && board[x][y] == c;
    }
}

주의 )

- visited와 ans의 초기화