https://www.acmicpc.net/problem/1062

✔ 문제파악
- 첫번 째 줄에 단어의 개수 N과 배울 수 있는 글자 수 K가 주어진다. 그리고 단어 배열이 주어진다.
- 선생님은 학생들에게 K개의 글자를 가르칠 수 있는데, K개의 글자를 가르친 후 학생들이 읽을 수 있는 단어의 개수가 최대인 값이 무엇인지 구하여라.
- 접두사는 "anta", 접미사는 "tica"로 끝난다.
✔ 접근방법
백트래킹(DP 문제), 브루트포스 알고리즘
1) 단어 배열을 예쁘게 만들어 준 후, 공통된 접두사와 접미사에 포함된 글자를 방문 처리해준다.
=> 우리는 배운 글자를 boolean 방문 배열을 통해 해결해줄 것이다 !
- visited['a' - 97]을 빼주는 이유는 소문자 a의 아스키코드가 97이기 때문.
🎐 아스키코드를 잘 모르겠으면 https://namu.wiki/w/%EC%95%84%EC%8A%A4%ED%82%A4%20%EC%BD%94%EB%93%9C
=> 공통적으로 포함된 "anta"와 "tica"는 시간을 줄이기 위해 정제한 후, 단어 배열에 추가해준다.
=> antic는 무조건 배워야하는 단어이므로 방문처리 해준다.
// 1) 단어 정제
for (int i = 0; i < n; i++) {
String word = br.readLine();
arr[i] = word.replaceAll("[a|n|t|i|c]", "");
}
// a,n,t,i,c 방문처리
static boolean[] visited = new boolean[27];
visited['a' - 97] = visited['n' - 97] = visited['t' - 97] = visited['i' - 97] = visited['c' - 97] = true;
2) 백트래킹 시작
static void dp(int depth, int start) {
// 정해진 수 만큼의 단어를 외우면 종료(종료조건)
if (depth == k - 5) {
result = 0;
for (int i = 0; i < n; i++) {
if (check(arr[i])) {
result++;
}
}
MAX_VALUE = Math.max(result, MAX_VALUE);
return;
}
for (int i = start; i < 27; i++) {
if (!visited[i]) {
visited[i] = true;
dp(depth + 1,i);
visited[i] = false;
}
}
}
// 단어에 있는 모든 글자를 배웠는지 확인
static boolean check(String word) {
for (int i = 0; i < word.length(); i++) {
if (!visited[word.charAt(i) - 97]) {
return false;
}
}
return true;
}
💭 브루트포스, 백트래킹, DFS 차이
브루트 포스 알고리즘 = 모든 가능한 경우를 전부 해보는 방식의 알고리즘
백트래킹 = 탐색을 진행하고 조건에 맞지 않는 부분을 제외하면서 진행하는 방식의 알고리즘
DFS = 트리를 완전 탐색하는 한가지 방법
✔ 전체코드
import java.util.*;
import java.io.*;
public class Main {
static int n;
static int k;
static String[] arr;
static int MAX_VALUE = 0;
// 배운 글자를 표시할 방문 배열 생성
static boolean[] visited = new boolean[27];
static int result = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
arr = new String[n];
// 1) 단어 정제 및 방문처리
for (int i = 0; i < n; i++) {
String word = br.readLine();
arr[i] = word.replaceAll("[a|n|t|i|c]", "");
}
visited['a' - 97] = visited['n' - 97] = visited['t' - 97] = visited['i' - 97] = visited['c' - 97] = true;
if (k < 5) {
System.out.println(0);
} else {
dp(0,0);
System.out.println(MAX_VALUE);
}
}
static void dp(int depth, int start) {
// 정해진 수 만큼의 단어를 외우면 종료(종료조건)
if (depth == k - 5) {
result = 0;
for (int i = 0; i < n; i++) {
if (check(arr[i])) {
result++;
}
}
MAX_VALUE = Math.max(result, MAX_VALUE);
return;
}
// start 인덱스를 통해 중복을 방지해준다.
for (int i = start; i < 27; i++) {
if (!visited[i]) {
visited[i] = true;
dp(depth + 1,i);
visited[i] = false;
}
}
}
static boolean check(String word) {
for (int i = 0; i < word.length(); i++) {
if (!visited[word.charAt(i) - 97]) {
return false;
}
}
return true;
}
}
🐥 회고
3번째 풀고 있는 코드이다. (재귀는 어려워)
시간 초과가 나와서 애를 먹었다. 예외처리를 연습하는 방법이 조금 더 필요할 것 같다
I can do it !!!!!!
'[Algorithm] 알고리즘' 카테고리의 다른 글
| [프로그래머스][JAVA] 조이스틱 - 그리디 (1) | 2025.01.06 |
|---|---|
| [프로그래머스] 체육복 (JAVA) (1) | 2024.12.27 |
| [백준][boj]연산자 끼워넣기 (JAVA) - 재귀의 기본 (0) | 2024.12.17 |
| [프로그래머스][level3] 가장 긴 팰린드롬 (Python) (1) | 2024.10.31 |
| [백준][boj]괄호의 값 (Python) - 스택의 응용 (1) | 2024.10.17 |