AtCoder Beginner Contest 009 C: 辞書式順序ふたたび
解法
前の方から貪欲に決めていく。
コード
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(); } }