[백준/BOJ] 1062번 가르침 자바 풀이

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

1062번: 가르침

 

문제

남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다.

남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문자로만 이루어져 있고, 길이가 8보다 크거나 같고, 15보다 작거나 같다. 모든 단어는 중복되지 않는다.

출력

첫째 줄에 김지민이 K개의 글자를 가르칠 때, 학생들이 읽을 수 있는 단어 개수의 최댓값을 출력한다.

 

 

		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		str = new String[N];

		if(K < 5) {
			System.out.println(0);
			return;
		}
		if(K == 26) {
			System.out.println(N);
			return;
		}

백트래킹을 이용해 문제를 풀었다.

모든 단어는 anta로 시작하고 tica로 끝나기 때문에, a/n/t/i/c는 꼭 가르쳐야 한다.

K가 5보다 작다면 a/n/t/i/c를 가르칠 수 없으므로 어떠한 단어도 읽을 수 없기 때문에 0을 출력한다.

반대로 K가 26이라면 모든 단어를 읽을 수 있으므로 N을 출력한다.

 

		for(int i=0;i<N;i++) 
			str[i] = br.readLine().replaceAll("anta|tica", "");
		
        visit = new boolean[26];
		visit['a' - 'a'] = true;
		visit['n' - 'a'] = true;
		visit['t' - 'a'] = true;
		visit['i' - 'a'] = true;
		visit['c' - 'a'] = true;

그리고 입력으로 들어온 단어를 anta/tica 기준으로 자르고 String[] str에 저장한다.

visit[] 배열을 알파벳의 개수인 26 크기로 선언하고,

무조건 배워야 할 알파벳인 a/n/t/i/c를 true로 설정한다.

visit[] 배열의 인덱스가 알파벳이 되고, 그 인덱스의 값이 true라면 가르친 알파벳, false라면 가르치지 않은 알파벳이다.

 

 

	static void DFS(int depth, int start) {
		if(depth == K) {
            int cnt = 0;
		    Loop : for(int i=0;i<N;i++) {
                for(int j=0;j<str[i].length();j++)
                    if(!visit[str[i].charAt(j) - 'a'])
                        continue Loop;
			    cnt++;
		    }
            
			answer = Math.max(answer, cnt);
			return;
		}
		
		for(int i=start;i<26;i++) {
			if(visit[i])
				continue;
			
			visit[i] = true;
			DFS(depth + 1, i + 1);
			visit[i] = false;
		}
	}

}

그 다음 DFS를 통해 재귀적으로 K - 5개의 알파벳을 뽑는다. (a/n/t/i/c는 이미 배웠으므로 K - 5)

알파벳을 다 뽑았다면 입력으로 들어온 단어의 알파벳을 하나씩 탐색하면서 visit[]가 false인 알파벳이 있는지 확인한다.

만약 어떠한 단어 중 visit[]가 false인 알파벳이 하나라도 있다면, 그 단어는 읽을 수 없으므로 continue 한다.

그리고 false인 알파벳이 존재하지 않아 continue되지 않았다면(for문이 끝까지 돌았다면)

그 단어는 읽을 수 있는 것이므로 cnt를 1 증가시킨다.

 

모든 단어를 탐색했다면 answer와 cnt를 비교해 더 큰 값을 answer로 갱신한다.

 

 

 

 

 

* DFS에서 depth가 K가 되었을 때(모든 알파벳을 뽑았을 때) cnt를 구하는 함수를 따로 만들었었는데,

함수로 이동하여 계산하고 int cnt를 DFS로 반환하는 것 보다는

DFS 함수 내에서 cnt를 구하는 것이 더 효율적이다.

 

* String을 한 문자씩 탐색하기 위해서는 toCharArray() 대신 charAt(index)를 사용하는 것이 공간, 시간적으로 훨씬 효율적이다.

메모리가 너무 비정상적으로 크게 나와 여러가지를 수정해봤는데, toCharArray()를 없애니 훨씬 적은 메모리가 잡혔다.

시간도 두배 정도 차이가 난다..!

(사진 상 위에 것이 charAt() 사용 / 아래 것이 toCharArray() 사용)

import java.util.*;
import java.io.*;

public class Main {
	static String[] str;
	static boolean[] visit;
	static int N, K;
	static int answer = 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()); 
		str = new String[N];

		if(K < 5) {
			System.out.println(0);
			return;
		}
		if(K == 26) {
			System.out.println(N);
			return;
		}
		
		K -= 5;
		
		for(int i=0;i<N;i++) 
			str[i] = br.readLine().replaceAll("anta|tica", "");
		
        visit = new boolean[26];
		visit['a' - 'a'] = true;
		visit['n' - 'a'] = true;
		visit['t' - 'a'] = true;
		visit['i' - 'a'] = true;
		visit['c' - 'a'] = true;
		
		DFS(0, 0);
		System.out.println(answer);
		
	}
	
	static void DFS(int depth, int start) {
		if(depth == K) {
            int cnt = 0;
		    Loop : for(int i=0;i<N;i++) {
                for(int j=0;j<str[i].length();j++)
                    if(!visit[str[i].charAt(j) - 'a'])
                        continue Loop;
			    cnt++;
		    }
            
			answer = Math.max(answer, cnt);
			return;
		}
		
		for(int i=start;i<26;i++) {
			if(visit[i])
				continue;
			
			visit[i] = true;
			DFS(depth + 1, i + 1);
			visit[i] = false;
		}
	}

}