백준 31784번 [포닉스의 문단속](C++) -yes6686- 티스토리

백준 문제 풀이: 31784 (포닉스의 문단속)

---

문제 링크: https://www.acmicpc.net/problem/31784

문제 설명:

주어진 문자열의 각 문자를 **A**로 변경하려고 합니다. 문자를 변경할 때, 알파벳 Z까지의 남은 이동 횟수가 **k**보다 작으면, 문자를 **A**로 바꾸고 남은 이동 횟수를 **k**에서 차감합니다. 문자열 끝에 도달하면 남은 횟수 **k**를 이용해 마지막 문자를 조정합니다. 최종 문자열을 출력하는 문제입니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k; // 문자열 길이 n, 이동 횟수 k
    cin >> n >> k;
    string s;
    cin >> s;

    // 문자열 처리
    for (int i = 0; i < s.size(); i++) {
        if ('Z' - s[i] < k && s[i] != 'A') { // Z까지의 거리보다 k가 크면 A로 변경
            k -= (('Z' - s[i]) + 1); // 남은 k에서 이동 거리 차감
            s[i] = 'A'; // 문자 변경
        }

        // 마지막 문자에 남은 k를 처리
        if (i == s.size() - 1) {
            k %= 26; // 남은 이동 횟수를 26으로 나눈 나머지 계산
            int updatedChar = (int)s[i] + k; // 현재 문자에서 k만큼 이동
            if (updatedChar > 'Z') { // Z를 넘어가면 다시 A로 돌아감
                updatedChar = (updatedChar % 'Z') + 'A' - 1;
            }
            s[i] = (char)updatedChar; // 마지막 문자 업데이트
        }
    }

    cout << s << '\n'; // 결과 출력
    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 핵심 알고리즘: 문자열을 한 문자씩 탐색하면서 이동 횟수 **k**를 활용해 문자를 **A**로 변경하거나 마지막 문자를 조정합니다.
• 구현 세부사항:
  • 'Z' - s[i]: 문자 s[i]에서 Z까지 남은 거리입니다.
  • 남은 이동 횟수 k가 충분하면 해당 문자를 **A**로 바꿉니다.
  • 문자열의 마지막 문자에 대해 k % 26으로 이동을 최적화하고 알파벳 범위를 초과하면 다시 **A**로 돌아가게 처리합니다.
• 시간 복잡도 분석:
  • 문자열의 길이가 **n**일 때, 문자열을 한 번 순회하므로 시간 복잡도는 O(n)입니다.

---

결과

주어진 문자열과 이동 횟수를 바탕으로 조건에 따라 문자를 변경한 최종 문자열을 출력합니다.

• 입력 예시:

  5 28  
  PHONX

• 출력 예시:

  AAAAZ

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!