読者です 読者をやめる 読者になる 読者になる

AtCoder Beginner Contest 009 C: 辞書式順序ふたたび

問題

abc009.contest.atcoder.jp

解法

前の方から貪欲に決めていく。

コード

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public void solve() {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int K = scanner.nextInt();
		char[] str = scanner.next().toCharArray();
		scanner.close();

		int[] strCnt = new int[26];
		for (int i = 0; i < N; i++) {
			strCnt[str[i] - 'a']++;
		}
		int[] restCnt = Arrays.copyOf(strCnt, 26);

		StringBuilder ans = new StringBuilder();
		for (int i = 0; i < N; i++) {
			// i文字目を決めよう
			for (int j = 0; j < 26; j++) {
				// アルファベットを小さい順に見ていく
				if (restCnt[j] == 0) {
					// アルファベットjがもう残っていない場合はスルー
					continue;
				}
				int c = str[i] - 'a';

				// アルファベットjがstrのi文字目と一致する場合はそれを使う
				if (c != j) {
					// アルファベットjがstrのi文字目と一致しない場合
					int cost = 0; // 発生する不一致の数
					if (strCnt[j] >= restCnt[j]) {
						// i文字目にjを使ってしまうと
						// strの他の部分にあるjと必ず不一致が生まれる場合
						cost++;
					}
					if (strCnt[c] <= restCnt[c]) {
						//i文字目にcを使わなかったことによって
						//
						cost++;
					}
					if (K < cost) {
						continue;
					}
					K -= cost;
				}
				strCnt[c]--;
				restCnt[j]--;
				ans.append((char) (j + 'a'));
				break;
			}
		}
		System.out.println(ans.toString());
	}

	public static void main(String[] args) {
		new Main().solve();
	}

}