반응형
이해가 되지않아 자세한 도움이 필요하거나 오류가 있는 경우 댓글을 남겨주세요.
문제
풀이
- 브루트 포스를 통해 조합을 만들어내는 문제.
- 문제 파악은 읽으면서, index를 백트레킹에 넣지 않아 시도횟수 증가.
모든 문제는 꼼꼼히 읽고 집중을 해서 풀자. - String의 경우 연산이 많이 읽어나는 경우 효율이 떨어지지만, 시간제한이 2sec로 넉넉한 편이어서 가독성이 좋은 코드로 작성을 했다.
과정
- 입력받은 알파벳들을 사전순으로 정렬(Arrays.sort 사용).
- index 번호와 문자열을 파라미터로 가지는 dfs 호출.
- 기저 조건은 문자열의 길이가 L이 되는 경우와 자음2개, 모음 1개이상으로 이루어진 경우.
- 자음 2개와 모음 1개의 검사는 contains, replace와 length를 활용.
ex) 모음을 한개 이상 포함, 모든 모음을 공백으로 변경 후 길이가 2이상인 경우 true. - index가 배열의 범위를 넘는 경우 리턴.
- 문자열에 현재 인덱스의 알파벳을 붙여서 dfs 호출.
- 문자욜에 현재 인덱스를 건너뛰어 dfs 호출.
- 3번의 경우에 부합한 경우 암호로 판단 풀력.
알고리즘 지식
- 브루트포스
- 조합
- 백트래킹
JAVA코드
package BaekJoon_2020_12_30__2021_01_06;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
/**
* @packageName : BaekJoon_2020_12_30__2021_01_06
* @fileName : BJ_1759_암호만들기.java
* @author : Mingeon
* @date : 2020. 12. 31.
* @language : JAVA
* @classification : 브루트포스 알고리즘, 조합론, 백트래킹
* @time_limit : 2sec
* @required_time : 14:00 ~ 14:48
* @submissions : 3
* @description
*/
public class BJ_1759_암호만들기 {
static int L; // 암호의 길이
static int C; // 문자들의 갯수
static char[] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
L = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
arr = new char[C];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < C; i++) {
arr[i] = st.nextToken().charAt(0);
} // End of input
// 사전순을 위한 정렬
Arrays.sort(arr);
dfs(0, "");
}
private static String dfs(int idx, String str) {
if (str.length() == L && isValid(str)) {
System.out.println(str);
return str;
}
if (idx >= C) {
return str;
}
// 현재 인덱스 포함
dfs(idx + 1, str + arr[idx]);
// 현재 인덱스 스킵
dfs(idx + 1, str);
return str;
}
// 모음 1개 이상, 자음 2개 이상 포함 확인
private static boolean isValid(String str) {
if (str.contains("a") || str.contains("e") || str.contains("i") || str.contains("o") | str.contains("u")) {
str = str.replace("a", "");
str = str.replace("e", "");
str = str.replace("i", "");
str = str.replace("o", "");
str = str.replace("u", "");
if (str.length() >= 2) {
return true;
}
}
return false;
}
}
반응형
'Algorithm > 문제 풀이' 카테고리의 다른 글
[BAEKJOON_26043 - JAVA] 식당 메뉴 (0) | 2022.11.23 |
---|---|
[BAEKJOON_3055 - JAVA] 탈출 (0) | 2021.01.01 |
[KAKAO_BLIND_RECRUITMENT_2020] 괄호 변환 (0) | 2020.12.30 |
[KAKAO_BLIND_RECRUITMENT_2020] 문자열 압축 (0) | 2020.12.30 |
[BAEKJOON_9935 - JAVA] 문자열 폭발 (0) | 2020.12.29 |