백준 31784번
https://www.acmicpc.net/problem/31784

문제

---

생각하기

---

• 문자열, 그리디 문제이다.

동작

index를 증가하면서 문자열을 사전순으로 가장 빠르게 만들면된다.

K는 모두 소진해야 한다.

        int idx = 0;
        while (K > 0) {
            if (idx == N - 1) {
                // 나머지 처리
                K %= 26;
                if (K > 'Z' + 1 - chArr[idx]) {
                    K -= 'Z' + 1 - chArr[idx];
                    chArr[idx] = 'A';
                }
                chArr[idx] += K;
                K = 0;
            } else {
                if (chArr[idx] == 'A') {
                    idx++;
                    continue;
                } else {
                    int count = 'Z' - chArr[idx] + 1;
                    if (count <= K) {
                        chArr[idx] = 'A';
                        K -= count;
                        idx++;
                    } else {
                        idx++;
                    }
                }
            }
        }

처음 문자부터 하나씩 확인한다.
이미 ＇A＇인 값들은 굳이 수정할 필요 없으므로 통과.
그리고 K를 이용해서 ＇A＇를 만들 수 있는지 계속 확인한다. ＇A＇를 만들 수 있으면 K를 ＇A＇로 만드는 데 필요한 회전수만큼 빼주고 만약 회전해서 ＇A＇를 만들 수 없다면 그 문자는 선택하지 않는다 -> 이 부분이 그리디

이후 다른 문자에서 사용하지 못한 남은 K 값을 가장 마지막 문자에서 사용한다.

A를 만들 수 있으면 A부터 시작하고, 아닐 경우 나머지 연산을 통해서 회전 후 남은 K값으로 문자를 증가시키면 된다.

결과

코드

---

Java

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

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, K;
    private static String S;
    private static char[] chArr;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        int idx = 0;
        while (K > 0) {
            if (idx == N - 1) {
                // 나머지 처리
                K %= 26;
                if (K > 'Z' + 1 - chArr[idx]) {
                    K -= 'Z' + 1 - chArr[idx];
                    chArr[idx] = 'A';
                }
                chArr[idx] += K;
                K = 0;
            } else {
                if (chArr[idx] == 'A') {
                    idx++;
                    continue;
                } else {
                    int count = 'Z' - chArr[idx] + 1;
                    if (count <= K) {
                        chArr[idx] = 'A';
                        K -= count;
                        idx++;
                    } else {
                        idx++;
                    }
                }
            }
        }

        for (int i = 0; i < N; i++) {
            sb.append(chArr[i]);
        }

        return sb.toString();
    } // End of solve()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        S = br.readLine();
        chArr = S.toCharArray();
    } // End of input()
} // End of Main class

Kotlin

import java.io.BufferedReader
import java.io.File
import java.util.StringTokenizer

// input
private var br = System.`in`.bufferedReader()

// variables
private var N = 0
private var K = 0
private lateinit var chArr: CharArray

fun main() {
    val bw = System.out.bufferedWriter()

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    // 앞쪽을 최대한 A로 만들고 나머지를 뒤에서 처리하는 방식
    var idx = 0
    while (K > 0) {
        if (idx == N - 1) {
            K %= 26
            if (K > ('Z' + 1) - chArr[idx]) {
                // A로 만들 수 있으면 회전해서 A에서 시작
                K -= ('Z' + 1) - chArr[idx]
                chArr[idx] = 'A'
            }

            // 나머지 K횟수 활용
            chArr[idx] = (chArr[idx] + K).toChar()
            K = 0 // K 모두 소진 처리
        } else {
            if (chArr[idx] == 'A') {
                idx++
                continue
            }

            val count = ('Z' + 1) - chArr[idx]
            if (count <= K) {
                chArr[idx] = 'A'
                K -= count
                idx++
            } else {
                idx++
            }
        }
    }

    chArr.forEach {
        sb.append(it)
    }

    return sb.toString()
} // End of solve()

private fun input() {
    val st = StringTokenizer(br.readLine())
    N = st.nextToken().toInt()
    K = st.nextToken().toInt()
    chArr = br.readLine().toCharArray()
} // End of input()