공부흔적

문제 링크

풀이 ) 우선순위큐

문제 조건에 따라 우선순위큐에 넣었다가 빼주면된다.

뺄 때 조건은 절댓값이 같을 때는 작은값 즉 음수를 꺼내고, 절댓값이 다를때는 절댓값이 작은값을 꺼내주면 된다.

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder answer = new StringBuilder();

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

        PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2)->{
            if(Math.abs(o1) == Math.abs(o2)) {
                return o1-o2;
            } else {
                return Math.abs(o1)-Math.abs(o2);
            }
        });
        while(n-- > 0) {
            int x = Integer.parseInt(br.readLine());

            if(x == 0) {
                if(pq.isEmpty()) {
                    answer.append(0).append('\n');
                } else {
                    answer.append(pq.poll()).append('\n');
                }
            } else {
                pq.offer(x);
            }
        }

        System.out.println(answer.toString());
    }
}

문제 링크

풀이 ) MST - Kruskal

  입력으로 들어온 모든 점을 저장한 후 두 점 사이의 거리를 모두 구해서 최소힙에 넣어준다.

  이후 m개의 입력으로 들어온 선분을 먼저 이어주고 크루스칼 알고리즘을 적용하여 MST를 구했다.

코드 )

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

class Main {

    static int n, m;
    static Point[] points;
    static PriorityQueue<Node> pq;
    static int[] root;
    static int nPick = 1;

    public static void main(String[] args) throws IOException {
        input();
        kruskal();
    }

    static void kruskal() {
        double answer = 0;
        while(!pq.isEmpty()) {
            if(nPick == n) {
                break;
            }
            Node cur = pq.poll();
            if(find(cur.v1) != find(cur.v2)) {
                answer += cur.w;
                nPick++;
                union(cur.v1, cur.v2);
            }
        }
        System.out.printf("%.2f\n", answer);
    }

    static void input() 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());
        root = new int[n];
        points = new Point[n];
        for(int i = 0; i < n; ++i) {
            root[i] = i;
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            points[i] = new Point(x, y);
        }
        // MinHeap
        pq = new PriorityQueue<>((o1, o2) ->
            Double.compare(o1.w, o2.w)
        );
        for(int i = 0; i < n-1; ++i) {
            for(int j = i+1; j < n; ++j) {
                int dx = points[i].x-points[j].x, dy = points[i].y-points[j].y;
                double tmp = Math.sqrt(1L*dx*dx+1L*dy*dy);	// long casting
                pq.offer(new Node(i, j, tmp));
            }
        }
        for(int i = 0; i < m; ++i) {
            st = new StringTokenizer(br.readLine(), " ");
            int v1 = Integer.parseInt(st.nextToken())-1;
            int v2 = Integer.parseInt(st.nextToken())-1;
            if(find(v1) != find(v2)) {
                nPick++;
                union(v1, v2);
            }
        }
    }

    static void union(int v1, int v2) {
        int root1 = find(v1);
        int root2 = find(v2);
        if(v1 < v2) {
            root[root2] = root1;
        } else {
            root[root1] = root2;
        }
    }

    static int find(int v) {
        if(root[v] == v) {
            return v;
        }
        return root[v] = find(root[v]);
    }

    static class Node {
        int v1, v2;
        double w;

        public Node(int v1, int v2, double w) {
            this.v1 = v1;
            this.v2 = v2;
            this.w = w;
        }
    }

    static class Point {
        int x, y;

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

주의 )

  두 점 사이의 거리를 구할 때, 좌표의 범위가 [0, 1000000] 여서 차이를 제곱하면 Integer 범위를 벗어나기 때문에 Long으로 캐스팅해주는 작업이 필요하다.

문제 링크

풀이 ) BFS

  현재 아기상어 위치를 시작으로 BFS로 먹이 후보를 찾고

  후보 중 조건에 만족하는 먹이로 이동하기를 이동할 수 없을 때까지 반복한다.

코드 )

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

class Main {

    static int n;
    static int[][] board;
    static boolean[][] visited;
    static Fish shark;
    static Fish next;
    static Queue<Fish> q;

    static int answer;

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

    public static void main(String[] args) throws IOException {
        input();	// 입력
        solve();	// 풀이
    }

    static void solve() {

        while(true) {
            int distance = init();	// 현재 상어 위치부터 다음 먹이까지의 거리 (초기화)

            while(!q.isEmpty() && next == null) {	// 다음 물고기가 없을때까지
                int size = q.size();
                distance++;
                while (size-- > 0) {
                    Fish cur = q.poll();
                    /*
                     * 다음 물고기의 크기가 더 작은 지 확인하고
                     * 더 작으면 먹을 수 있는 다른 물고기와 위치를 비교하여 갱신
                     */
                    promise(cur.x, cur.y);

                    for (int dir = 0; dir < 4; ++dir) {
                    	// 다음 위치로 이동할 수 있으면 추가
                        findRoute(cur.x+dx[dir], cur.y+dy[dir]);
                    }
                }
            }

            if(next != null) {
            	// 이동 가능한 경우
                move(distance);
            } else {
            	// 이동 불가능한 경우
                System.out.println(answer);
                break;
            }
        }
    }

    static void move(int distance) {
        answer += distance;
        // 물고기를 먹고
        board[next.x][next.y] = 0;
        shark = next;
        // 크기가 증가할 수 있으면 증가
        shark.grow();
    }

    static void findRoute(int x, int y) {
        if (!isIn(x, y) || visited[x][y] || board[x][y] > shark.size){
            return;
        }

        visited[x][y] = true;
        q.offer(new Fish(x, y, board[x][y], -1));
    }

    static void promise(int x, int y) {
        if (board[x][y] > 0 && board[x][y] < shark.size) {
            Fish candidate = new Fish(x, y, shark.size, shark.feed+1);
            if(next == null ||
                    candidate.x < next.x ||
                    (candidate.x == next.x && candidate.y < next.y)) {
                next = candidate;
            }
        }
    }

    static int init() {
        visited = new boolean[n][n];
        q = new LinkedList<>();
        q.offer(shark);
        visited[shark.x][shark.y] = true;
        next = null;
        return -1;
    }

    static boolean isIn(int nx, int ny) {
        return nx>=0&&nx<n&&ny>=0&&ny<n;
    }

    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        board = new int[n][n];
        for(int i = 0; i < n; ++i) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j < n; ++j) {
                board[i][j] = Integer.parseInt(st.nextToken());
                if(board[i][j] == 9) {
                    shark = new Fish(i, j, 2, 0);
                    board[i][j] = 0;
                }
            }
        }
    }

    static class Fish {
        int x, y;
        int size;
        int feed;

        public Fish(int x, int y, int size, int feed) {
            this.x = x;
            this.y = y;
            this.size = size;
            this.feed = feed;
        }

        void grow() {
            if(feed == size) {
                size++;
                feed = 0;
            }
        }
    }
}

주의 )

  단순히 상, 좌, 우, 하 순으로 검사하게되면 4번 예시 케이스에서 답인 60이 아닌 56이 출력된다.

문제 링크

풀이 ) DFS

1. 각 역이 순환선에 포함된 역인지 확인
2. 사이클에서 지선이 있는 역에서부터 각 지선 노선의 거리 구하기

위의 순서대로 DFS만을 이용해서 구했다.

  먼저 각 역이 순환선인지 확인하기 위해 모든 점에 대해서 현재 점으로 되돌아 오는지 확인했다. (checkCycle()) 이때 순환선을 확인하면 순환선 내의 역은 한번에 구해 반복 횟수를 줄일 수 있다. (return type이 boolean인 이유)

  순환역에 속한 역 중 차수가 3 이상인 역은 지선으로 갈 수 있는 역이므로 이 역을 시작으로해서 지선에 포함된 역까지의 거리를 구한다. (getDistance())

코드 )

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

class Main {

    static int n;
    static List<Integer>[] adj;
    static boolean[] visited;
    static boolean[] isCycle;
    static int[] distance;

    public static void main(String[] args) throws IOException {
        input();
        checkCycle();	// 사이클 확인
        getDistance();	// 거리 구하기
    }

    static void getDistance() {
        distance = new int[n+1];
        visited = new boolean[n+1];

		// 사이클에서 벗어나는 길 거리 구하기
        for(int i = 1; i <= n; ++i)
            if(isCycle[i] && adj[i].size() > 2)
                searchRoute(i);

		// 거리 출력
        StringBuilder sb = new StringBuilder();
        for(int i = 1; i <= n; ++i) {
            sb.append(distance[i] + " ");
        }
        System.out.println(sb.toString());
    }

    static void searchRoute(int i) {
        for(int next: adj[i]) {
            if(isCycle[next] || distance[next] > 0) {
               continue;
            }
            distance[next] = distance[i]+1;
            searchRoute(next);
        }
    }

    static void checkCycle() {
        isCycle = new boolean[n+1];

        for(int i = 1; i <= n; ++i)
            if(!isCycle[i]) {
                visited = new boolean[n+1];
                dfs(i, i, 0);
            }
    }

    static boolean dfs(int strt, int i, int cnt) {
        for(int next: adj[i]) {
            if(next == strt) {
            // 바로 돌아오는 경우를 cnt를 사용해서 방지
                if (cnt > 1)
                    return isCycle[i] = true;
                else
                    continue;
            }
            
            // 다음이 사이클(사이클이 아닌 곳에서 사이클로 -> 사이클 아님)
            // 현재가 사이클(조건 만족)
            // 이미 방문(사이클인지 여부가 이미 나옴)
            if(isCycle[next] || isCycle[i] || visited[next])
                continue;
            visited[next] = true;
            isCycle[i] = dfs(strt, next, cnt+1);
        }
        return isCycle[i];
    }

    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        adj = new List[n+1];
        for(int i = 1; i <= n; ++i)
            adj[i] = new ArrayList<>();
        for(int i = 0; i < n; ++i) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            // 양방향
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            adj[v1].add(v2);
            adj[v2].add(v1);
        }
    }
}

알게된 점 )

  그래프에서 정점과 간선의 개수가 같고 모두 이어져 있으면 사이클은 단 하나만 가능하다.

문제 링크

풀이 ) 우선순위큐

  처음에는 큐를 이용해서 완전탐색을 하는 방식으로 구현하려했지만 이럴 때의 시간복잡도는 O(nk)가 되고 n과 k가 각각 10만 이하이므로 완전탐색으로는 해결할 수 없었다.

  계산대를 이용하는 고객을 저장하는 우선순위큐를 만들어서, 끝나는 시간이 빠르고 이용하는 계산대의 번호가 큰 순서대로 우선순위가 높게 만들었다.

  손님을 줄세우고 먼저 계산대에 모두 채워 넣는다. (* 이때 계산대의 수에 조심하지 않으면 null pointer exception 발생)

  이후 계산이 가장 빨리 끝나는 고객의 시간으로 시간을 갱신한 이후(time = counter.peek().time), 해당 시간에 계산이 끝나는 고객을 모두 제거하고(pollAt(time)) 비어있는 계산대에 손님으로 채운다.(offerAt(time))

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;

    static int n, k;
    static Queue<Info> customers = new LinkedList<>();	// 고객 줄
    static PriorityQueue<Info> counters = new PriorityQueue<>((o1, o2)->{
        if(o1.time == o2.time)
            return o2.num-o1.num;
        return o1.time-o2.time;
    });		// 끝나는 시간이 짧고, 계산대 번호가 큰 순서대로 제거하는 우선순위큐
    static Stack<Integer> vacancy = new Stack<>();	// 비어있는 계산대
    static long answer;		// 결과
    static int nFinish;		// 계산 끝난 사람 수

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }

    static void solve() throws IOException {
        int time = 0;
        for(int i = 0; i < k; ++i){		// 처음 k명 계산대 이용
            if(customers.isEmpty())		// * 주의사항: 계산대수 > 고객수
                break;
            Info customer = customers.poll();
            customer.time = customer.w;
            customer.num = i;
            counters.offer(customer);
        }
        while(!customers.isEmpty()){
            if(!counters.isEmpty())
                time = counters.peek().time;	// 시간 갱신
            pollAt(time);
            offerAt(time);
        }

        while(!counters.isEmpty())	// 줄이 없는 상태에서 계산대 이용중인 고객 계산
            answer += 1L * (++nFinish) * counters.poll().id;

        bw.write(answer+" ");
        bw.flush();
    }

    static void pollAt(int time){	// time 시간에 계산을 마치는 고객 모두 계산대에서 제거
        while(!counters.isEmpty()){
            Info counter = counters.peek();
            if(counter.time == time){	// 가장 빨리 끝나는 고객의 시간이 현재시간이면 제거
                counters.poll();
                vacancy.push(counter.num);	// 비어있는 계산대 추가
                answer += 1L * (++nFinish) * counter.id;	// 정답 추가
            }
            else
                break;
        }
    }

    static void offerAt(int time){	// time 시간에 빈 계산대에 고객 채우기
        while(!customers.isEmpty() && !vacancy.isEmpty()){
            Info customer = customers.poll();
            customer.num = vacancy.pop();	// 비어있는 계산대 이용
            customer.time = time+customer.w;	// 계산대 이용하는 고객의 끝 시간 갱신
            counters.offer(customer);		// 계산대 이용
        }
    }

    static void input() throws IOException {
        st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        for(int i = 0; i < n; ++i){
            st = new StringTokenizer(br.readLine(), " ");
            customers.offer(new Info(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }
    }

    static class Info{
        int id, w, time, num;
        // id: 고객의 회원번호
        // w: 물건 개수(계산 소요 시간)
        // time: 계산을 마치는 시간
        // num: 이용하는 계산대 번호 

        public Info(int id, int w) {
            this.id = id;
            this.w = w;
        }
    }
}

주의 )

• 계산대의 수가 손님보다 많은 경우

문제 링크

풀이 )

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

• 전위: 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);
    }
}

주의 )

  인덱스 실수