[BOJ] 10814. 나이순 정렬 - (Java)

Problem

제출일 : 2020-04-02

문제 풀이 시간 : 10M

난이도 : ★★

---

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

온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.

Input

첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다.

Output

첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다.

Example

input

3
21 Junkyu
21 Dohyun
20 Sunyoung

output

20 Sunyoung
21 Junkyu
21 Dohyun

Solution & Inpression

나이를 오름차순으로 정렬하여 출력... Class를 만들어 User를 저장하는 객체를 생성 Comparable을 이용하여 정렬조건을 정의하여 문제를 해결하였습니다.

Code

언어 : JAVA

메모리 : 147412 kb

실행 시간 : 1832 ms

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

public class Silver5_10814_나이순정렬 {
    static class User implements Comparable<User> {
        int age;
        String name;

        public User(int age, String name) {
            super();
            this.age = age;
            this.name = name;
        }

        @Override
        public int compareTo(User o) {
            return this.age - o.age;
        }

        @Override
        public String toString() {
            return age + " " + name;
        }

    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        User[] users = new User[N];
        for (int i = 0; i < N; i++) {
            users[i] = new User(sc.nextInt(), sc.next());
        }

        Arrays.sort(users);

        for (User user : users) {
            System.out.println(user);
        }
    }
}

[BOJ] 2751. 수 정렬하기 2 - (Java)

Problem

제출일 : 2020-04-02

문제 풀이 시간 : 10M

난이도 : ★★

---

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

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

Input

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

Output

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

Example

input

5
5
4
3
2
1

output

1
2
3
4
5

Solution & Inpression

Arrays.sort() >> 시간초과,

BufferedReader >> 시간초과,

정렬알고리즘을 구현하여 문제를 해결해야 하나 고민하다 그냥 값의 범위만큼 배열을 만들어 각 위치에 저장한뒤 순서대로 StringBuilder을 이용하여 값을 출력했다.

이때 주의해야할 점이 값의 범위가 절대값이 1,000,000 보다 작거나 같은 정수이기때문에 범위에 음수가 포함된다.

저장할때 음수를 제거하기위해 +1000000을 수행했고 출력할때 -1000000을 한뒤 원상복구후 출력하였습니다.

Code

언어 : JAVA

메모리 : 126104 kb

실행 시간 : 676 ms

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        boolean[] data = new boolean[2000001];

        for (int i = 0; i < N; i++) {
            data[Integer.parseInt(br.readLine()) + 1000000] = true;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < data.length; i++) {
            if (data[i])
                sb.append(i - 1000000).append('\n');
        }
        System.out.println(sb);
    }
}

[BOJ] 1181. 단어정렬 - (Java)

Problem

제출일 : 2020-04-02

문제 풀이 시간 : 30M

난이도 : ★★

---

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

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

Input

첫째 줄에 단어의 개수 N이 주어진다. (1≤N≤20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

Output

조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다

Example

input

13
but
i
wont
hesitate
no
more
no
more
it
cannot
wait
im
yours

output

i
im
it
no
but
more
wait
wont
yours
cannot
hesitate

Solution & Inpression

Set을 이용하여 중복을 제거한 뒤 ArrayList에 옮겨 정렬하였습니다

정렬은 Comparator을 이용하여 문제에 조건에 따라 재정의 하였습니다.

Code

언어 : JAVA

메모리 : 35944 kb

실행 시간 : 720 ms

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Silver5_1181_단어정렬 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        Set<String> set = new HashSet<>();
        for (int i = 0; i < N; i++) {
            set.add(sc.next());
        }
        ArrayList<String> data = new ArrayList<>(set);
        Collections.sort(data, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if (o1.length() != o2.length())
                    return o1.length() - o2.length();
                else
                    return o1.compareTo(o2);
            }
        });
        for (String string : data) {
            System.out.println(string);
        }
    }
}

[BOJ] 2798. 블랙잭 - (Java)

제출일 : 2020-04-01

문제 풀이 시간 : 10M

난이도 : ★

---

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

문제

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.

한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.

김정인 버젼의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.

이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.

N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

입력

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는다.

합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.

예제

입력

5 21
5 6 7 8 9

출력

21

해결방안

조합을 이용하여 문제를 해결하였습니다. 조합의 결과가 M 이하이고 현재보다 값이 크다면 갱신하여 최종적인 답을 구했습니다.

코드

언어 : JAVA

메모리 : 14616 kb

실행 시간 : 124 ms

package BOJ.BF;
import java.util.Scanner;

public class Bronze2_2798_블랙잭 {
    static int N, M, ans;
    static int[] card;
    static boolean[] visit;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        card = new int[N];
        visit = new boolean[N];
        for (int i = 0; i < N; i++) {
            card[i] = sc.nextInt();
        }
        ans = -1;
        solve(0, 0, 0);
        System.out.println(ans);
    }

    private static void solve(int index, int depth, int sum) {
        if (depth == 3) {
            if (sum <= M && ans < sum)
                ans = sum;
            return;
        }
        for (int i = index; i < N; i++) {
            if (!visit[i]) {
                visit[i] = true;
                solve(i, depth + 1, sum + card[i]);
                visit[i] = false;
            }
        }

    }
}

[BOJ] 12851. 숨바꼭질2 - (Java)

Problem

제출일 : 2020-03-22

문제 풀이 시간 : 1H 30M

난이도 : ★★

---

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

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

Output

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에는 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다.

Example

input

8 9 10

output

1 2 8 9 10

Solution & Inpression

같은 점을 중복으로 방문을 가능하게 하기 위해 q에서 값을 뺄 때 방문 처리를 해주었음.

Code

언어 : JAVA

메모리 : 48664 kb

실행 시간 : 236 ms

package BOJ.DFS_BFS;

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

public class Gold5_12851_숨바꼭질2 {
    static int N, K;

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

        boolean[] visited = new boolean[100001];
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] { N, 0 });
        visited[N] = true;

        int[] next = new int[3];
        int time = Integer.MAX_VALUE;
        int count = 0;

        while (!q.isEmpty()) {
            int[] now = q.poll();

            if (now[1] > time)
                continue;
            else if (now[0] == K) {
                if (time > now[1]) {
                    time = now[1];
                    count = 1;
                } else if (time == now[1])
                    count++;
            }

            visited[now[0]] = true;

            next[0] = now[0] - 1;
            next[1] = now[0] + 1;
            next[2] = now[0] << 1;

            for (int i = 0; i < 3; i++) {
                if (0 <= next[i] && next[i] <= 100000 && !visited[next[i]])
                    q.add(new int[] { next[i], now[1] + 1 });
            }
        }
        System.out.println(time);
        System.out.println(count);
    }

}

[BOJ] 2251. 물통 - (Java)

Problem

제출일 : 2020-03-22

문제 풀이 시간 : 30M

난이도 : ★★

---

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

각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.

이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.

Input

첫째 줄에 세 정수 A, B, C가 주어진다.

Output

첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.

Example

input

8 9 10

output

1 2 8 9 10

Solution & Inpression

물통의 물을 옮기는 방법

from A to B

from A to C

from B to A

from B to C

from C to A

from C to B

모든 경우를 BFS 탐색 Set을 이용하여 중복을 제거한 뒤 List로 옮겨 정렬 후 출력

Code

언어 : JAVA

메모리 : 23520 kb

실행 시간 : 112 ms

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

public class Main {
    static int[] input;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        input = new int[3];
        input[0] = sc.nextInt();
        input[1] = sc.nextInt();
        input[2] = sc.nextInt();

        Queue<int[]> q = new LinkedList<>();
        Set<Integer> set = new HashSet<>();
        boolean[][][] visit = new boolean[input[0] + 1][input[1] + 1][input[2] + 1];
        visit[0][0][input[2]] = true;
        set.add(input[2]);
        q.offer(new int[] { 0, 0, input[2] });

        while (!q.isEmpty()) {
            int[] now = q.poll();
            if (now[0] == 0) {
                set.add(now[2]);
            }

            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    if (i == j)
                        continue;
                    int[] next = solve(now, i, j);
                    if (!visit[next[0]][next[1]][next[2]]) {
                        visit[next[0]][next[1]][next[2]] = true;
                        q.offer(next);
                    }
                }
            }
        }

        ArrayList<Integer> ans = new ArrayList<>(set);
        Collections.sort(ans);
        StringBuilder sb = new StringBuilder();
        for (Integer i : ans) {
            sb.append(i).append(" ");
        }
        System.out.println(sb);
    }

    private static int[] solve(int[] now, int i, int j) {
        if (now[i] == 0 || now[j] == input[j]) {
            return now;
        }

        // from i to j;
        int[] next = now.clone();
        int tmp = input[j] - next[j];
        if (next[i] > tmp) {
            next[j] += tmp;
            next[i] -= tmp;
        } else {
            next[j] += next[i];
            next[i] = 0;
        }

        return next;
    }
}

[BOJ] 1525. 퍼즐- (Java)

Problem

제출일 : 2020-03-22

문제 풀이 시간 : 1H 30M

난이도 : ★★★

---

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

3×3 표에 다음과 같이 수가 채워져 있다. 오른쪽 아래 가장 끝 칸은 비어 있는 칸이다.

어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있으면, 수를 그 칸으로 이동시킬 수가 있다. 물론 표 바깥으로 나가는 경우는 불가능하다. 우리의 목표는 초기 상태가 주어졌을 때, 최소의 이동으로 위와 같은 정리된 상태를 만드는 것이다. 다음의 예를 보자.

가장 윗 상태에서 세 번의 이동을 통해 정리된 상태를 만들 수 있다. 이와 같이 최소 이동 횟수를 구하는 프로그램을 작성하시오.

Input

세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다.

Output

첫째 줄에 최소의 이동 횟수를 출력한다. 이동이 불가능한 경우 -1을 출력한다.

Example

input

1 0 3
4 2 5
7 8 6

output

3

Solution & Inpression

맵의 상태를 정수형으로 변환 Set자료구조를 이용한 방문 확인

Code

언어 : JAVA

메모리 : 63944 kb

실행 시간 : 688 ms

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

public class Gold3_1525_퍼즐 {
    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);
        int map = 0;
        int[] start = new int[2];
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                int tmp = sc.nextInt();
                map *= 10;
                map += tmp;
                if (tmp == 0) {
                    map += 9;
                    start[0] = i;
                    start[1] = j;
                }
            }
        }
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] { map, start[0], start[1], 0 });
        Set<Integer> set = new TreeSet<>();
        set.add(map);
        while (!q.isEmpty()) {
            if (q.peek()[0] == 123456789) {
                System.out.println(q.peek()[3]);
                System.exit(0);
            }

            char[] now = ("" + q.peek()[0]).toCharArray();
            int r = q.peek()[1];
            int c = q.peek()[2];
            int cnt = q.peek()[3];
            q.poll();

            for (int k = 0; k < dr.length; k++) {
                int nr = r + dr[k];
                int nc = c + dc[k];
                if (isRange(nr, nc)) {
                    int next = getNext(now, r * 3 + c, nr * 3 + nc);
                    if (!set.contains(next)) {
                        set.add(next);
                        q.offer(new int[] { next, nr, nc, cnt + 1 });
                    }
                }
            }
        }
        System.out.println(-1);
    }

    private static int getNext(char[] now, int i, int j) {
        char tmp = now[i];
        now[i] = now[j];
        now[j] = tmp;
        int ret = 0;
        for (char c : now) {
            ret *= 10;
            ret += c - '0';
        }
        tmp = now[i];
        now[i] = now[j];
        now[j] = tmp;
        return ret;
    }

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

}

[BOJ] 1175. 배달 - (Java)

Problem

제출일 : 2020-03-21

문제 풀이 시간 : 3H

난이도 : ★★★

---

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

어제 선물을 모두 포장한 민식이는 이제 선물을 배달하려고 한다. 민식이가 선물을 배달할 곳은 이 문제를 읽는 사람들이 앉아 있는 교실이다. 교실은 직사각형모양이고, 모두 같은 크기의 정사각형 블록으로 나누어져 있다.

입력으로 교실의 지도가 주어진다. 각각의 정사각형 블록은 다음과 같이 4가지 종류가 있다.

• S : 지금 민식이가 있는 곳이다. 이곳이 민식이가 배달을 시작하는 곳이다.
• C : 민식이가 반드시 선물을 배달해야 하는 곳이다. 이러한 블록은 정확하게 2개 있다.
• # : 민식이가 갈 수 없는 곳이다.
• . : 민식이가 자유롭게 지나갈 수 있는 곳이다.

민식이가 한 블록 동서남북으로 이동하는데는 1분이 걸린다. 민식이는 네가지 방향 중 하나로 이동할 수 있으며, 교실을 벗어날 수 없다. 민식이가 선물을 배달해야 하는 곳에 들어갈 때, 민식이는 그 곳에 있는 사람 모두에게 선물을 전달해야 한다. 이 상황은 동시에 일어나며, 추가적인 시간이 소요되지 않는다.

민식이는 어느 누구도 자신을 보지 않았으면 하기 때문에, 멈추지 않고 매 시간마다 방향을 바꿔야 한다. 이 말은 같은 방향으로 두 번 연속으로 이동할 수 없다는 말이다. 민식이가 선물을 모두 배달하는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

Input

첫째 줄에 교실의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 교실의 지도가 주어진다.

Output

첫째 줄에 민식이가 선물을 모두 배달하는데 걸리는 시간의 최솟값을 출력한다. 만약 불가능 할 때는 -1을 출력한다.

Example

input

2 3
SCC
...

output

4

Solution & Inpression

visit[r][c][status][dir] 방향과 상태를 포함하여 방문처리하여 문제 해결

Code

언어 : JAVA

메모리 : 20068 kb

실행 시간 : 168 ms

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

public class Main {
    static int N, M;
    static char[][] map;
    static int[][] point;

    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 char[N][M];
        point = new int[3][2];
        int idx = 1;
        for (int i = 0; i < N; i++) {
            String str = sc.next();
            for (int j = 0; j < M; j++) {
                map[i][j] = str.charAt(j);
                if (map[i][j] == 'S') {
                    point[0][0] = i;
                    point[0][1] = j;
                    map[i][j] = '.';
                } else if (map[i][j] == 'C') {
                    point[idx][0] = i;
                    point[idx++][1] = j;
                    map[i][j] = '.';
                }
            }
        }

        Queue<int[]> q = new LinkedList<>();
        // visit[r][c][status][dir]
        boolean[][][][] visit = new boolean[N][M][3][4];

        for (int i = 0; i < 4; i++) {
            visit[point[0][0]][point[0][1]][0][i] = true;
        }

        q.offer(new int[] { point[0][0], point[0][1], -1, 0, 0 });
        while (!q.isEmpty()) {
            int r = q.peek()[0];
            int c = q.peek()[1];
            int dir = q.peek()[2];
            int cnt = q.peek()[3];
            int status = q.peek()[4];
            q.poll();

            if (r == point[1][0] && c == point[1][1]) { // 1번 도착
                status |= 1;
            } else if (r == point[2][0] && c == point[2][1]) { // 2번 도착
                status |= 2;
            }

            if (status == 3) {
                System.out.println(cnt);
                System.exit(0);
            }

            for (int k = 0; k < dr.length; k++) {
                if (k == dir)
                    continue;
                int nr = r + dr[k];
                int nc = c + dc[k];
                if (isRange(nr, nc) && !visit[nr][nc][status][k] && map[nr][nc] == '.') {
                    visit[nr][nc][status][k] = true;
                    q.offer(new int[] { nr, nc, k, cnt + 1, status });
                }
            }
        }
        System.out.println(-1);
    }

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