[BJ1062] 가르침

🚩 문제 설명

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

1062번: 가르침

◾ anta, tica 를 포함해서 단어 K 개를 가르칠 수 있다.

◾ 이렇게 배운 글자들을 가지고 주어진 단어들 중 최대 몇 개를 읽을 수 있는지 알아보는 문제.

 

 

 

---

 

 

 

✅ 입출력

변수 설명
N: 주어지는 단어의 개수
K: 배울 수 있는 알파벳의 개수
return ➡️ 배운 알파벳으로 읽을 수 있는 최대 단어의 개수

✔️ 예제 1

3 6
antarctica
antahellotica
antacartica

2

 

 

---

 

 

 

📑 문제 풀이

with 자바 (Java)

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


public class Main {
	static int ans, N, K;
	static String[] arr; // 읽어야하는 단어들
	static boolean[] alpha = new boolean[26]; // 알파벳 visit 배열


	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());

		alpha['a' - 'a'] = true;
		alpha['n' - 'a'] = true;
		alpha['t' - 'a'] = true;
		alpha['i' - 'a'] = true;
		alpha['c' - 'a'] = true;

		arr = new String[N];
		for (int i = 0; i < N; i++) {
			String line = br.readLine();
			line = line.substring(4, line.length());
			line = line.substring(0, line.length() - 4);
			arr[i] = line;
		}

		// 완전탐색
		if (K < 5) ans = 0;
		else if (K == 26) ans = N;
		else comb(0, 0);

		// 출력
		System.out.println(ans);

	} // end main


	private static void comb(int dep, int idx) {
		if (dep == K - 5) {
			ans = Math.max(ans, check());
			return;
		}

		for (int i = idx; i < 26; i++) {
			if (alpha[i]) continue;

			alpha[i] = true;
			comb(dep + 1, i + 1);
			alpha[i] = false;
		}

	} // end dfs


	private static int check() {
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			boolean flag = true;
			for (char c : arr[i].toCharArray()) {
				if (!alpha[c - 'a']) {
					flag = false;
					break;
				}

			}

			if (flag) cnt++;

		}

		return cnt;
	} // end check

}

💬 Point

➡️ 조합 사용
➡️ 크기가 26인 alphapet 배열 사용

◾ 조합을 이용해서 풀 수 있는 문제이다.

◾ 새로이 배울 수 있는 알파벳 조합을 만들기 위해, 크기가 26인 boolean 타입의 알파벳 배열을 만들어준다.

◾ 만약, 해당 배열에서 true 라면 배운 알파벳이다.

◾ 또한, 'anta', 'tica' 라는 문자열을 기본적으로 알고가야지 단어들을 읽을 수 있다.

◾ 따라서 만약 K가 5보다 작다면 무조건적으로 0을 리턴해야한다.

 

private static void comb(int dep, int idx) {
    if (dep == K - 5) {
        ans = Math.max(ans, check());
        return;
    }

    for (int i = idx; i < 26; i++) {
        if (alpha[i]) continue;

        alpha[i] = true;
        comb(dep + 1, i + 1);
        alpha[i] = false;
    }

} // end dfs

◾ 조합을 이용하여 새롭게 배우는 알파벳 조합을 만들었다.

◾ K - 5 인 이유는 기본적으로 배워야하는 'anta', 'tica' 을 제외하고서 배워야하기 때문이다.

 

// 각 단어의 알파벳이 새롭게 배운 알파벳이 아니라면 false
private static int check() {
    int cnt = 0;

    for (int i = 0; i < N; i++) {
        boolean flag = true;

        for (char c : arr[i].toCharArray()) {
            if (!alpha[c - 'a']) {
                flag = false;
                break;
            }

        }

        if (flag) cnt++;

    }

    return cnt;
} // end check

◾ 읽어야하는 단어의 각 알파벳이 새롭게 배운 알파벳이 아니라면 flag 를 false 로 만들어준다.

◾ false 가 아니라면 읽을 수 있는 단어이므로 카운팅을 해준다.

시간초과 코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.stream.Collectors;


public class Main {
	static int ans, N, K;
	static String[] arr;

	static Set<Character> set = new HashSet<>();
	static Set<Character> setNew = new HashSet<>();
	static Set<Character> setLearned = new HashSet<>();


	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());

		// 기존의 문자열 set
		set.add('a');
		set.add('n');
		set.add('t');
		set.add('i');
		set.add('c');

		setLearned.addAll(set);

		arr = new String[N];
		for (int i = 0; i < N; i++) {
			arr[i] = br.readLine();

			// 새롭게 배울 수 있는 문자열 set (anta, tica 제외)
			for (char c : arr[i].toCharArray()) {
				if (c == 'a' || c == 'n' || c == 't' || c == 'i' || c == 'c') continue;
				setNew.add(c);
			}

		}

		// 완전탐색
		if (K < 5) ans = 0;
		else dfs(0);

		// 출력
		System.out.println(ans);

	} // end main


	private static void dfs(int dep) {
		if (dep == (K - 5)) {
			int cnt = 0;
			for (int i = 0; i < N; i++) {
				Character[] chs = arr[i].chars().mapToObj(c -> (char) c).toArray(Character[]::new);
				Set<Character> tmp = Arrays.stream(chs).collect(Collectors.toSet());

				if (setLearned.containsAll(tmp)) cnt++;

			}

			ans = Math.max(ans, cnt);

			return;
		}

		for (char c : setNew) {
			if (setLearned.contains(c)) continue;

			setLearned.add(c);
			dfs(dep + 1);
			setLearned.remove(c);
		}

	} // end dfs

}

배운 문자열과 집합에 해당 단어들이 포함되는지 확인해서 cnt 를 센다.

시간초과가 난다. 뭐에 홀렸나? 왜이렇게 풀었지..?

 

 

 

 

 

 

 

 

 

 

 

 

 

# 알고리즘 백준 가르침 java

# 백준 가르침 자바

---