www.acmicpc.net/problem/15654

 

15654번: N과 M (5)

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열

www.acmicpc.net

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 

 

N개의 자연수는 각각 다른 수로 직접 입력받는다.

 

출력하는 수열들의 순서는 오름차순으로 한다.

 

 

 

풀이.

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

public class Main {
    static BufferedReader br = null;
    static BufferedWriter bw = null;
    static StringTokenizer st = null;
    static StringBuilder sb = null;
    static boolean[] check = null;
    static int[] permu = null;
    static int[] num = null;
    static int n, m;

    public static void dfs(int dept, int deptNow) {
        if (dept == deptNow) {
            for (int i = 0; i < dept; i++) {
                sb.append(permu[i]).append(' ');
            }
            sb.append('\n');
            return;
        }

        for (int i = 0; i < n; i++) {
            if(check[i] == false) {
                permu[deptNow] = num[i];
                check[i] = true;
                dfs(dept, deptNow + 1);
                check[i] = false;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine());
        sb = new StringBuilder();
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        permu = new int[m + 1];
        num = new int[n];
        check = new boolean[n];

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            num[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(num);

        for (int i = 0; i < n; i++) {
            if(check[i] == false) {
                permu[0] = num[i];
                check[i] = true;
                dfs(m, 1);
                check[i] = false;
            }
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

 

이전 문제들과는 다르게 1~N의 수가 아니라 직접 입력받은 N개의 숫자로 수열을 만들어낸다.

중복을 허용하지 않으므로 boolean[] check 가 필요하다.

'알고리즘 문제 > 백준 온라인 저지' 카테고리의 다른 글

[BOJ] 15656 - N과 M (7) JAVA  (0) 2021.01.07
[BOJ] 15655 - N과 M (6) JAVA  (0) 2021.01.07
[BOJ] 15652 - N과 M (4) JAVA  (0) 2021.01.06
[BOJ] 15651 - N과 M (3) JAVA  (0) 2021.01.06
[BOJ] 15650 - N과 M (2) JAVA  (0) 2021.01.06

www.acmicpc.net/problem/15652

 

15652번: N과 M (4)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

1~N 의 자연수를 사용 하여 나타낼 수 있는 M자리 수열을 모두 출력해야한다. (숫자들의 중복 사용 허용)

단, 내림차순이 아닌 수열들만 출력한다.

출력하는 수열들의 순서는 사전 순 오름차순으로 한다.

 

 

codeung.tistory.com/54

 

[BJ] N과 M (3) JAVA

www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열

codeung.tistory.com

N과 M (3) 에서 '비 내림차순' 조건만 추가되었다.

 

 

 

풀이 .

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

public class Main {
    static BufferedReader br = null;
    static BufferedWriter bw = null;
    static StringTokenizer st = null;
    static StringBuilder sb = null;
    static int[] permu = null;
    static int n, m;

    public static boolean isNotDesc(int len) {
        for (int i = 0; i < len; i++) {
            if (permu[i] > permu[i + 1]) {
                return false;
            }
        }
        return true;
    }

    public static void dfs(int dept, int deptNow) {
        if (dept == deptNow) {
            for (int i = 0; i < dept; i++) {
                sb.append(permu[i]).append(' ');
            }
            sb.append('\n');
            return;
        }

        for (int i = 1; i <= n; i++) {
            permu[deptNow] = i;
            if (isNotDesc(deptNow)) {
                dfs(dept, deptNow + 1);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine());
        sb = new StringBuilder();
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        permu = new int[m + 1];

        for (int i = 1; i <= n; i++) {
            permu[0] = i;
            dfs(m, 1);
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

 

N과 M (3) 코드에서 isNotDesc() 하나만 추가되었다.

 

dfs를 재귀하기 전 검사를 통해 조건에 맞지 않는 수열로의 재귀를 막았다.

'알고리즘 문제 > 백준 온라인 저지' 카테고리의 다른 글

[BOJ] 15655 - N과 M (6) JAVA  (0) 2021.01.07
[BOJ] 15654 - N과 M (5) JAVA  (0) 2021.01.06
[BOJ] 15651 - N과 M (3) JAVA  (0) 2021.01.06
[BOJ] 15650 - N과 M (2) JAVA  (0) 2021.01.06
[BOJ] 15649 - N과 M (1) JAVA  (0) 2021.01.06

www.acmicpc.net/problem/15651

 

15651번: N과 M (3)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

1~N 의 자연수를 사용 하여 나타낼 수 있는 M자리 수열을 모두 출력해야한다. (숫자들의 중복 사용 허용)

수열들의 순서는 사전 순 오름차순으로 한다.

 

 

codeung.tistory.com/52

 

[BJ] N과 M (1) JAVA

www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열

codeung.tistory.com

이 문제에서 중복 허용으로 조건만 바꾼 문제.

 

 

 

풀이 1. (시간 초과)

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

public class Main {
    static BufferedReader br = null;
    static StringTokenizer st = null;

    // 한자리씩 사용하기 쉽도록 comb, numbers는 String으로 나타냈다
    public static void dfs(int dept, int deptNow, String comb, String numbers) {
        if (dept == deptNow) {
            System.out.println(comb);
            return;
        }

        for (int i = 0; i < numbers.length(); i++) {
            String temp = comb;
            comb += numbers.charAt(i) + " ";  // 출력 주의. 숫자 사이에 공백 넣어야 함

            dfs(dept, deptNow + 1, comb, numbers);

            // 백트래킹
            comb = temp;
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        String numbers = "";
        for (int i = 1; i <= n; i++) {
            numbers += String.valueOf(i);
        }

        for (int i = 0; i < n; i++) {
            char ch = numbers.charAt(i);
            String comb = String.valueOf(ch) + " ";
            dfs(m, 1, comb, numbers);
        }
    }
}

 

N과 M (1) 의 정답에서 check의 역할만 없애주었는데 시간 초과가 발생했다.

 

이전 코드의 문제점

 

1. 쓸데없이 String numbers를 사용했다. 

어차피 1~N의 "연속된" 숫자들을 사용하는 것이기 때문에 반복문의 i 로도 충분히 표현이 가능한데 굳이 String을 넘겨주도록 해서 부하를 증가시켰다.

 

2. System.out.println() 

테스트 케이스의 덩치가 꽤 컸는지 println을 사용하면 시간 초과가 발생했다. 

이러한 문제를 처음부터 피해버리기 위해 Scanner, println() 의 사용을 애초에 사용하지 않고 br, bw, sb의 사용을 생활화해야겠다.

 

 

 

풀이 2. (시간 초과)

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

public class Main {
    static BufferedReader br = null;
    static StringTokenizer st = null;
    static StringBuilder sb = null;

    public static void dfs(int dept, int deptNow, StringBuilder comb, String numbers) {
        if (dept == deptNow) {
            System.out.println(comb);
            return;
        }

        for (int i = 0; i < numbers.length(); i++) {
            comb.append(numbers.charAt(i));
            comb.append(" ");

            dfs(dept, deptNow + 1, comb, numbers);

            // 백트래킹
            comb.deleteCharAt(comb.length() - 1);  // 공백 제거
            comb.deleteCharAt(comb.length() - 1);  // 숫자 제거
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        sb = new StringBuilder();
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        String numbers = "";
        for (int i = 1; i <= n; i++) {
            numbers += String.valueOf(i);
        }

        for (int i = 0; i < n; i++) {
            sb.append(numbers.charAt(i));
            sb.append(" ");

            dfs(m, 1, sb, numbers);

            // 백트래킹
            sb.deleteCharAt(sb.length() - 1);  // 공백 제거
            sb.deleteCharAt(sb.length() - 1);  // 숫자 제거
        }
    }
}

 

sb를 사용하긴 했지만 여전히 시간초과가 발생했다.

 

코드의 문제점 

1. sb라고 만사형통은 아니다?

내 추측이지만 sb를 사용한 출력도 많이 사용하면 시간 소요가 큰 것 같았다.

 

 

 

풀이 3. (정답)

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

public class Main {
    static BufferedReader br = null;
    static BufferedWriter bw = null;
    static StringTokenizer st = null;
    static StringBuilder sb = null;
    static int[] permu = null;
    static int n, m;

    public static void dfs(int dept, int deptNow) {
        if (dept == deptNow) {
            for(int i = 0; i < dept; i++) {
                sb.append(permu[i]).append(' ');
            }
            sb.append('\n');
            return;
        }

        for (int i = 1; i <= n; i++) {
            permu[deptNow] = i;
            dfs(dept, deptNow + 1);
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine());
        sb = new StringBuilder();
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        permu = new int[m + 1];

        for (int i = 1; i <= n; i++) {
            permu[0] = i;
            dfs(m, 1);
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

 

sb 출력을 한 번만 해도 되는 식으로 고쳤다.

 

이전 코드는 dfs의 재귀를 이어나가며 sb.append() 를 하고 수열이 완성됐을 때마다 sb 출력을 실행했다.

바뀐 코드는 수열이 완성됐을 때 한꺼번에 sb.append() 하고 모든 dfs가 완료된 후에 sb 출력을 한 번만 실행한다.

 

 

 

 

배운 점

 

1. 백준에서 StringBuilder를 사용해 출력할 때 개행문자를 sb에 넣음으로써 모든 출력을 한 번의 출력만으로 완료할 수 있다.

 

2. Scanner, println을 멀리하자. 그냥 처음부터 br, bw, sb를 쓰자

 

'알고리즘 문제 > 백준 온라인 저지' 카테고리의 다른 글

[BOJ] 15655 - N과 M (6) JAVA  (0) 2021.01.07
[BOJ] 15654 - N과 M (5) JAVA  (0) 2021.01.06
[BOJ] 15652 - N과 M (4) JAVA  (0) 2021.01.06
[BOJ] 15650 - N과 M (2) JAVA  (0) 2021.01.06
[BOJ] 15649 - N과 M (1) JAVA  (0) 2021.01.06

www.acmicpc.net/problem/15650

 

15650번: N과 M (2)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

1~N 의 자연수를 사용 하여 나타낼 수 있는 중복되지 않는 M자리 수열을 모두 출력해야한다.

수열들의 순서는 사전 순 오름차순으로 한다.

단, 오름차순이 유지되는 수열만 출력한다.

 

 

 

풀이 .

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

public class Main {
    static BufferedReader br = null;
    static StringTokenizer st = null;
    static boolean[] check = null;

    public static boolean isAsc(String comb) {
        for(int i = 0; i < comb.length() - 1; i++) {
            if(comb.charAt(i) > comb.charAt(i + 1)) {
                return false;
            }
        }
        return true;
    }

    // 한자리씩 사용하기 쉽도록 comb, numbers는 String으로 나타냈다
    public static void dfs(int dept, int deptNow, String comb, String numbers) {
        if(dept == deptNow) {
            if(isAsc(comb)) {
                for(int i = 0; i < comb.length(); i++) {
                    System.out.print(comb.charAt(i) + " ");
                }
                System.out.println();
            }
            return;
        }

        for(int i = 0; i < numbers.length(); i++) {
            if(check[i] == false) {
                String temp = comb;
                comb += numbers.charAt(i);
                check[i] = true;

                dfs(dept, deptNow + 1, comb, numbers);

                // 백트래킹
                check[i] = false;
                comb = temp;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        check = new boolean[n];

        String numbers = "";
        for(int i = 1; i <= n; i++) {
            numbers += String.valueOf(i);
        }

        for(int i = 0; i < n; i++) {
            char ch = numbers.charAt(i);
            String comb = String.valueOf(ch);

            check[i] = true;
            dfs(m, 1, comb, numbers);

            // 백트래킹
            check[i] = false;
        }
    }
}

 

 

 

codeung.tistory.com/52

 

[BJ] N과 M (1) JAVA

www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열

codeung.tistory.com

이 문제에서 오름차순 수열만 출력한다는 조건만 추가된 문제.

 

isAsc() 를 통해 순열이 완성된 후 오름차순 여부만 추가로 체크해주었다.

 

이전 문제에서는 출력하기 전에 아예 comb를 갱신할 때부터 공백을 같이 넣어주었는데, 이 공백 때문에 isAsc() 가 제대로 동작하지 않았다.

 

공백을 출력부에서 처리하도록 바꿔주어 정답 처리 되었다.

 

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

isAsc 사용하지 말고 그냥 !check[i] 검사할 때 오름차순 검사까지 같이 해서 오름차순인것만 재귀하면 되잖아!

'알고리즘 문제 > 백준 온라인 저지' 카테고리의 다른 글

[BOJ] 15655 - N과 M (6) JAVA  (0) 2021.01.07
[BOJ] 15654 - N과 M (5) JAVA  (0) 2021.01.06
[BOJ] 15652 - N과 M (4) JAVA  (0) 2021.01.06
[BOJ] 15651 - N과 M (3) JAVA  (0) 2021.01.06
[BOJ] 15649 - N과 M (1) JAVA  (0) 2021.01.06

www.acmicpc.net/problem/15649

 

15649번: N과 M (1)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

1~N 의 자연수를 사용 하여 나타낼 수 있는 중복되지 않는 M자리 수열을 모두 출력해야한다.

수열들의 순서는 사전 순 오름차순으로 한다.

 

 

 

풀이 .

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

public class Main {
    static BufferedReader br = null;
    static StringTokenizer st = null;
    static boolean[] check = null;

    // 한자리씩 사용하기 쉽도록 comb, numbers는 String으로 나타냈다
    public static void dfs(int dept, int deptNow, String comb, String numbers) {
        if(dept == deptNow) {
            System.out.println(comb);
            return;
        }

        for(int i = 0; i < numbers.length(); i++) {
            if(check[i] == false) {
                String temp = comb;
                comb += numbers.charAt(i) + " ";  // 출력 주의. 숫자 사이에 공백 넣어야 함
                check[i] = true;

                dfs(dept, deptNow + 1, comb, numbers);

                // 백트래킹
                check[i] = false;
                comb = temp;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        check = new boolean[n];

        String numbers = "";
        for(int i = 1; i <= n; i++) {
            numbers += String.valueOf(i);
        }

        for(int i = 0; i < n; i++) {
            char ch = numbers.charAt(i);
            String comb = String.valueOf(ch) + " ";

            check[i] = true;
            dfs(m, 1, comb, numbers);

            // 백트래킹
            check[i] = false;
        }
    }
}

 

프로그래머스만 풀다가 백준을 풀려니 입출력이 매우 거슬렸다.

 

문제는 전형적인 백트래킹 문제이다.

 

숫자들을 한자리씩 사용하기 쉽도록 String 형태로 넘겨줬다.

 

처음엔 완성된 수열들을 배열에 담아서 정렬을 해야겠다고 생각했는데 생각해보니 어차피 순서대로 만들어지기 때문에 굳이 정렬할 필요도 없었고, 배열에 담을 필요 없이 완성되는 순간 바로 출력하도록 했다.

'알고리즘 문제 > 백준 온라인 저지' 카테고리의 다른 글

[BOJ] 15655 - N과 M (6) JAVA  (0) 2021.01.07
[BOJ] 15654 - N과 M (5) JAVA  (0) 2021.01.06
[BOJ] 15652 - N과 M (4) JAVA  (0) 2021.01.06
[BOJ] 15651 - N과 M (3) JAVA  (0) 2021.01.06
[BOJ] 15650 - N과 M (2) JAVA  (0) 2021.01.06

programmers.co.kr/learn/courses/30/lessons/49189

 

코딩테스트 연습 - 가장 먼 노드

6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3

programmers.co.kr

노드의 개수 int n, 각 노드의 연결 상태 int[][] edge 가 주어진다. (edge의 각 행 [a, b] 는 노드 a, b 사이가 연결되어있음을 뜻한다.)

 

시작 노드를 1번으로 하였을 때, 1번 노드에서 가장 멀리 떨어진 노드의 개수를 반환해야한다.

 

 

 

풀이 .

import java.util.*;

class Solution {

    ArrayList<Integer>[] list = null;
    boolean[] check = null;
    int[] dist = null;

    public void bfs(int start) {
        Queue<Integer> que = new LinkedList<>();
        que.add(start);
        check[start] = true;
        dist[start] = 1;

        while (!que.isEmpty()) {
            int now = que.poll();
            for (int i = 0; i < list[now].size(); i++) {
                int next = list[now].get(i);
                if (check[next] == false) {
                    que.add(next);
                    check[next] = true;
                    dist[next] = dist[now] + 1;
                }
            }
        }
    }

    public int solution(int n, int[][] edge) {
        int answer = 0;

        // 0번 인덱스는 무시하고 1번부터 사용
        list = new ArrayList[n + 1];
        check = new boolean[n + 1];
        dist = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            list[i] = new ArrayList<>();
        }

        for (int[] connect : edge) {
            int u = connect[0];
            int v = connect[1];
            list[u].add(v);
            list[v].add(u);
        }

        bfs(1);

        int max = 0;
        for(int d : dist) if(max < d) max = d;
        for(int d : dist) if(max == d) answer++;

        return answer;
    }
}

 

최단 거리, 최장 거리 문제는 웬만해선 BFS로 해결된다.

 

BFS 는 현재 노드에서 1만큼 떨어진 노드들을 우선적으로 탐색하기 때문에 시작 노드에서부터의 거리를 공평하게 잴 수 있다.

'알고리즘 문제 > 프로그래머스' 카테고리의 다른 글

[PG] 두 개 뽑아서 더하기 JAVA  (0) 2021.02.18
[PG] 크레인 인형뽑기 게임 JAVA  (0) 2021.02.18
[PG] 입국심사 JAVA  (0) 2021.01.04
[PG] 여행경로 JAVA  (0) 2021.01.04
[PG] 단어 변환 JAVA  (0) 2021.01.04

programmers.co.kr/learn/courses/30/lessons/43238

 

코딩테스트 연습 - 입국심사

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한

programmers.co.kr

입국심사를 받아야 하는 사람 수 int n, 심사관 별 심사 소요시간 int[] times 가 주어진다.

모든 사람이 입국심사를 마치기까지 걸리는 최소시간을 반환해야한다.

 

1. 한 심사대에서는 동시에 한 명만 심사를 할 수 있다.

2. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

 

 

 

풀이 .

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        Arrays.sort(times);

        long answer = (long)times[times.length - 1] * n;  // 최악의 경우 : n명 모두 최대시간으로 검사
        long max = (long)times[times.length - 1] * n;  // 최악의 경우 : n명 모두 최대시간으로 검사
        long min = 1;  // 최고의 경우 : 1초만에 모든 검사 끝

        while(min <= max) {  // 시간 범위를 점점 좁히다가 엇길리게 되면 답을 찾은 것임
            long mid = (min + max) / 2;

            long sum = 0;
            for(int time : times) {  // 각 심사관별로 mid 시간동안 몇 명을 검사할 수 있는지의 총합
                sum += mid / time;
            }

            if(sum >= n) {
                answer = Math.min(answer, mid);
                max = mid - 1;  // n명 이상 해결이 가능하다 -> 시간을 줄인다
            }else {
                min = mid + 1;  // n명까지 해결하지 못한다 -> 시간을 늘린다
            }
        }

        return answer;
    }
}

 

비슷한 풀이법을 떠올리지조차 못했다. 구글링을 통해 다른이의 코드를 이해만 하고 넘어간 수준이다.

 

문제를 처음 봤을 때 했던 생각은..

 

그냥 단순하게 시간을 나타내는 변수를 두고 반복을 돌리면서,

각 심사관들이 다음 심사를 하려면 시간이 얼마나 지나야 하는가를 계산해서,

사람들을 어느 심사관에게 배치할 것인지를 고르려고 했다.

 

막상 곧이곧대로 구현해보려니 쉽지도 않았고 완성했어도 시간초과가 났을 거다.

(이분탐색이라고 분류가 돼있는데도 이런 방법 밖에 생각하지 못했다.)

 

n과 times[]의 최대 원소의 최대값이 10억인 걸 보고 이분탐색, DP 등 시간을 아낄 수 있는 방식을 떠올릴 수 있어야 한다.

(완전탐색은 택도 없이 시간초과)

 

1. 엄청나게 큰 n을 보고 이분탐색을 떠올린다

2. 심사에 걸리는 시간을 반환하는 것 -> 시간을 조정해가며 심사관들이 해당 시간 내에 몇명이나 심사할 수 있는지 확인

3. 이분 탐색을 통해 시간을 절반씩 줄여나간다.

 

아마 for each 부분을 생각 해내는 게 핵심이지 않았을까 싶다. (주어진 시간 내에 모든 심사관이 계속해서 심사를 이어간다면 몇 명의 심사를 마칠 수 있는지)

 

 

 

너무 어렵다.

객관적으로 그렇게까지 어려운 문제는 아닌 거 같은데 그냥 나한테는 어려운 거 같아서 더 짜증난다.

'알고리즘 문제 > 프로그래머스' 카테고리의 다른 글

[PG] 크레인 인형뽑기 게임 JAVA  (0) 2021.02.18
[PG] 가장 먼 노드 JAVA  (0) 2021.01.06
[PG] 여행경로 JAVA  (0) 2021.01.04
[PG] 단어 변환 JAVA  (0) 2021.01.04
[PG] 네트워크 JAVA  (0) 2021.01.04

programmers.co.kr/learn/courses/30/lessons/43164

 

코딩테스트 연습 - 여행경로

[[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]] [ICN, ATL, ICN, SFO, ATL, SFO]

programmers.co.kr

항공권의 배열 String[][] tickets 가 주어진다. (항공권은 [출발지, 도착지] 로 되어있다)

주어진 항공권을 모두 사용하는 여행경로를 담은 배열을 반환해야한다.

 

1. 맨 처음 시작은 ICN 에서만 한다.

2. 항공권을 모두 사용하는 경로가 여러 개일 경우 알파벳 순서가 빠른 것을 정답으로 한다.

3. 정답이 없는 경우는 없다.

 

 

 

풀이 .

import java.util.*;

class Solution {
    boolean[] check = null;
    String[] answer = null;
    ArrayList<String> temp = null;

    public void dfs(int dept, String now, String[][] tickets) {
        // dept == 방문한 장소 개수 == 다음 장소 입력할 인덱스
        if(dept == tickets.length + 1) {
            if(answer[0] == null) {
                answer = temp.toArray(new String[tickets.length + 1]);
                return;
            }

            for(int i = 0; i < tickets.length + 1; i++) {
                if(answer[i].compareTo(temp.get(i)) == 0) {
                    continue;
                }else if(answer[i].compareTo(temp.get(i)) < 0) {
                    return;
                }else if(answer[i].compareTo(temp.get(i)) > 0) {  // 새로운 정답이 더 빠르면 교체
                    answer = temp.toArray(new String[tickets.length + 1]);
                    return;
                }
            }
        }

        for(int i = 0; i < tickets.length; i++) {
            if(check[i] == false && now.equals(tickets[i][0])) {
                check[i] = true;
                temp.set(dept, tickets[i][1]);
                dfs(dept + 1, tickets[i][1], tickets);
                check[i] = false;
            }
        }
    }

    public String[] solution(String[][] tickets) {
        answer = new String[tickets.length + 1];
        check = new boolean[tickets.length];
        temp = new ArrayList<>();

        // add 없이 set 하면 에러남
        for(int i = 0; i < tickets.length + 1; i++) {
            temp.add("");
        }

        // ICN 에서만 출발 가능
        for(int i = 0; i < tickets.length; i++) {
            if(tickets[i][0].equals("ICN")) {
                check[i] = true;
                temp.set(0, tickets[i][0]);
                temp.set(1, tickets[i][1]);
                dfs(2, tickets[i][1], tickets);
                check[i] = false;
            }
        }

        return answer;
    }
}

 

'단어 변환' 문제와 거의 유사한 문제.

 

똑같이 DFS, 백트래킹을 사용해서 풀었다.

 

백트래킹 할 때 ArrayList에 집어넣었던 경로를 빼는 게 불편해서 스택으로 바꿀까 싶었지만 ArrayList.set() 으로 해결했다.

set() 을 사용하면 집어넣을 인덱스를 지정할 수 있기 때문에 굳이 remove() 를 하지 않아도 된다.

'알고리즘 문제 > 프로그래머스' 카테고리의 다른 글

[PG] 가장 먼 노드 JAVA  (0) 2021.01.06
[PG] 입국심사 JAVA  (0) 2021.01.04
[PG] 단어 변환 JAVA  (0) 2021.01.04
[PG] 네트워크 JAVA  (0) 2021.01.04
[PG] 타겟 넘버 JAVA  (0) 2021.01.03

+ Recent posts