백준 1062 가르침

알고리즘

k-5개만 고르면 된다

• 모든 단어가 "anta"로 시작하고 "tica"로 끝나므로 {'a', 'n', 't', 'i', 'c'}는 무조건 알고 있어야 한다
• 나머지 알파벳 중 k-5개를 마저 뽑아서 시뮬레이션(?)을 돌리면 된다
• 나는 무조건 알야야 하는 알파벳(origin)과 뽑을 알파벳(pick)으로 나눠서 체크해줬다

 

배운 것

1. List의 contains()메소드

리스트에 해당 요소가 있는지 알려준다

2. 문자열 처리

for(int i=0; i<26; i++) {
	char now = (char) ('a'+i); // 'a'~'z'의 알파벳 구하기
}

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main_bj_1062_가르침_서울_06_신유진 {
	static int n, k;
	static List<Character> candi = new ArrayList<Character>();
	static List<char[]> words =  new ArrayList<char[]>();
	static List<Character> origin = new ArrayList<Character>();
	static int ans = 0;
	public static void main(String[] args) throws IOException {
		// 뽑을 알파벳들 넣기 
		for(int i=0; i<26; i++) {
			char now = (char) ('a'+i);
			if(now!='a' && now!='c' && now!='n' && now!='i' && now!='t') {
				candi.add(now);
			}
		}
		// 원래 있어야 하는 글자 고르기 
		origin.add('a'); origin.add('c'); origin.add('n'); origin.add('i'); origin.add('t');
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		
		for(int i=0; i<n; i++) {
			char[] word = br.readLine().toCharArray();
			words.add(word);
		}
		combi(0, 0);
		System.out.println(ans);
	}
	static List<Character> pick = new ArrayList<Character>();
	
	static void combi(int depth, int now) {
		if(depth==k-5) {
			int cnt = 0;
			// 읽을 수 있는 단어 개수 
			for(int i=0; i<n; i++) {
				char[] word = words.get(i);
				if(check(word)) cnt++;
			}
			ans = Math.max(cnt, ans);
			return;
		}
		for(int i=now; i<candi.size(); i++) {
			pick.add(candi.get(i));
			combi(depth+1, i+1);
			//System.out.println(pick);
			pick.remove(pick.size()-1);
		}
	}
	static boolean check(char[] word) {
		for(int i=4; i<word.length-4; i++) {
			char now = word[i];
			if(origin.contains(now) || pick.contains(now)) continue;
			else return false;
		}
		return true;
	}
}