BOJ 28109 - 약속 장소 2

BOJ 28109 - 약속 장소 2

내가 해낸 관찰은 대략 다음과 같이 우선순위가 변한다는 것이다.

AOSTECH 1
BOSTECH 2
COSTECH 3
DOSTECH 4
EOSTECH 5
FOSTECH 6
GOSTECH 7
HOSTECH 8
IOSTECH 9
JOSTECH 10
KOSTECH 11
LOSTECH 12
MOSTECH 13
NOSTECH 14
OOSTECH 15
---
PASTECH 16
PBSTECH 17
PCSTECH 18
PDSTECH 19
PESTECH 20
PFSTECH 21
PGSTECH 22
PHSTECH 23
PISTECH 24
PJSTECH 25
PKSTECH 26
PLSTECH 27
PMSTECH 28
PNSTECH 29
---
POATECH 30
POBTECH 31

따라서 이를 구간합 배열을 잘 써서 그리디로 풀었는데, 더 쉬운 방법이 있다.

<바뀌는 위치, 바뀌는 알파벳> 을 pair 로 두고 정렬을 하는 것이다.

최대 $25N+1$ 개의 가능한 가지수가 있기 때문에 걍 정렬하면 된다.

정렬의 우선순위는 바뀌는 위치가 같다면 알파벳의 사전순대로,

바뀌는 위치가 다르다면 앞에있는 게 원래 문자열보다 사전순으로 앞선다면 앞에있는게 바뀌는게 더 앞으로 와야하고, 원래 문자열이랑 동일하다면 뒤에 있는것의 알파벳의 사전순을 봐야하고, 원래 문자열보다 크다면 앞에 있는 것이 더 뒤로가야한다.

그리디 코드

void solve() {
   int n, k;
   string s;
   cin >> n >> k >> s;
   string ans = s;

   vi small(n + 1), big(n + 1);

   small[n - 1] = s[n - 1] - 'A';
   big[n - 1] = 'Z' - s[n - 1];
   for (int i = n - 2; i >= 0; i--) {
      small[i] = small[i + 1] + s[i] - 'A';
      big[i] = big[i + 1] + 'Z' - s[i];
   }

   if (small[0] + big[0] + 1 < k) {
      cout << -1;
      return;
   }

   for (int i = 0; i < n; i++) {
      // A 부터 s[i] 이전까지 가능한 것
      int c = s[i] - 'A';

      if (k <= c) {
         ans[i] = k - 1 + 'A';
         break;
      }
      k -= c;

      if (small[i + 1] + big[i + 1] + 1 >= k) {
         continue;
      }
      k -= small[i + 1] + big[i + 1] + 1;

      ans[i] = s[i] + k;
      break;
   }
   cout << ans;
}