## 과제 : 백준 문제 풀이

목표 : 백준 문제를 풀어본다.

- [다음 순열](https://www.acmicpc.net/problem/10972)
- [암호 만들기](https://www.acmicpc.net/problem/1759)
- [거스름돈](https://www.acmicpc.net/problem/5585)
- [회의실 배정](https://www.acmicpc.net/problem/1931)

### 추가 문제

- [동전 0](https://www.acmicpc.net/problem/11047)
- [ATM](https://www.acmicpc.net/problem/11399)
- [잃어버린 괄호](https://www.acmicpc.net/problem/1541)

---

## 과제 : 백준 문제 풀이 모범답안

### 다음 순열

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 사용자로부터 순열의 길이 N을 입력받음
        int[] permutation = new int[N]; // 순열을 저장할 배열 선언
        for (int i = 0; i < N; i++) {
            permutation[i] = sc.nextInt(); // 순열의 요소를 하나씩 입력받음
        }
        
        if (nextPermutation(permutation)) {
            for (int i = 0; i < N; i++) {
                System.out.print(permutation[i] + " "); // 다음 순열을 출력
            }
        } else {
            System.out.println("-1"); // 다음 순열이 없는 경우 -1 출력
        }
    }
    
    public static boolean nextPermutation(int[] array) {
        int i = array.length - 1;
        // 뒤쪽부터 탐색하여 처음으로 a[i-1] < a[i]를 만족하는 i를 찾음
        while (i > 0 && array[i-1] >= array[i]) i--;
        
        // 마지막 순열인 경우 false 반환
        if (i <= 0) return false;
        
        int j = array.length - 1;
        // a[i-1]보다 큰 첫 번째 값을 뒤에서부터 찾음
        while (array[j] <= array[i-1]) j--;
        
        // a[i-1]과 a[j]를 교환
        int temp = array[i-1];
        array[i-1] = array[j];
        array[j] = temp;
        
        // i 위치부터 끝까지를 오름차순으로 정렬
        j = array.length - 1;
        while (i < j) {
            temp = array[i];
            array[i] = array[j];
            array[j] = temp;
            i++;
            j--;
        }
        
        // 다음 순열을 성공적으로 생성하였으므로 true 반환
        return true;
    }
}

### 암호 만들기

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

public class Main {
    static int L, C; // L은 암호의 길이, C는 주어진 문자의 개수
    static char[] candidates, password; // 사용 가능한 문자들과 암호를 저장할 배열
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        L = sc.nextInt();
        C = sc.nextInt();
        candidates = new char[C]; // 사용 가능한 문자들을 저장할 배열
        password = new char[L]; // 생성된 암호를 저장할 배열
        
        for (int i = 0; i < C; i++) {
            candidates[i] = sc.next().charAt(0); // 문자를 하나씩 입력받아 배열에 저장
        }
        
        Arrays.sort(candidates); // 사전 순으로 문자를 정렬
        generatePassword(0, 0); // 암호 생성 시작
    }
    
    public static void generatePassword(int start, int depth) {
        if (depth == L) {
            if (isValid(password)) { // 생성된 암호가 조건을 만족하는지 확인
                System.out.println(password); // 조건을 만족하는 암호 출력
            }
            return;
        }
        
        for (int i = start; i < C; i++) {
            password[depth] = candidates[i]; // 현재 위치에 문자를 설정
            generatePassword(i + 1, depth + 1); // 다음 문자를 설정하기 위해 재귀 호출
        }
    }
    
    public static boolean isValid(char[] arr) {
        int vowels = 0; // 모음의 개수
        int consonants = 0; // 자음의 개수
        for (char c : arr) {
            // 모음인지 자음인지 확인하여 각각의 개수를 셈
            if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                vowels++;
            } else {
                consonants++;
            }
        }
        // 최소 한 개의 모음과 최소 두 개의 자음이 포함되어 있는지 확인
        return vowels >= 1 && consonants >= 2;
    }
}

### 거스름돈

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int payment = sc.nextInt(); // 지불 금액 입력
        int change = 1000 - payment; // 거스름돈 총액 계산

        int[] coins = {500, 100, 50, 10, 5, 1}; // 화폐 단위 배열
        int coinCount = 0; // 거슬러줄 동전 개수

        for (int coin : coins) {
            coinCount += change / coin; // 해당 화폐로 거슬러 줄 수 있는 최대 동전 개수 누적
            change %= coin; // 남은 거스름돈 갱신

            if (change == 0) break; // 거스름돈이 없으면 종료
        }

        System.out.println(coinCount); // 거슬러 줄 동전 개수 출력
    }
}

### 회의실 배정

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 회의의 수 입력
        int[][] meetings = new int[N][2]; // 회의 정보 저장 배열

        for (int i = 0; i < N; i++) {
            meetings[i][0] = sc.nextInt(); // 시작 시간
            meetings[i][1] = sc.nextInt(); // 종료 시간
        }

        // 회의 종료 시간 기준 정렬, 종료 시간이 같다면 시작 시간 기준 정렬
        Arrays.sort(meetings, (a, b) -> {
            if (a[1] == b[1]) return a[0] - b[0];
            return a[1] - b[1];
        });

        int count = 0;
        int currentTime = 0;
        
        for (int i = 0; i < N; i++) {
            int[] meeting = meetings[i];
            if (meeting[0] >= currentTime) {
                currentTime = meeting[1];
                count++;
            }
        }
        
        System.out.println(count); // 사용할 수 있는 회의의 최대 개수 출력
    }
}

### 동전 0

import java.util.Scanner;

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

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

        int count = 0;
        for (int i = N - 1; i >= 0; i--) {
            if (coins[i] <= K) {
                count += K / coins[i];
                K %= coins[i];
            }
        }

        System.out.println(count);
    }
}

### ATM

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

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

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

        Arrays.sort(times);

        int total = 0;
        int sum = 0;
        for (int time : times) {
            sum += time;
            total += sum;
        }

        System.out.println(total);
    }
}

### 잃어버린 괄호

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] substractions = sc.nextLine().split("-");

        int result = 0;
        for (int i = 0; i < substractions.length; i++) {
            int temp = 0;

            String[] addition = substractions[i].split("\\+");
            for (String val : addition) {
                temp += Integer.parseInt(val);
            }

            if (i == 0) result += temp;
            else result -= temp;
        }

        System.out.println(result);
    }
}