[프로그래머스] Level 3: 봉인된 주문

https://school.programmers.co.kr/learn/courses/30/lessons/389481

프로그래머스

 

먼저, 봉인된 주문을 순서대로 정렬한다.

내가 찾으려는 n번째 안에 봉인된 주문이 없으면 계산할 필요가 없기 때문이다.

내가 10번째 문자를 찾는데, 그 안에 3개의 문자가 봉인되었다면, 그냥 13번째 문자를 찾으면 된다.

 

일단 이렇게 봉인된 주문을 고려한 최종적으로 찾아야 할 순번을 구한다.

 

다음으로, 이제 이 순번의 문자를 구하면 된다.

일단 절대로 for문으로 이를 하나씩 올리는 건 불가능하다.

 

찾으려는 문자의 순번을 보면, 정답이 몇 자리인지 알 수 있다.

1 ~ 26이라면, 최소 "a"에서, 최대 "z"까지 가능하다.

27 ~ 676이라면, 최소 "aa"에서, 최대 "zz"까지 가능하다.

 

각 문자열 자리의 a가 b가 되기 위해서는, 나보다 작은 자리의 문자들이 모두 z가 된 후에 1이 더해져야 한다.

이를 고려했을 때, 각 자리 순서대로 문자 순번을 나눈 몫이 구하려는 문자열의 문자 이게 된다.

 

문제 입출력 예 2번을 보면, 봉인된 문자를 제외하고 7392번째의 문자를 찾아야 한다.

7392번째는 계산해 보면, 최대 3자리의 문자열만이 올 수 있다. (즉, 정답은 "zzz"보다 작은 문자열)

 

그러면 이제 각 자리별로 a가 b가 되기 위한 수들을 구해 배열로 저장한다.

이때, 제일 앞자리가 올라간 후, 뒤에 자리들을 모두 "a"로 채워주기 위해서는, 이전 문자가 "z"가 되는 수를 빼줘야 한다.

• a가 b가 되기 위해서는 1이 필요 (1 - 0)
• aa가 ba가 되기 위해서는 26이 필요 (27 - 1)
• aaa가 baa가 되기 위해서는 676이 필요 (702 - 26)
• ...

 

문제 입출력 예 2번으로 예를 들어보자.

• 봉인된 주문을 정렬한다.
• 정렬된 봉인된 주문들을 순회하며, 찾으려는 n번째 주문 안에 속해있는지 검사하고, 속해있으면 1씩 올린다.
  • 봉인된 주문이 "gqk"인 경우를 계산해 보자.
  • "aaa"에서 "gaa"가 되려면, 4056번째여야 한다. ( g - a  = 6, 6 * 676 = 4056)
  • "gaa"에서 "gqa"가 되러면, 4472번째여야 한다. ( q - a = 16, 16 * 26 = 416, 4056 + 416 = 4472)
  • "gqa"에서 "gqk"가 되러면, 4482번째여야 한다. ( k - a = 10, 10 * 1 = 10, 4472 + 10 = 4482)
  • 즉, "gqk"는 4482번째 주문이므로, 찾으려는 7388번째 안에 속해있기 때문에, 찾으려는 수를 1 올린다.
• 이렇게 최종적으로 찾아야 할 n번째를 구하면, 7395번째 문자를 찾게 된다.
• 그러면, 찾으려는 문자 3개에서 가장 큰 비중을 차지하는 앞 문자부터 찾는다.
  • 7395에서 뒤에 a를 갖추기 위한 26을 뺀다. ( 7395 - 26 = 7369 )
  • 7369를 676으로 나눈 몫을 구한다. (반내림)
    • 7369 / 676 = 10
    • 즉, 가장 앞 문자는 알파벳 10번째 문자이다. "j"
• 앞 문자를 구하고 남은 나머지를 가지고, 다음 문자를 구한다.
  • 635에서 뒤에 a를 갖추기 위한 1을 뺀다. ( 635 - 1 = 634 )
  • 634를 26으로 나눈 몫을 구한다. (반내림)
    • 634 / 26 = 24
    • 즉, 두 번째 문자는 알파벳 24번째 문자이다. "x"
• 앞 문자를 구하고 남은 나머지를 가지고, 다음 문자를 구한다.
  • 12가 남았고, 이는 마지막 자리이므로 가장 마지막 문자는 알파벳 12번째 문자이다. "k"
• 최종적으로 "jxk"이다.

#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

// 수가 작은 순서대로(a > aa)
// 알파벳 순서대로(aa > ca)
bool cmp(const string& str1, const string& str2)
{
	if (str1.size() != str2.size()) return str1.size() < str2.size();
	for (int i = 0; i < str1.size(); ++i)
		if (str1[i] != str2[i]) return str1[i] < str2[i];
}

string solution(long long n, vector<string> bans) {
	string answer = "";

	// 봉인된 주문을 순서대로 정렬
	// n번째 주문 탐색에 고려해야하는 주문만 판별하기 위함
	sort(bans.begin(), bans.end(), cmp);

	// z, zz, zzz, zzzz...의 순번
	// [1 * 26], [26 * 26], [17576 * 26]...
	vector<long long> Grade
	{
		0, 1, 26, 676, 17576, 456976, 11881376, 308915776, 8031810176,
		208827064576, 5429503678976, 141167095653376
	};

	// 봉인된 주문을 순회하며, n번째 주문을 찾는 데 고려해야하는지 판별
	// ex. 1번째 주문을 탐색하는데, 봉인된 주문이 z라면, 고려할 필요가 없기 때문
	for (const auto& ban : bans)
	{
		long long Num = 0;
		for (int i = 0, Index = ban.size(); i < ban.size(); ++i, --Index)
			Num += Grade[Index] * (ban[i] - 96);
		if (Num <= n) n++;
	}

	// 가장 큰 수 부터 나눔
	for (int i = 11; i >= 0; --i)
	{
		if (Grade[i] > n) continue;

		// 알파벳은 0이 없기 때문에, 정확히 나누어 떨어질 수 없음 (1 ~ 26)
		// a가 되려면, 이전의 zzz...의 값을 한 번 뺴줌, 그래야 뒤에가 최소 a가 남게됨
		int div = (double)floor((double)(n - Grade[i - 1]) / (double)Grade[i]);
		if (div > 0)
		{
			n -= Grade[i] * div;
			answer += 96 + div;
		}
	}

	return answer;
}