문제

영어 문제에 도전해봤다.

번역은 전문가를 초빙해 부탁했다.

이 문제는 유치원생들이 영어 알파벳을 순서대로 발음하는 대회에 참여하는 상황을 설명하고 있습니다. 참가자들은 다른 참가자가 끝나지 않았더라도 언제든지 알파벳을 발음하기 시작할 수 있습니다. 선생님은 모든 참가자가 발음한 알파벳을 하나의 문자열로 기록합니다.

참가자들이 알파벳을 발음할 때 실수를 할 수 있습니다. 실수란 특정 알파벳을 건너뛰는 것을 의미하며, 각 참가자가 실수한 횟수는 건너뛴 알파벳의 개수로 계산됩니다. 모든 참가자의 실수를 합친 총 실수 횟수는 k를 초과하지 않습니다. 참가자는 중간에 발음을 멈출 수 있으며, 이 경우 남은 알파벳은 실수로 계산되지 않습니다.

문제에서 주어진 것은 k와 최종 문자열입니다. 주어진 정보를 바탕으로 가능한 최소 참가자 수를 구하거나, 주어진 데이터가 올바르지 않다고 판단해야 합니다.

고마워요 지피티맨

유치원생들의 알파벳 말하기 대회를 진행하는 중, 유치원생들은 몇몇의 알파벳을 건너 뛸 수 있다.
예를 들어 유치원생 홍길동씨가 있을 때, 홍길동씨는 ABDF와 같이 발언할 수 있다.

이 때 홍길동씨는 2번 건너뛰었다고 할 수 있다.

또한 이 유치원생들은 비동기적으로 동작하는데, 예를 들면 다음과 같다.
홍길동: ABC
성춘향: DEF
와 같이 발언할 때, 최종 문자열은 ADBEFC, ADEFBC와 같이 나타날 수 있다.

최종 문자열과 최대 건너뛴 횟수 k가 주어질 때 가능한 최소 참가자 수를 구하고, 불가능한 경우에 "Impossible"을 출력한다.

아이디어

유치원생 리스트를 유지하며, 오래된 유치원생들부터 순회하며 가능한 유치원생에게 알파벳을 할당한다.
탐욕 가득한 문제 풀이 시작!

소스코드

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

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

        int k = Integer.parseInt(br.readLine());
        String str = br.readLine();

        List<Character> kids = new ArrayList<>();
        for (int i = 0; i < str.length(); i++) {
            boolean temp = false;
            for (int j = 0; j < kids.size(); j++) {
                if(kids.get(j) < str.charAt(i)){
                    temp = true;
                    k -= str.charAt(i) - kids.get(j) - 1;
                    kids.set(j, str.charAt(i));
                    break;
                }
            }
            if(temp) continue;
            kids.add(str.charAt(i));
            k -= str.charAt(i) - 'A';
        }

        if(k < 0) System.out.println("Impossible");
        else System.out.println(kids.size());
    }
}

채점 결과

골4의 난이도가 무색하게 원트클 성공...
문제 푼 사람이 7명밖에 없어서 난이도가 일치하지 않을거라고 생각하긴 했는데, 생각보다 더 쉬웠다.
체감 난이도는 실버 1~3 정도인 것 같다.
난이도 의견을 제출했더니 실버 1이 되어버렸다!