| 문제번호 | 제목 | 난이도 |
|---|---|---|
| 1759 | 암호 만들기 | 골드 5 |
| 16987 | 계란으로 계란치기 | 골드 5 |
1759번 암호 만들기
해결 코드:
import java.io.*;
import java.util.*;
/**
* 풀이 과정:
* - 고민과 풀이:
* 1-1. 일단 모음과 자음을 분리해서 리스트에 저장하자 -> 그냥 하나에 넣자
* 1-2. 위 방법 말고 그냥 하나의 리스트에 넣고 오름차순 정렬을 해주자
*
* 2. 재귀
* 2-1. 함수식 security(주어진 문자열 리스트, depth, 만들어진 문자열 + 현재 문자열)
* 2-2. base condition depth == L -> 현재 문자열에 모음이 한개이상 있는지, 자음이 두개이상 있는지 함수를 통해 체크해주자
* -> 만약 이 조건을 만족하면 StringBuilder에 넣어주고 종료하고, 아니면 그냥 조료한다
* 2-3. 재귀식 security(depth+1, 만들어진 문자열 + 현재문자열)
*
* - 문제 해결:
*
*
*
* 시간복잡도: O()
* 공간복잡도: O()
*
*/
public class Main {
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int L = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
List<String> code = new ArrayList<>();
for (int i = 0; i < C; i++) {
String input = st.nextToken();
code.add(input);
}
Collections.sort(code);
security(code, L, 0, "", 0);
bw.write(sb.toString());
br.close();
bw.close();
}
private static void security(List<String> code, int size, int depth, String total, int start) {
if(depth == size){
if(moOk(total, size) && zaOk(total, size)){
sb.append(total).append("\n");
}
return;
}
for (int i = start; i < code.size(); i++) {
security(code, size, depth+1, total + code.get(i), i+1);
}
}
private static boolean zaOk(String total, int size) {
int tmp = 0;
for (int i = 0; i < size; i++) {
if(total.charAt(i) != 'a' && total.charAt(i) != 'e' && total.charAt(i) != 'i' && total.charAt(i) != 'o' && total.charAt(i) != 'u'){
tmp++;
}
}
return tmp >= 2;
}
private static boolean moOk(String total, int size) {
for (int i = 0; i < size; i++) {
if(total.charAt(i) == 'a' || total.charAt(i) == 'e' || total.charAt(i) == 'i' || total.charAt(i) == 'o' || total.charAt(i) == 'u'){
return true;
}
}
return false;
}
}
학습 정리:
- 지금까지 N과 M 시리즈를 하면서 나온 부분을 모두 활용하면 쉽게 풀 수 있는 문제다.
고민의 시간:
- 처음에는 본능적으로 모음과 자음을 분리해서 따로 처리해야겠다고 생각했으나, 재귀식을 생각하다보니 분리하는 것보다는 그냥 하나로 통합해서 구분하는 것이 낫겠다고 풀이 방식을 바꾸게 되었다.
- 입력되는 문자들을 모두 리스트에 넣었고, 오름차순 출력을 위해 리스트를 정렬하였다.
- 깊이와 만들려는 문자열 크기인 L 을 이용하여 base condition을 만족시켰다.
- 추가로 total에다가는 지금까지 만들어진 문자열을 넣는 방식을 택했다.
- 이후 다시 푼 후에 정리할 Moo 게임에서는 이 방식을 사용할 수 없는 것과 대조대는 방식이다.
- 이 문제는 만들어지는 문자열의 크기가 한도없이 크게 늘어나지 않고, 1씩 증가하며 L의 크기에서 멈추기 때문에 메모리초과는 걱정하지 않아도 된다
- 하나의 수열에서 리스트의 이전 위치에 있는 값을 다시 탐색하는 암호는 만들면 안된다. 따라서 start라는 파라미터와 i+1라는 인수를 넘겨서 시작 위치를 새롭게 갱신하였다
- 종료조건에서 정답 문자열에 추가하는 조건을 두가지 추가한다. 문제에서 주어진 최소 모음 한개와 최소 자음 두개 조건이다.
- 해당 조건은 따로 메소드로 빼서 처리하였다. 최소 모음 한개 조건은 문자열을 순회하면서 모음이 있으면 true,없으면 false를 리턴한다
- 최소 자음 두개 조건은 tmp라는 임시 변수를 선언하여 모음이 아닌 경우 자음이므로, 자음인 경우가 발견되면 tmp++를 해준다.
- 순회 종료 후에는 tmp값이 2이상이냐 아니냐에 따라 true와 false를 리턴하도록 한다
- 이러한 방식으로 진행된다면 수학적 귀납법에 의해 원하는 암호가 출력됨을 확인할 수 있다.
16987번 계란으로 계란치기
해결 코드:
import java.io.*;
import java.util.*;
/**
* 고민과 풀이:
*
* 문제 해결:
*
*
* 시간복잡도: O()
* 공간복잡도: O()
*
*
*/
class Egg{
int weight;
int power;
public Egg(int weight, int power) {
this.weight = weight;
this.power = power;
}
}
public class Main {
static Egg[] eggs;
static int count = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
eggs = new Egg[n];
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
eggs[i] = new Egg(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
}
eggToEgg(0, n, 0);
bw.write(count+"");
br.close();
bw.close();
}
private static void eggToEgg(int now, int n, int total) {
if(now == n || total == n-1){
count = Math.max(count, total);
return;
}
if(eggs[now].weight <= 0){
eggToEgg(now+1, n, total);
}else{
for (int i = 0; i < n; i++) {
if(now != i && eggs[i].weight > 0){
eggs[now].weight -= eggs[i].power;
eggs[i].weight -= eggs[now].power;
eggToEgg(now+1, n, total + eggResult(now, i));
eggs[now].weight += eggs[i].power;
eggs[i].weight += eggs[now].power;
}
}
}
}
private static int eggResult(int now, int i) {
int tmp = 0;
if(eggs[now].weight <=0 ){
tmp++;
}
if(eggs[i].weight <= 0){
tmp++;
}
return tmp;
}
}학습 정리:
고민의 시간:
- C++에는 Pair라는 좋은 라이브러리가 있지만 자바에는 없다. 하지만 자바는 더 확장할 수 있는 클래스가 있다
- 계란에는 속성이 존재한다. 내구도와 무게이다. 이를 속성으로 각각 weight, power로 지정했다
- 그리고 클래스를 담을 배열을 선언해서 입력값들을 담아주었다
- 이제 재귀식을 생각해야한다. 가장 왼쪽부터 시작해서 마지막 오른쪽을 집으면 끝나므로, 위치를 나타낼 now와 끝을 나타낼 n을 파라미터로 선언하였다
- 그다음 각 계란치기마다 깨진 개수를 체크할 것이다. 재귀로 쭉 그 개수가 이어지면서 내려오는 백트래킹 방법을 사용할 것이기 때문에 total을 파라미터로 지정하였다
- 종료조건은 현재위치인 now와 끝을 나타내는 n이랑 같을 경우거나 다른 계란이 다 깨지고 딱 한개만 남은 경우이다. 전자는 3번 조건에서 명시해줬으나 후자는 2번 조건에서 유추해서 종료조건에 추가해야한다
- 종료조건에서는 가장 많이 깨진 계란의 개수를 count에 넣도록 Math.max를 활용하였다. 여러 백트래킹으로 내려온 total중 가장 많은 개수가 count에 저장될 것이다.
- 이어서 재귀함수를 실행시킬 조건을 생각했다. 먼저 현재 계란이 깨져있으면 그대로 스킵을 해야하는데, 이때 재귀함수를 실행시키지 않고 그냥 return;해서 종료한다면 백트래킹이 깨지게된다
- 따라서 total에 추가적인 값을 추가하지 않도록 그냥 total을 인수로 넘겨주는 재귀함수를 실행한다
- 만약 깨져있지 않다면, 이제 n만큼 순회를 시작한다. 만약 순회하는 현재의 께란이 깨져있지 않고 now가 i랑 같은 경우(자기 자신을 가리키는 경우)에 다음을 수행한다
- 먼저 서로의 내구도를 power만큼 깎는다.
- 그리고 이제 깨진 계란의 개수를 확인하는 메소드를 실행시켜서 그 값만큼 total에 추가해서 백트래킹을 해준다.
- 이렇게 하면 여러 가지가 나올 것이고, 수학적 귀납법에 의해 원하는 결과를 얻을 수 있을 것이다.
- 이후에, 다시 내구도를 power만큼 복원시켜서 다음 백트래킹에서 해당 계란을 계란치기 할 수 있도록 한다
- 마치 11 ~ 14번은 N과 M시리즈의 visited 배열을 사용해서 방문 배열을 true로 한 뒤, 재귀함수 실행하고 다시 방문 체크를 false로 하는 방식과 유사하다
- 완성된 count를 출력하면 원하는 결과를 얻을 수 있다.
Software Developer