백준 1352번: 문자열

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

 

주어진 100이하의 자연수 N에 대해서 길이 N의 문자열을 만들때 각각의 문자에 대해 그 문자가 가장 먼저 나타난 것의 인덱스만큼 그 문자가 나타나는 문자열을 만드는 경우의 수 중 사전 순으로 가장 빠른 문자열을 만드는 문제이다. 문자는 알파벳 대문자로 구성해야 하며 인덱스는 1부터 시작한다.

 

우선, 모든 알파벳의 갯수를 더하면 전체 길이인 N이 되어야 한다. 즉, 합이 N이 되는 증가 수열을 찾아야 하며, 이러한 수열 중 빈칸을 채울 수 있는지 검사해야 한다. 이를 위해 백트래킹을 수행하여 다음 알파벳을 처음으로 나타날 위치를 선택하면서 가지치기를 한다. 이미 등장한 문자들의 총 개수가 다음 문자가 나오기 전까지의 인덱스보다 작으면, 중간에 절대 채울 수 없는 빈 공간이 생기게 되어 가지치기를 위해 종료한다. 길이의 합이 N이 되면 buildString을 통해 문자열로 치환한다.

private static void solve(int count, int sum, int[] seq, int lastVal) {
    if (sum == N) {
        String current = buildString(count, seq);
        if (current != null) {
            if (bestResult == null || current.compareTo(bestResult) < 0) {
                bestResult = current;
            }
        }
        return;
    }
    
    for (int next = lastVal + 1; sum + next <= N; next++) {
        if (count == 0 && next != 1) {
            continue;
        }
        
        if (count > 0 && sum < next - 1) {
            break;
        }
        
        seq[count] = next;
        solve(count + 1, sum + next, seq, next);
    }
}

 

 

buildString은 각 문자의 첫번째 위치 확인 후, 위치에 맞게 배치한다. 이후 문자 순서대로 비어있는 공간에 남은 문자를 채워서 문자열을 반환한다. 배치할 수 없다면 만들 수 없는 문자열이므로 null을 반환한다.

private static String buildString(int k, int[] seq) {
    char[] res = new char[N];
    int[] remaining = new int[k];
    int[] firstPos = new int[k];
    boolean[] isFirstPos = new boolean[N + 1];
    
    for (int i = 0; i < k; i++) {
        int pos = seq[i];
        firstPos[i] = pos;
        res[pos - 1] = (char) ('A' + i);
        remaining[i] = pos - 1;
        isFirstPos[pos] = true;
    }
    
    for (int i = 1; i <= N; i++) {
        if (isFirstPos[i]) {
            continue;
        }
        
        boolean placed = false;
        for (int j = 0; j < k; j++) {
            if (firstPos[j] < i && remaining[j] > 0) {
                res[i - 1] = (char) ('A' + j);
                remaining[j]--;
                placed = true;
                break;
            }
        }
        if (!placed) {
            return null;
        }
    }
    return new String(res);
}

 

 

결과 코드는 다음과 같다.

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

public class 문자열1352 {
    
    static int N;
    static String bestResult = null;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        br.close();
        solve(0, 0, new int[N + 1], 0);
        
        System.out.print(bestResult == null ? "-1" : bestResult);
    }
    
    static void solve(int count, int sum, int[] seq, int lastVal) {
        if (sum == N) {
            System.out.println(Arrays.toString(seq));
            String current = buildString(count, seq);
            if (current != null) {
                if (bestResult == null || current.compareTo(bestResult) < 0) {
                    bestResult = current;
                }
            }
            return;
        }
        
        for (int next = lastVal + 1; sum + next <= N; next++) {
            if (count == 0 && next != 1) {
                continue;
            }
            
            if (count > 0 && sum < next - 1) {
                break;
            }
            
            seq[count] = next;
            solve(count + 1, sum + next, seq, next);
        }
    }
    
    private static String buildString(int k, int[] seq) {
        char[] res = new char[N];
        int[] remaining = new int[k];
        int[] firstPos = new int[k];
        boolean[] isFirstPos = new boolean[N + 1];
        
        for (int i = 0; i < k; i++) {
            int pos = seq[i];
            firstPos[i] = pos;
            res[pos - 1] = (char) ('A' + i);
            remaining[i] = pos - 1;
            isFirstPos[pos] = true;
        }
        
        for (int i = 1; i <= N; i++) {
            if (isFirstPos[i]) {
                continue;
            }
            
            boolean placed = false;
            for (int j = 0; j < k; j++) {
                if (firstPos[j] < i && remaining[j] > 0) {
                    res[i - 1] = (char) ('A' + j);
                    remaining[j]--;
                    placed = true;
                    break;
                }
            }
            if (!placed) {
                return null;
            }
        }
        return new String(res);
    }
}