[백준 / Java] 1062번: 가르침 (골드4)

문제 풀이 날짜: 2023.09.12
포스트 작성일: 2023.09.30

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 1062번: 가르침 (골드4)

 

키워드

순열, Next Permutation

 

풀이 접근법

• 모든 단어는 anta로 시작해서 tica로 끝나기 때문에 이 단어에 들어가있는 알파벳 다섯개 a, n, t, i, c 가 우선순위를 갖는다.
• 하지만 단순히 알파벳 출현 빈도수만을 체크한다면 아래와 같은 반례가 존재한다.
• 이 테케에서 첫 번째 단어 빼고 다른 단어에는 x가 들어가지 않는다.

8 25
antaxxxxxxxxxxxxxxxxxxxtica
antaabctica
antadeftica
antaghijtica
antaklmntica
antaopqrtica
antastuvtica
antawxyztica

//x를 제외한 나머지 알파벳을 학습해야 함.

• 이 상황에서 x의 빈도수가 가장 높다고 해도 다른 알파벳을 학습해야 최댓값을 구할 수 있다.
  • 따라서 a, n, t, i, c 다섯 개를 제외하고 어떤 알파벳을 학습해야 하는지를 조합으로 구한다.
  • 시간을 단축시키기 위하여 Next Permutation으로 풀이하였다.
• 조합을 구할 때는, 현재까지 출현한 알파벳을 집계해서 각각의 인덱스를 Map으로 만들어 주었다.
  • 인덱스를 참조할 때는 Map을 이용해 O(1) 시간만에 이 알파벳의 학습 여부를 판단할 수 있다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	private static int N;
	private static int K;
	private static int result = 0;

	private static int[] items;
	private static String[] words;
	private static Map<Character, Integer> indexes = new HashMap<>();
	private static Set<Character> set = new HashSet<>();

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

		String[] temp = br.readLine().split(" ");

		N = Integer.parseInt(temp[0]);
		K = Integer.parseInt(temp[1]);
		words = new String[N];

		K = K - 5;
		if (K < 0) { // a, n, t, i, c 을 모두 학습할 수 없다면
			System.out.print(0);
			return;
		}

		for (int i = 0; i < N; i++) {
			words[i] = br.readLine();
			
			for (int j = 4; j < words[i].length() - 4; j++) {
				char c = words[i].charAt(j);
				
				if (c == 'a' || c == 'n' || c == 't'
						|| c == 'i' || c == 'c') { // a, n, t, i, c 제외
					continue;
				}
				
				set.add(c);
			}
		}
		
		int idx = 0;
		for(Character c : set) {
			indexes.put(c, idx++);
		}

		items = new int['z' - 'a' + 1 - 5];

		for (int i = items.length - 1; i >= items.length - K; i--) {
			items[i] = 1; // 뽑아야 하는 수만큼 초기화 시킨다.
		}

		do {
			result = Math.max(countWords(), result);
		} while (np(items));

		System.out.println(result);
	}

	private static int countWords() {
		int count = 0;
		all : for(String word : words) {
			for (int i = 4; i < word.length() - 4; i++) {
				char c = word.charAt(i);
				
				if (c == 'a' || c == 'n' || c == 't'
						|| c == 'i' || c == 'c') { // a, n, t, i, c 제외
					continue;
				}

				if(items[indexes.get(c)] == 0) {
					continue all; //읽을 수 없는 단어
				}
			}
			count++;
		}
		
		return count;
	}

	private static boolean np(int[] count) {
		int swapIdx = -1;
		for (int i = 1; i < count.length; i++) {
			if (count[i - 1] < count[i])
				swapIdx = i - 1;
		}
		if (swapIdx == -1)
			return false;

		int largerIdx = -1;
		for (int j = 1; j < count.length; j++) {
			if (count[swapIdx] < count[j])
				largerIdx = j;
		}

		swap(count, swapIdx, largerIdx);

		int j = count.length - 1;
		for (int i = swapIdx + 1; i < j; i++) {
			swap(count, i, j);
			j--;
		}

		return true;
	}

	private static void swap(int[] count, int swapIdx, int largerIdx) {
		int temp = count[swapIdx];
		count[swapIdx] = count[largerIdx];
		count[largerIdx] = temp;
	}
}

---

Next Permutation을 사용했음에도 동일 자바 대비 실행 시간이 조금 느리게 나왔다. 알파벳의 학습 여부를 boolean으로 체크하고, recursion으로 답을 찾으면 오히려 더 빠를 수도 있는데, 아무래도 Next Permutation으로 조합을 계산하는 시간을 줄였어도 컬렉션을 참조하는 시간이 오래 걸리는 듯하다.

 

git 링크

(git 링크 첨부)