프로그래머스[Lv.3] - 봉인된 주문

 

 

문제 설명

어느 날, 전설 속에 전해 내려오는 비밀 주문서가 세상에 다시 모습을 드러냈습니다. 이 주문서에는 마법 세계에서 사용되는 모든 주문이 적혀 있는데, 각 주문은 알파벳 소문자 11글자 이하로 구성되어 있습니다. 주문서에는 실제로 마법적 효과를 지니지 않는 의미 없는 주문들 즉, 알파벳 소문자 11글자 이하로 쓸 수 있는 모든 문자열이 고대의 규칙에 따라 아래와 같이 정렬되어 있습니다.

1. 글자 수가 적은 주문부터 먼저 기록된다.
2. 글자 수가 같다면, 사전 순서대로 기록된다. 예를 들어, 주문서의 시작 부분은 다음과 같이 구성됩니다.

• "a"→"b"→"c"→"d"→"e"→"f"→...→"z"
• →"aa"→"ab"→...→"az"→"ba"→...→"by"→"bz"→"ca"→...→"zz"
• →"aaa"→"aab"→...→"aaz"→"aba"→...→"azz"→"baa"→...→"zzz"
• →"aaaa"→...→"aazz"→"abaa"→...→"czzz"→"daaa"→...→"zzzz" →"aaaaa"→...

하지만 이 주문서에는 오래전 봉인된 저주받은 주문들이 숨겨져 있었고, 이를 악용하려는 자들을 막기 위해 마법사들이 몇몇 주문을 주문서에서 삭제했습니다. 당신은 삭제가 완료된 주문서에서 n번째 주문을 찾아내야 합니다.

예를 들어, 주문서에서 "d", "e", "bb", "aa", "ae" 5개의 주문을 지웠을 때, 주문서에서 30번째 주문을 찾으려고 합니다.

• 1~3번째 주문은 "a", "b", "c" 입니다.
• "d"와 "e"는 삭제됐으므로 4~24번째 주문은 "f" ~ "z"입니다.
• "aa"는 삭제됐으므로 25~27번째 주문은 "ab", "ac", "ad"입니다.
• "ae"는 삭제됐으므로 28~30번째 주문은 "af", "ag", "ah"입니다.

따라서 30번째 주문은 "ah"가 됩니다. 삭제된 주문 중 “bb”와 같이 n번째 주문보다 뒤에 위치해 있어서 n번째 주문을 찾는 데 영향을 주지 않는 주문도 존재할 수 있습니다.

정수 n과 삭제된 주문들을 담은 1차원 문자열 배열 bans가 매개변수로 주어질 때, 삭제가 완료된 주문서의 n번째 주문을 return 하도록 solution 함수를 완성해 주세요.

---

 

 

 

 

 

 

제한 사항

• 1 ≤ n ≤ 1015
• 1 ≤ bans의 길이 ≤ 300,000
  
  • bans의 원소는 알파벳 소문자로만 이루어진 길이가 1 이상 11 이하인 문자열입니다.
  • bans의 원소는 중복되지 않습니다.

 

---

 

 

 

 

 

 

풀이

문제를 요약하면, n번째 주문을 구하면 되는데 bans에 주어진 문자를 제외해야 한다.

주문의 순서는 길이를 기준으로 하며 길이가 같다면 사전순으로 정렬한다.

 

문제는 간단하다.

bans에 있는 수만 제외하고 순서를 세면 된다.

하지만, 이를 하나하나 살펴보면 시간 초과가 걸릴 것이다.

이는 수학적으로 해결할 수 있다.

길이순, 사전순이라는 얘기를 보면 이는 n진법과 매우 유사하다.

즉, 알파벳이 26개이므로 26진법이라 생각할 수 있다.

하지만 유의할 점은 해당 진법에서는 0이라는 수가 존재하지 않으니 이에 대한 예외 처리를 해야 한다.

만약, n번째 수를 진법으로 계산하여 구한 문자열을 X라고 해보자.

그럼 bans에서 X보다 작은 것들의 개수만큼 더 뒤로 가야 한다.

만약, bans에 X보다 작은 것들이 없다면 X가 정답이 된다.

 

그럼 X를 구하는 과정부터 살펴보자.

"a" ~ "z"까지는 1~26에 대응된다.

이를 진법을 통해 계산해보면 다음과 같은 식이 성립한다.

//i번째 자리 = xi
xi = n / pow(26, i) % 26;

 26의 i제곱으로 n을 나눈 몫에 26으로 나눈 나머지 연산을 하면 i번째 자리가 결정된다.

2진법으로 검증해보자.

5는 2진법으로 101이다.

0번째 자리는 pow(2,0) = 1로 5를 나눈 몫을 2로 나눈 나머지 연산의 결과인 1이 0번째 자리가 된다.

1번째 자리는 pow(2,1) = 2로 5를 나는 몫을 2로 나눈 나머지 연산의 결과인 1이 1번째 자리가 된다.

마찬가지로 2번째 자리는 1이 된다.

따라서, 101이 5를 2진법으로 변환한 수가 된다.

동일한 원리를 해당 문제에 적용할 수 있다.

하지만, 0이 없이 표현되기 때문에 예외 처리가 필요하다.

만약, 결과가 0이라면 26이 될 것이고 이는 "z"를 의미한다.

따라서, 0을 26으로 변경해 준다.

그리고 그 앞자리에서는 1을 뺀 결과를 저장해야 한다.

뺄 샘에서 내림과 비슷하게 작용한다고 생각하면 된다.

string Find()
{   
    int len = 0;
    vector<int> digit;
    while(pow(num, len) < N)
    {
        int idx = N / (long long)pow(num, len) % num;
        if(idx == 0) idx = num;
        if(!digit.empty() && digit.back() == num-1) idx--;
        digit.push_back(idx - 1);
        len++;
    }
    
    string result;
    
    for(int i = 0; i < digit.size(); i++)
    {
        int d = digit[i];
        
        char temp = d + 'a';
        result += temp;
    }
    
    reverse(result.begin(), result.end());
    
    return result;
}

idx에서 1을 빼는 이유는 'a'는 0부터 시작하기 때문에 연산의 편의를 위해 빼준 것이다.

 

제외한 문자열 없이 n번째 문자열인 X를 찾아냈다면 bans에서 X보다 앞에 있는 것들의 개수를 세면 된다.

sort(bans.begin(), bans.end(), [](string& a, string& b){
    if(a.length() == b.length()) return a < b;
    return a.length() < b.length();
});

int pos = 0;
for(; pos < bans.size(); pos++)
{
    auto bansLen = bans[pos].length();
    auto targetLen = target.length();

    if(bansLen > targetLen) break;
    else if(bansLen == targetLen)
    {
        if(bans[pos] > target) break;
    }
}

 pos는 문자열을 다음으로 넘겨보며 다시 제외할 문자열을 찾는 커서 역할을 하게 된다.

int cnt = pos;
while(cnt > 0)
{
    auto next = NextMove(target);
    target = next;

    if(pos >= bans.size())
    {
        cnt--;
        continue;
    }

    if(bans[pos] != next) cnt--;
    if(bans[pos] <= next) pos++;
}

NextMove는 다음 수를 찾는 함수이다.

다음 수를 찾는 방법은 마지막 문자에 1을 더한 뒤 올림이 필요하다면 연쇄적으로 계산하는 것이다.

string NextMove(string target)
{
    int idx = target.length() - 1;
    int carry = 0;
    string result;
    
    int temp = target[idx] - 'a';
    temp++;
    if(temp < num)
    {
        result = target;
        result[idx] = temp + 'a';
    }
    else
    {
        while(idx >= 0)
        {
            carry += temp / num;
            temp %= num;
            
            result += temp + 'a';
            idx--;
            
            temp = target[idx] - 'a' + carry;
            carry = 0;
        }
    
        if(carry != 0)
        {
            result += carry + 'a';
        }
    
        reverse(result.begin(), result.end());
    }
    
    return result;
}

---

 

 

 

 

 

전체 코드

#include <string>
#include <vector>
#include <bits/stdc++.h>

using namespace std;
long long N;
int num = 26;

string Find()
{   
    int len = 0;
    vector<int> digit;
    while(pow(num, len) < N)
    {
        int idx = N / (long long)pow(num, len) % num;
        if(idx == 0) idx = num;
        if(!digit.empty() && digit.back() == num-1) idx--;
        digit.push_back(idx - 1);
        len++;
    }
    
    string result;
    
    for(int i = 0; i < digit.size(); i++)
    {
        int d = digit[i];
        
        char temp = d + 'a';
        result += temp;
    }
    
    reverse(result.begin(), result.end());
    
    return result;
}

string NextMove(string target)
{
    int idx = target.length() - 1;
    int carry = 0;
    string result;
    
    int temp = target[idx] - 'a';
    temp++;
    if(temp < num)
    {
        result = target;
        result[idx] = temp + 'a';
    }
    else
    {
        while(idx >= 0)
        {
            carry += temp / num;
            temp %= num;
            
            result += temp + 'a';
            idx--;
            
            temp = target[idx] - 'a' + carry;
            carry = 0;
        }
    
        if(carry != 0)
        {
            result += carry + 'a';
        }
    
        reverse(result.begin(), result.end());
    }
    
    return result;
}

string solution(long long n, vector<string> bans) {
    N = n;
    
    string target = Find();
    
    sort(bans.begin(), bans.end(), [](string& a, string& b){
        if(a.length() == b.length()) return a < b;
        return a.length() < b.length();
    });
    
    int pos = 0;
    for(; pos < bans.size(); pos++)
    {
        auto bansLen = bans[pos].length();
        auto targetLen = target.length();
        
        if(bansLen > targetLen) break;
        else if(bansLen == targetLen)
        {
            if(bans[pos] > target) break;
        }
    }
    
    int cnt = pos;
    while(cnt > 0)
    {
        auto next = NextMove(target);
        target = next;
        
        if(pos >= bans.size())
        {
            cnt--;
            continue;
        }
        
        if(bans[pos] != next) cnt--;
        if(bans[pos] <= next) pos++;
    }
    
    return target;
}

---