[BOJ] 17472. 다리만들기2 (Java)

Problem

제출일 : 2020-04-14

문제 풀이 시간 : 2H 30M

난이도 : ★★★☆

---

link : https://www.acmicpc.net/problem/17472

섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다.

섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고, 아래 그림은 네 개의 섬으로 이루어진 나라이다. 색칠되어있는 칸은 땅이다.

다리는 바다에만 건설할 수 있고, 다리의 길이는 다리가 격자에서 차지하는 칸의 수이다. 다리를 연결해서 모든 섬을 연결하려고 한다. 섬 A에서 다리를 통해 섬 B로 갈 수 있을 때, 섬 A와 B를 연결되었다고 한다. 다리의 양 끝은 섬과 인접한 바다 위에 있어야 하고, 한 다리의 방향이 중간에 바뀌면 안된다. 또, 다리의 길이는 2 이상이어야 한다.

다리의 방향이 중간에 바뀌면 안되기 때문에, 다리의 방향은 가로 또는 세로가 될 수 밖에 없다. 방향이 가로인 다리는 다리의 양 끝이 가로 방향으로 섬과 인접해야 하고, 방향이 세로인 다리는 다리의 양 끝이 세로 방향으로 섬과 인접해야 한다.

섬 A와 B를 연결하는 다리가 중간에 섬 C와 인접한 바다를 지나가는 경우에 섬 C는 A, B와 연결되어있는 것이 아니다.

아래 그림은 섬을 모두 연결하는 올바른 2가지 방법이고, 다리는 회색으로 색칠되어 있다. 섬은 정수, 다리는 알파벳 대문자로 구분했다.

다리의 총 길이: 13D는 2와 4를 연결하는 다리이고, 3과는 연결되어 있지 않다.	다리의 총 길이: 9 (최소)

다음은 올바르지 않은 3가지 방법이다

C의 방향이 중간에 바뀌었다	D의 길이가 1이다.	가로 다리인 A가 1과 가로로 연결되어 있지 않다.

다리가 교차하는 경우가 있을 수도 있다. 교차하는 다리의 길이를 계산할 때는 각 칸이 각 다리의 길이에 모두 포함되어야 한다. 아래는 다리가 교차하는 경우와 기타 다른 경우에 대한 2가지 예시이다.

A의 길이는 4이고, B의 길이도 4이다.총 다리의 총 길이: 4 + 4 + 2 = 10	다리 A: 2와 3을 연결 (길이 2)다리 B: 3과 4를 연결 (길이 3)다리 C: 2와 5를 연결 (길이 5)다리 D: 1과 2를 연결 (길이 2)총 길이: 12

나라의 정보가 주어졌을 때, 모든 섬을 연결하는 다리 길이의 최솟값을 구해보자.

Constraints

• 1 ≤ N, M ≤ 10
• 3 ≤ N×M ≤ 100
• 2 ≤ 섬의 개수 ≤ 6

Input

모든 섬을 연결하는 다리 길이의 최솟값을 출력한다. 모든 섬을 연결하는 것이 불가능하면 -1을 출력한다.

Output

테스트 케이스의 개수 만큼 T개의 줄에 각 테스트 케이스에 대한 답을 출력한다.

각 줄은 “#x”로 시작하고, 공백을 하나 둔 후 정답을 출력한다. (x는 테스트 케이스의 번호이며, 1번부터 시작한다.)

출력해야 할 정답은 M시간 후 남아 있는 미생물 수의 총 합이다.

Example

input

7 8
0 0 0 0 0 0 1 1
1 1 0 0 0 0 1 1
1 1 0 0 0 0 0 0
1 1 0 0 0 1 1 0
0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1

output

9

Solution & Inpression

문제 풀이 순서

1. 입력 받은 map의 섬의 개수를 파악하며 섬에 번호를 붙여준다 (DFS)
2. 각 섬에서 출발하여 도착 가능한 섬에 건설할수 있는 최소비용을 찾는다. (BFS)
3. 모든 섬을 연결하는 다리 길이의 최솟값을 구한다(MST:최소신장트리)

이 문제는 완전탐색, 너비우선탐색, 깊이우선탐색, 그래프이론, 최소신장트리를 이용하여 구현하는 문제로 문제의 난이도가 높다.

Code

언어 : JAVA

메모리 : 14512 kb

실행시간 : 116ms

package BOJ.Graph;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;


public class Gold3_17472_다리만들기2 {
    static int N, M;
    static int[][] map;

    static int[] dr = { -1, 1, 0, 0 };
    static int[] dc = { 0, 0, -1, 1 };

    static int[] parent;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        map = new int[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                map[i][j] = sc.nextInt();
                if (map[i][j] == 1)
                    map[i][j] = -1;
            }
        }

        // 맵 라밸링 맵의개수 파악
        int island = 1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == -1) {
                    DFS(i, j, island++);
                }
            }
        }

        // 간선의 비용 구하기
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2] - o2[2];
            }
        });

        for (int i = 1; i < island; i++) {
            for (int j = i + 1; j < island; j++) {
                int cost = getBridge(i, j);
                if (cost != 0)
                    pq.add(new int[] { i, j, cost });
            }
        }

        // makeSet
        parent = new int[island];
        for (int i = 1; i < island; i++) {
            parent[i] = i;
        }

        int ans = 0;
        // 다리선택 MST
        while (!pq.isEmpty()) {
            int[] now = pq.poll();
            int x = find(now[0]);
            int y = find(now[1]);
            if (x != y) {
                union(now[0], now[1]);
                ans += now[2];
            }
        }

        // 결과
        boolean flag = true;
        for (int i = 1; i < island; i++) {
            if (find(i) != 1) {
                flag = false;
                break;
            }
        }
        System.out.println(flag ? ans : -1);
    }

    private static void union(int i, int j) {
        int x = find(i);
        int y = find(j);

        if (x > y)
            parent[x] = y;
        else
            parent[y] = x;
    }

    private static int find(int i) {
        if (i == parent[i])
            return i;
        return parent[i] = find(parent[i]);
    }

    private static int getBridge(int start, int end) {
        boolean[][][] visit = new boolean[N][M][4];
        Queue<int[]> q = new LinkedList<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] != start)
                    continue;
                for (int k = 0; k < dr.length; k++) {
                    int r = i + dr[k];
                    int c = j + dc[k];
                    if (!isRange(r, c) || map[r][c] != 0)
                        continue;
                    q.add(new int[] { r, c, 0, k });
                    visit[r][c][k] = true;
                }
            }
        }

        int ret = 0;

        while (!q.isEmpty()) {
            int[] now = q.poll();
            if (map[now[0]][now[1]] == end) {
                if (now[2] == 1)
                    continue;
                ret = now[2];
                break;
            }
            int nr = now[0] + dr[now[3]];
            int nc = now[1] + dc[now[3]];

            if (isRange(nr, nc) && !visit[nr][nc][now[3]]
                    && (map[nr][nc] == 0 || map[nr][nc] == end)) {
                visit[nr][nc][now[3]] = true;
                q.add(new int[] { nr, nc, now[2] + 1, now[3] });
            }
        }

        return ret;
    }

    private static void DFS(int i, int j, int cnt) {
        map[i][j] = cnt;
        for (int k = 0; k < dc.length; k++) {
            int nr = i + dr[k];
            int nc = j + dc[k];
            if (isRange(nr, nc) && map[nr][nc] == -1) {
                DFS(nr, nc, cnt);
            }
        }
    }

    private static boolean isRange(int nr, int nc) {
        if (0 <= nr && nr < N && 0 <= nc && nc < M)
            return true;
        return false;
    }
}

[BOJ] 1922. 네트워크연결 - (Java)

Problem

제출일 : 2020-04-08

문제 풀이 시간 : 30M

난이도 : ★★★

---

link : https://www.acmicpc.net/problem/1922

도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.)

그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있을 것이다. 이제 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하라. 모든 컴퓨터를 연결할 수 없는 경우는 없다.

Input

첫째 줄에 컴퓨터의 수 N (1 ≤ N ≤ 1000)가 주어진다.

둘째 줄에는 연결할 수 있는 선의 수 M (1 ≤ M ≤ 100,000)가 주어진다.

셋째 줄부터 M+2번째 줄까지 총 M개의 줄에 각 컴퓨터를 연결하는데 드는 비용이 주어진다. 이 비용의 정보는 세 개의 정수로 주어지는데, 만약에 a b c 가 주어져 있다고 하면 a컴퓨터와 b컴퓨터를 연결하는데 비용이 c (1 ≤ c ≤ 10,000) 만큼 든다는 것을 의미한다. a와 b는 같을 수도 있다.

Output

모든 컴퓨터를 연결하는데 필요한 최소비용을 첫째 줄에 출력한다.

Example

input

6
9
1 2 5
1 3 4
2 3 2
2 4 7
3 4 6
3 5 11
4 5 3
4 6 8
5 6 8

output

23

Hint

이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다.

Solution & Inpression

유니온 파인드를 이용한 최소스패닝트리 알고리즘.

Code

언어 : JAVA

메모리 : 225564 kb

실행 시간 : 1100 ms

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

public class Main {
    static int N, M;
    static int[] parent;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        M = sc.nextInt();
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2] - o2[2];
            }
        });
        for (int i = 0; i < M; i++) {
            pq.offer(new int[] { sc.nextInt() - 1, sc.nextInt() - 1, sc.nextInt() });
        }

        parent = new int[N];
        for (int i = 0; i < N; i++) {
            parent[i] = i;
        }
        int ans = 0;
        while (!pq.isEmpty()) {
            int[] now = pq.poll();

            int a = find(now[0]);
            int b = find(now[1]);

            if (a == b)
                continue;

            union(a, b);
            ans += now[2];
        }
        System.out.println(ans);
    }

    private static void union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            if (x < y)
                parent[y] = x;
            else
                parent[x] = y;
        }
    }

    private static int find(int x) {
        if (x == parent[x])
            return x;
        return parent[x] = find(parent[x]);
    }
}

[BOJ] 2573. 빙산 - (Java)

Problem

제출일 : 2020-04-08

문제 풀이 시간 : 1H 30M

난이도 : ★★★

---

link : https://www.acmicpc.net/problem/2573

지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각한다.

그림 1. 행의 개수가 5이고 열의 개수가 7인 2차원 배열에 저장된 빙산의 높이 정보

빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다. 바닷물은 호수처럼 빙산에 둘러싸여 있을 수도 있다. 따라서 그림 1의 빙산은 일년후에 그림 2와 같이 변형된다.

그림 3은 그림 1의 빙산이 2년 후에 변한 모습을 보여준다. 2차원 배열에서 동서남북 방향으로 붙어있는 칸들은 서로 연결되어 있다고 말한다. 따라서 그림 2의 빙산은 한 덩어리이지만, 그림 3의 빙산은 세 덩어리로 분리되어 있다.

한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오. 그림 1의 빙산에 대해서는 2가 답이다. 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.

Input

첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다.

Output

첫 줄에 빙산이 분리되는 최초의 시간(년)을 출력한다. 만일 빙산이 다 녹을 때까지 분리되지 않으면 0을 출력한다.

Example

input

5 7
0 0 0 0 0 0 0
0 2 4 5 3 0 0
0 3 0 2 5 2 0
0 7 6 2 4 0 0
0 0 0 0 0 0 0

output

2

Solution & Inpression

빙산이 녹는 조건을 잘 읽자......

Code

언어 : JAVA

메모리 : 255480 kb

실행 시간 : 1092 ms

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int N, M;
    static int[][] map;
    static int[] dr = { -1, 1, 0, 0 };
    static int[] dc = { 0, 0, -1, 1 };

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        map = new int[N][M];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                map[i][j] = sc.nextInt();
            }
        }
        int ans = 0;
        while (true) {
            ans++;

            int[][] mel = new int[N][M];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (map[i][j] > 0) {
                        int m = 0;
                        for (int k = 0; k < dr.length; k++) {
                            int nr = i + dr[k];
                            int nc = j + dc[k];
                            if (isRange(nr, nc) && map[nr][nc] == 0)
                                m++;
                        }
                        mel[i][j] = m;
                    }
                }
            }

            Queue<int[]> q = new LinkedList<>();
            boolean[][] visit = new boolean[N][M];
            int count = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    map[i][j] -= mel[i][j];
                    if (map[i][j] < 0)
                        map[i][j] = 0;
                    else if (map[i][j] > 0) {
                        count++;
                        if (q.isEmpty()) {
                            q.offer(new int[] { i, j });
                            visit[i][j] = true;
                        }
                    }
                }
            }
            if (count == 0) {
                System.out.println(0);
                return;
            }
            int size = 1;
            while (!q.isEmpty()) {
                int[] now = q.poll();
                for (int k = 0; k < dr.length; k++) {
                    int nr = now[0] + dr[k];
                    int nc = now[1] + dc[k];
                    if (isRange(nr, nc) && map[nr][nc] > 0 && !visit[nr][nc]) {
                        visit[nr][nc] = true;
                        q.offer(new int[] { nr, nc });
                        size++;
                    }
                }
            }

            if (size != count) {
                System.out.println(ans);
                return;
            }
        }
    }

    private static boolean isRange(int nr, int nc) {
        if (0 <= nr && nr < N && 0 <= nc && nc < M)
            return true;
        return false;
    }
}

[BOJ] 10816. 숫자 카드 2 - (Java)

Problem

제출일 : 2020-04-02

문제 풀이 시간 : 30M

난이도 : ★★★

---

link : https://www.acmicpc.net/problem/10816

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

Input

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

Output

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

Example

input

10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

output

3 0 0 1 2 0 0 2

Solution & Inpression

upper_bound, lower_bound 연습문제

자바는 위 함수가 없기에 구현하여 문제를 해결하여야 합니다.

Code

언어 : JAVA

메모리 : 297116 kb

실행 시간 : 2164 ms

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N;
    static int card[];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        card = new int[N];
        for (int i = 0; i < N; i++) {
            card[i] = sc.nextInt();
        }
        Arrays.sort(card);
        int M = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            sb.append(check(sc.nextInt())).append(" ");
        }
        System.out.println(sb);
    }

    private static int check(int x) {
        int low = lower(x);
        int high = upper(x);
        return high - low + 1;
    }

    private static int upper(int x) {
        int s = 0, e = N;
        while (s < e) {
            int m = (s + e) >> 1;
            if (card[m] == x) {
                s = m + 1;
            } else if (card[m] > x) {
                e = m;
            } else
                s = m + 1;
        }
        return e;
    }

    private static int lower(int x) {
        int s = 0, e = N;
        while (s < e) {
            int m = (s + e) >> 1;
            if (card[m] == x) {
                e = m;
            } else if (card[m] > x) {
                e = m;
            } else
                s = m + 1;
        }
        return s + 1;
    }
}

[BOJ] 9012. 괄호 - (Java)

Problem

제출일 : 2020-04-02

문제 풀이 시간 : 15M

난이도 : ★★

---

link : https://www.acmicpc.net/problem/9012

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.

Input

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다.

Output

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다.

Example

input

6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(

output

NO
NO
YES
NO
YES
NO

Solution & Inpression

스택을 이용하여 해결

여는 괄호를 만났을 때 스택에 담고 닫히는 괄호를 만났을 때 스택의 크기를 확인하여 검사

최종적으로 스택이 비어있지 않다면 VPS가 아님.

Code

언어 : JAVA

메모리 : 14700 kb

실행 시간 : 124 ms

import java.util.LinkedList;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        for (int tc = 0; tc < N; tc++) {
            Stack<Character> stack = new Stack<>();

            String input = sc.next();
            boolean flag = true;
            for (int i = 0; i < input.length(); i++) {
                char now = input.charAt(i);
                if (now == '(')
                    stack.push(now);
                else if (now == ')') {
                    if (stack.size() > 0)
                        stack.pop();
                    else
                        flag = false;
                }
                if (!flag)
                    break;
            }
            if (stack.size() > 0)
                flag = false;
            sb.append(flag ? "YES\n" : "NO\n");
        } // end of TC
        System.out.println(sb);
    }
}

[BOJ] 2164. 카드2 - (Java)

Problem

제출일 : 2020-04-02

문제 풀이 시간 : 10M

난이도 : ★★

---

link : https://www.acmicpc.net/problem/2164

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

Input

첫째 줄에 정수 N(1≤N≤500,000)이 주어진다.

Output

첫째 줄에 남게 되는 카드의 번호를 출력한다.

Example

input

6

output

4

Solution & Inpression

삽입삭제가 빈번하게 일어나기 때문에 LinkedList를 사용

카드가 한장이 남을때 까지 반복하여 마지막 카드를 출력

Code

언어 : JAVA

메모리 : 45892kb

실행 시간 : 188ms

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        LinkedList<Integer> cards = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            cards.add(i);
        }
        while (cards.size() != 1) {
            cards.remove(0);
            cards.add(cards.get(0));
            cards.remove(0);
        }

        System.out.println(cards.get(0));
    }
}

[BOJ] 1920. 수 찾기 - (Java)

Problem

제출일 : 2020-04-02

문제 풀이 시간 : 20M

난이도 : ★★

---

link : https://www.acmicpc.net/problem/11650

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

Input

첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 $-2^{31}$ 보다 크거나 같고 $2^{31}$ 보다 작다.

Output

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

Example

input

5
4 1 5 2 3
5
1 3 7 9 5

output

1
1
0
0
1

Solution & Inpression

정렬 후 이분탐색

Code

언어 : JAVA

메모리 : 170092 kb

실행 시간 : 1164 ms

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N;
    static int[] data;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        data = new int[N];

        for (int i = 0; i < N; i++) {
            data[i] = sc.nextInt();
        }

        Arrays.sort(data);

        int M = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            if (find(sc.nextInt()))
                sb.append("1\n");
            else
                sb.append("0\n");
        }
        System.out.println(sb);
    }

    private static boolean find(int x) {
        int s = 0, e = N, m = 0;
        while (s < e) {
            m = (s + e) >> 1;
            if (data[m] == x)
                return true;
            else if (data[m] > x) {
                e = m;
            } else {
                s = m + 1;
            }
        }

        return false;
    }
}

[BOJ] 11650. 좌표 정렬하기 - (Java)

Problem

제출일 : 2020-04-02

문제 풀이 시간 : 10M

난이도 : ★★

---

link : https://www.acmicpc.net/problem/11650

2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

Input

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

Output

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

Example

input

5
3 4
1 1
1 -1
2 2
3 3

output

1 -1
1 1
2 2
3 3
3 4

Solution & Inpression

정렬조건을 Comparator을 이용하여 정의하여 Arrays.sort()함수를 이용하여 정렬뒤 출력하였습니다.

Code

언어 : JAVA

메모리 : 179020 kb

실행 시간 : 1352 ms

import java.awt.Point;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Silver5_11650_좌표정렬하기 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 점의 개수
        Point[] points = new Point[N];

        for (int i = 0; i < N; i++) {
            points[i] = new Point(sc.nextInt(), sc.nextInt());
        }

        Arrays.sort(points, new Comparator<Point>() {

            @Override
            public int compare(Point o1, Point o2) {
                if (o1.x != o2.x)
                    return o1.x - o2.x;
                else
                    return o1.y - o2.y;
            }
        });
        StringBuilder sb = new StringBuilder();
        for (Point point : points) {
            sb.append(point.x).append(" ").append(point.y).append("\n");
        }
        System.out.println(sb);
    }
}