- 소요시간 :
18분 . 맞은 후 최적화 하는데 까지는 25분 - 문제 사이트 : 백준
- 문제 수준 : 골드 4
- 문제 유형 : 브루트포스 알고리즘 , 비트마스킹, 백트래킹
- 다른 사람의 풀이를 참고 했는가 ? : X
- 한 번 풀었다가 다시 푸는 문제인가 ? : X
- 문제 링크 : https://www.acmicpc.net/problem/1062
- 푼 날짜 : 2023.03.19
1. 사용한 자료구조 & 알고리즘
백트래킹을 사용했다.
2. 사고과정
우선 백트래킹의 문제라는 것을 바로 알았다. 그래서 곧바로 백트래킹으로 구현했다. 크게 어려움은 없었으나 처음에 거의 3초에 가까운 시간대가 나와서 조금 당황했다. 오답처리 됐어도 할 말은 없었다. 그래서 어떻게 시간을 줄여볼까를 많이 고민했고, 그래서 최적화를 한 후 제출하니 368 ms 가 나왔다.
3. 풀이과정
[1] 처음에 시도한 풀이
1. 단어 전체를 탐색해서 순열을 뽑는다. r이 3이라면 a,b,c .. a,b,d .... x,y,z 까지 모든 조합을 탐색한다.
2. 그리고 각각 문자마다 이 알파벳이 있나 없나 확인한다. 있는 단어라면 count를 증가.
3. 최대 count 를 출력
[2] 최적화 하기
단어의 시작은 무조건 anta 이고 끝은 무조건 tica 임을 이용했다.
이 두개의 교집합은 a , c, i, n, t 이다. 각각 a를 0이라고 한다면 0,2,8,13,19 이고, 이 5개는 고정으로 배워야 한다. 그렇기에 나는 탐색할 단어의 길이를 총 8개나 줄일 수 있고, a~z 까지의 알파벳 26개 중 5개를 탐색하지 않음으로써 21개만을 탐색할 수 있다.
이 점을 이용했다.
문제를 다 풀고 다른 사람들의 풀이를 보니 역시 다들 나와 비슷한 방식으로 a,c,i,n,t를 배제하고 풀었었다.
4. 소스코드
import java.io.*;
import java.util.*;
public class Main {
static String arr[];
static boolean visited[];
static int maxCnt=0;
static StringBuilder sb=new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
visited=new boolean[26];
visited[0]=true;
visited[2]=true;
visited[8]=true;
visited[13]=true;
visited[19]=true;
st=new StringTokenizer(br.readLine());
int n=Integer.parseInt(st.nextToken());
int r=Integer.parseInt(st.nextToken());
arr=new String[n];
for(int i=0;i<n;i++) {
String word=br.readLine();
arr[i]=word.substring(4,word.length()-4);
}
dfs(0,0,r-5);
System.out.println(maxCnt);
}
public static void dfs(int depth,int start,int max) {
if(depth==max) {
int count=0;
for(int i=0;i<arr.length;i++) {
boolean status=true;
for(int j=0;j<arr[i].length();j++) {
int val=arr[i].charAt(j)-'a';
if(!visited[val]) {
status=false;
break;
}
}
if(status)
count++;
}
maxCnt=Math.max(count,maxCnt);
return;
}
for(int i=start;i<visited.length;i++) {
if(i==0||i==2||i==8||i==13||i==19) continue;
if(!visited[i]) {
visited[i]=true;
dfs(depth+1,i+1,max);
visited[i]=false;
}
}
}
}5. 결과
다른 틀렸습니다는 만약 단어의 r-5를 했는데 그게 0 이하라면 어떻게 탐색할 필요가 없는 단어들을 배제하는 과정에서의 최적화를 진행했었는데 틀렸다고 나왔다.
조금 더 시도해보다가 어차피 최대 길이에서의 최적화만 성공시키면 그 아래는 굳이 하지 않아도 되지 않을까 하며 넘어가기로 했다.
6. 회고
우선 다른사람의 풀이를 보지 않고 나 스스로 최적화를 했다는 것에 굉장히 만족스럽다.
처음에 혼자 이 생각을 했었을 때도 오 .. 내가 이런 생각을 했다고 ? 하면서 혼자 뿌듯했다.
다른 문제를 풀 때에도 불필요한 탐색이나 과정 등을 skip 할 수 있는 게 어떤 것이 있나 항상 고민해 보자.
하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212
