문제 탐색하기
입력 자료 정리
- T는 정답을 위해 확인하게 될 기준 문자열이다
- n은 이후 들어올 문자열의 개수다
- 이후 들어오는 값은 가격과 비교 문자열이다
해결방법 추론
- 입력 최대 값이 매우 작기 때문에, 브루트포스로 해결할 수 있을 것이라 생각하였다
- 단순 포문으로 할 수 있을까 생각했는데, 그러기에는 구현이 복잡해질 것이라 판단하였고
백트래킹으로 해야겠다고 생각하였다 - 알파벳 배열을 두개 만들어서 하나는 기준 문자열에 대한 알파벳 개수를 세고,
하나는 비교 문자열에 대한 알파벳 개수를 세어준다면 모든 경우에 대한 탐색을 할 수 있을 것이다 - 마지막에 선택한 경우에 대해 기준 문자열을 만들 수 있다는 조건을 만족시킨다면,
정답 변수와 비교해서 더 작은 값을 넣어주면 문제를 해결할 수 있을 것이다
시간복잡도 계산
- 백트래킹에서 두가지 선택지에 대해 n만큼의 depth가 발생하므로 2^n의 연산이 발생할 것이다
- 검증과정에서 알파벳 수만큼 탐색하므로 26, 그리고 각 문자열만큼 탐색해서 wi의 연산이 발생한다
- 총 정리하면 시간복잡도는 O(26 x 2^n x Wi)가 될 것이고,
각각의 최대 입력값을 생각했을 때, 시간제한안에 문제를 해결할 수 있다
코드 설계하기
입력값 상태 관리하기
- 기준 문자열은 word라는 변수로 관리하며,
26 크기의 int형 alpha 배열에 기준 문자를 비교하며, 그 개수를 세어준다 - n 역시 변수로 관리하며, 이후 들어오는 가격과 문자열은 Pair로 묶어 list에 저장한다
- 선택한 문자에 대한 개수를 관리하는 26크기의 배열도 하나 만들어두며,
정답을 위한 ans 변수는 최소값을 출력해야하므로 초기값을 Integer.MAX_VALUE로 한다
backtracking 설계
함수식
- backtracking(int idx, int sum, int n)
1. 탐색할 문자열의 인덱스를 의미하는 idx 파라미터와 비용의 합을 관리할 sum,
base condition을 위한 n까지 파라미터로 갖는다.
재귀식
선택하는 경우
- backtracking(idx+1, sum + list.get(idx).cost, n)
1. idx번째의 문자열을 선택하는 경우로, 그 비용을 더해서 넘겨준다
2. 재귀식 실행 전에 list.get(idx).name.length만큼 순회하여,
선택 문자 배열인 counts 배열에 현재 선택된 인덱스의 문자열의 문자 알파벳을
인덱스로하여 개수를 증가시켜준다
선택하지 않는 경우
- backtracking(idx+1, sum, n)
1. idx번째의 문자열을 선택하지 않는 경우로, 비용합산 없이 그대로 넘겨준다
2. 앞서 증가시킨 알파벳 개수를 선택하지 않는 경우이므로, 이번에는 감소시켜준다
base condition
- if(idx == n) {...}
1. idx가 n이되면 모든 문자열을 탐색한 것이므로 종료시켜준다
2. 검증 메소드를 통과하는 경우 ans와 sum을 비교하여 더작은 값은 ans에 넣어준다
검증 메소드 설계
- 26개의 알파벳 문자열을 순회하면서 만약 기준 문자열의 각 알파벳 개수가
비교 문자열의 알파벳 개수보다 많다면, 현재 선택된 알파벳 조합으로는 기준 문자열을
완성할 수 없다는 의미이므로 false를 리턴한다 - 모든 알파벳 검증을 통과했을 경우 true를 리턴한다
출력 설계
- ans가 최초값 그대로라면 -1을 출력하고, 아니면 ans를 출력하면 정답이 된다.
정답 코드
import java.io.*;
import java.util.*;
class Pair{
int cost;
String name;
public Pair(int cost, String name) {
this.cost = cost;
this.name = name;
}
}
public class Main {
static String word;
static List<Pair> list;
static int[] alpha = new int[26];
static int[] counts = new int[26];
static int ans = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
word = br.readLine();
for (int i = 0; i < word.length(); i++) {
alpha[word.charAt(i) - 'A']++;
}
int n = Integer.parseInt(br.readLine());
list = new ArrayList<>();
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
String b = st.nextToken();
list.add(new Pair(a, b));
}
backtracking(0,0, n);
if(ans == Integer.MAX_VALUE){
bw.write("-1");
}else{
bw.write(ans+"");
}
br.close();
bw.close();
}
private static void backtracking(int idx, int sum, int n) {
if(idx == n){
if (chk()) {
ans = Math.min(ans, sum);
}
return;
}
for (int i = 0; i < list.get(idx).name.length(); i++) {
counts[list.get(idx).name.charAt(i) - 'A']++;
}
backtracking(idx+1, sum + list.get(idx).cost, n);
for (int i = 0; i < list.get(idx).name.length(); i++) {
counts[list.get(idx).name.charAt(i) - 'A']--;
}
backtracking(idx+1, sum, n);
}
private static boolean chk() {
for (int i = 0; i < 26; i++) {
if(alpha[i] > counts[i]){
return false;
}
}
return true;
}
}문제 링크
Software Developer