[백준 20191번-C++] 줄임말

http://acmicpc.net/problem/20191

{코드}

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int solution() {
  string S, T;
  cin >> S; cin >> T;
  vector<vector<int> > next(26);
  for (int i = 0; i < T.length(); i++) {
    next[T[i]-'a'].push_back(i);
  }

  int chkCnt = 0, chkIdx;
  for (int i = 0; i < 26; i++) {
      if (!next[i].empty()) {chkCnt++; chkIdx = i;}
  }
  if (chkCnt == 1 && T[chkIdx] == S[0]) return (S.length()+T.length()-1)/T.length();

  int cnt = 1, pos = -1, before_pos = -1;
  for (const char &c : S) {
    int k = c - 'a';
    if (next[k].empty()) return -1;

    int left = 0, right = next[k].size();
    while (left < right) {
      int mid = (left + right) / 2;
      if (before_pos < next[k][mid]) right = mid;
      else left = mid + 1;
    }
    pos = left;
    if (pos == next[k].size()) {
      cnt++;
      pos = 0;
    }
    before_pos = next[k][pos];
  }

  return cnt;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout << solution();
}

{설명}

우선, S와 T를 입력받고 T에 등장하는 알파벳의 인덱스를 next라는 배열에 저장합니다.

이렇게 하면 실제로 문자열을 늘려가며 확인할 필요가 없이 S의 각 문자를 next를 이용해 인덱스 별로 찾고 만약 없다면 문자열을 추가하거나 -1을 반환하면 됩니다.

먼저 S와 T의 알파벳이 하나로만 구성되어 있고 둘이 같은 경우 수식을 통해 바로 답을 반환합니다.

*수식이 저렇게 나오는 이유는 S의 길이를 T로 나누는 데, 나머지가 생길 경우 1을 추가해야 하기 때문에 T의 길이를 더합니다. 다만, 나머지가 0인 경우, T의 길이를 그대로 더하면 원래 답보다 1이 추가되므로 -1을 해줍니다.

위의 경우를 제외하였으니 이제 S의 각 문자 별로 next에서 찾으면 됩니다.

이때, next에 해당 알파벳에 대한 인덱스가 없다는 것은 T에 존재하지 않는다는 뜻이므로 줄임말이 아니기에 -1을 반환합니다.

그 외의 경우는 줄임말이라고 판단해 현재 탐색한 인덱스보다 큰 인덱스 중에서 해당 알파벳이 등장하는 인덱스를 찾습니다.

위의 코드에서 before_pos는 이전 루프에서 탐색한 결과를 저장하는데 결국 before_pos보다 큰 값 중에 찾으려는 알파벳이 등장해야 T를 늘릴필요가 없는 것입니다.

인덱스를 찾는 방법은 이분탐색을 통해 찾는데, 이분 탐색은 정렬된 배열에서 배열의 중간 값을 기준으로 배열을 그 왼쪽이나 오른쪽으로 한정하여 다시 중간을 기준으로 탐색하는 것입니다.

이분 탐색의 결과는 찾으려는 값이 처음으로 등장할 장소나 찾으려는 값보다 큰 값이 처음으로 등장하는 장소를 리턴하는데 위의 경우는  보다 큰 값이 처음으로 등장하는 장소를 찾게 됩니다.

*만약 배열이 [2, 3, 4, 4, 4, 5, 7, 9] 라면, 찾으려는 값이 4일 때, 5를 반환합니다.

이러면 만약 현재 탐색한 인덱스보다 뒤에 등장하지 않으면 길이가 n인 배열에서 n을 반환하기 때문에 배열의 길이와 pos가 같으면 T를 늘린다는 의미에서 cnt를 1 증가하고 해당 알파벳이 처음 등장하는 인덱스를 before_pos가 갖도록 pos를 0으로 바꿉니다.

예시: (설명을 위해 next의 인덱스를 알파벳으로 표현하겠습니다.)

S = 'caa', T = 'ac'

next['a'] = [0] | next ['c'] = [1]

cnt=0, pos=-1, before_pos=-1

----

c = 'c'

이분 탐색 후 pos = 0, before_pos = 1

----

c = 'a'

이분 탐색 후 pos = 1, 배열의 길이와 같으므로 cnt+1, pos=0, before_pos = 0

----

c = 'a'

이분 탐색 후 pos = 1, 배열의 길이와 같으므로 cnt+1, pos=0, before_pos = 0

----

cnt=3 반환

 

*이 문제를 처음에는 T를 늘려가며 투 포인터를 통해 풀려고 했는데 시간 초과가 나서 찾아보다가 인덱스를 저장하며 풀길래 저도 코드를 따라해보며 이분 탐색을 넣었는데 처음에는 함수로 만들어서 했다가 계속 마지막 부분문제에서 시간초과가 걸리더라고요. 지금 생각하면 next[k]의 값을 인자로 그대로 넣어버려서 그런 것 같은데 참조를 했다면 시간초과가 안 났을 것 같네요. 파이썬은 기본이 참조라 그냥 생각 없이 한 거였는데 다시 참조와 포인터를 살펴봐야겠습니다.