[백준/java] 1062. 가르침

문제 링크 - https://www.acmicpc.net/problem/1062

🌱 문제

문제 요약

• 조금 신박한 문제여서 문제를 이해하기가 조금 어려웠다.
• 26개의 알파벳 중 K개만 읽을 수 있고, 주어진 N개의 단어중 단어 각각이 앞에서 선택된 K개의 알파벳으로 이루어져 있어야 그 단어를 읽을 수 있다.
• 주어진 단어 N개 중 읽을 수 있는 단어의 최댓값을 구하는 것이 문제이다.

🌱 풀이

초기 부분

• 모든 단어는 a,n,t,i,c 다섯개의 알파벳을 가지고 있으므로 K가 5보다 작다면 아무 단어도 읽을 수 없다.
  -> 그러므로 이 경우에는 0을 출력하고 함수 종료.
• 같은 맥락으로 K==26이면 모든 단어를 읽을 수 있으므로 N을 출력하고 종료하면된다. (이건 내 코드에선 없고, 풀고나서 다른사람 풀이 궁금해서 찾아보다가 발견)

if(K<5) { // K가 5보다 작으면 읽을 수 있는 단어 없음 
			answer=0;
			System.out.println(answer);
			return;
		}

조합 구하고, 계산하는 부분

k>5 일때만 실행되는 부분
1. a,n,t,i,c 알파벳은 미리 방문체크를 해둔 후 이 다섯개의 알파벳을 제외하고 K-5개의 알파벳을 선택한다.
2. 선택이 완료되면 N개의 단어들을 돌면서 고른 알파벳 조합으로 해당 단어가 고른 알파벳으로 이루어져 있는지 확인하고 갯수를 세준다. (최댓값 갱신)
이 때, 단어의 시작 4개와 끝 4개의 알파벳은 고정되어 있으므로 그 외의 인덱스만 살펴보면 된다.

static public void comb(int cnt, int start) { // 
		if(cnt==K-5) { // K-5개 선택이 완료되면 리턴 
			calculate(); // 현재 선택된 조합으로 계산하는 함수 
			return;
		}
		
		for(int i=start; i<26; i++) { // 조합 구하는 for문 
			if(!selected[i]) {
				selected[i]=true;
				comb(cnt+1,i+1);
				selected[i]=false;
			}
		}
	}
	static public void calculate() { //만들어진 조합으로 N개의 단어중 몇개 읽을 수 있는지 계산 
		int count=N;
		for(int i=0; i<N; i++) {
			String cur = arr[i];
			for(int j=4; j<cur.length()-4; j++) {
				if(selected[cur.charAt(j)-'a']==false) {
					count--;
					break;
				}
			}
			
		}
		answer=Math.max(count, answer); //최댓값 갱신 
	}

🌱 코드

package week13.boj_1062;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

//1062. 가르침 
public class Somyeong {
	static int N,K;
	static int answer;
	static String[] arr;
	static Set<Character> set;
	static boolean selected[];
	
	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];
		
		for(int i=0; i<N; i++) {
			arr[i]=br.readLine();
		}
		
		if(K<5) { // K가 5보다 작으면 읽을 수 있는 단어 없음 
			answer=0;
			System.out.println(answer);
			return;
		}
		
		selected = new boolean[26];
		// a,n,t,i,c
		// 단어에 항상 들어가는 5개의 단어는 무조건 포함해야 하므로 미리 방문처리 
		selected['a'-'a']=true;
		selected['n'-'a']=true;
		selected['t'-'a']=true;
		selected['i'-'a']=true;
		selected['c'-'a']=true;
		
		comb(0,0);	
		System.out.println(answer);
		
	
	}
	static public void comb(int cnt, int start) { // 
		if(cnt==K-5) { // K-5개 선택이 완료되면 리턴 
//			for(int i=0; i<26; i++) {
//				if(selected[i])
//					System.out.print(i+" ");
//			}
//			System.out.println();
			calculate(); // 현재 선택된 조합으로 계산하는 함수 
			return;
		}
		
		for(int i=start; i<26; i++) { // 조합 구하는 for문 
			if(!selected[i]) {
				selected[i]=true;
				comb(cnt+1,i+1);
				selected[i]=false;
			}
		}
	}
	static public void calculate() { //만들어진 조합으로 N개의 단어중 몇개 읽을 수 있는지 계산 
		int count=N;
		for(int i=0; i<N; i++) {
			String cur = arr[i];
			for(int j=4; j<cur.length()-4; j++) {
				if(selected[cur.charAt(j)-'a']==false) {
					count--;
					break;
				}
			}
			
		}
		answer=Math.max(count, answer); //최댓값 갱신 
//		System.out.println("count: "+count);
	}
}