[Programmers] 프로그래머스 Lv.3 봉인된 주문 문제풀이(C++) - 2025 프로그래머스 코드챌린지 2차 예선

핵심: 26진법임을 생각해내기 + 0의 개념이 없음을 깨닫기

 

알파벳 개수인 26개가 넘어가면 자릿수가 넘어간다는 점을 떠올리면 문제가 쉬워진다. 오른쪽 자리부터 26^0, 26^1, ... 이런 식의 의미를 지니기 때문.

그리고 0의 개념이 없다는 것을 이해하는 데 좀 시간이 걸렸다.

보통 10진법에서 9가 넘어가면 10이 되는데, 여기서는 "z" 다음에 "aa"가 된다.

자릿수가 넘어갈 때 같은 문자열 2개가 나오는 것으로 보아, 9 다음 11이 나오는 것과 같은 이치. 0이 없다고 볼 수 있다.

 

26진법이라면, 원래라면 26에 자릿수가 다음으로 넘어가야 정상이다.(10진법이 9 -> 10에 자릿수가 하나 늘어나는 것처럼)

하지만, 0의 개념이 없는 이 문제에서는 26에 다음 자리로 넘어가지 않고, "z"라는 문자열로 한 자리 수를 유지한다.

그리고 그 다음 27이 되어서야 "aa"라는 두 자리 문자열이 생긴다.

 

즉, 기존 진법 계산에서 자릿수가 넘어가는 지점에서의 계산이 특이해진다.

여기서는 나머지가 0일 때 자릿수를 넘기지 말고, 그 상위 자릿수를 1 내려서 26을 의미하는 "z"를 유지해야 한다.

 

근데 bans sort함수에서 길이 고려 안하고 사전 순으로만 정렬해놓고 한참 시간 까먹었음... 꼼꼼히 보는 습관을 길러야겠다.

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

/*
16:35 시작

<문제>
주문서 내용: 알파벳 소문자 11글자 이하
    1. 글자 수가 적은 주문부터 기록
    2. 글자 수가 같다면, 사전 순서대로 기록

몇몇 주문을 마법사들이 삭제했는데, 삭제 완료된 주문서에서 n번째 주문을 찾아내야 함

정수 n, 삭제된 주문들을 담은 1차원 문자열 배열 bans 주어짐
삭제 완료된 주문서의 n번째 주문 return

n <= 10^15
bans 길이 <= 30만
    중복 x, 알파벳 소문자로만 이루어진 길이 1~11 문자열

<풀이>
bans 각 주문이 몇 번째 인지를 알아내는게 관건인 것 같음
특정 문자열 줬을 때, 몇 번째인 지를 바로 알 수 있어야 함
일단 글자 수로
표시를 따져보면, 26진법인 거 같음
a:1, b:2, ... z:26
aa: 27

ex) abcd = a*26^3 + b*26^2 + c*26 + d

for bans 돌면서
    각 대응 숫자 구하기(target)
    
    if target <= n:
        n++
    else if target > n:
        pass

이렇게 했을 때의 n번을 구하기


def n번째 구하는 법

	정답 문자열 = ""

	while (true):
    	나머지 구하기
    	몫을 그 다음자리로 올리고, 나머지는 현재 자리로 지정
        	가장 앞에 해당 알파벳 추가
    
    	n/=26
    	나누고 나서 n이 26보다 작으면:
        	해당 알파벳 앞에 추가하고 끝
    

0 개념이 없음
z 다음 바로 aa임
즉, 9 다음 10이 아니라 11

<시간>
bans 정렬: O(nlogn)

bans 도는 것: 30만
    각 대응 숫자 구하기: O(11)
    n-1번째 문자열 구하기: O(11)

-> 총 30만 언저리

*/

//대응 문자열의 숫자 구하기(몇 번째 인지)
long long get_num(string ban){
    
    long long ans = 0;
    vector<long long> digit;    // 여기에 각 26^0, 26^1, ... 넣을 예정
    
    digit.push_back(1);
    
    //11자리 배치
    for(int i=1; i<=11; i++){
        digit.push_back(digit[i-1]*26);
    }
    
    //역순으로 알파벳 계산
    for(int i= ban.size()-1; i>=0; i--){
        
        int digit_num = ban.size()-i-1;   //현재 자릿수
        int alphabet = int(ban[i]) - int('a') + 1;   //현재 알파벳       
        ans += (digit[digit_num]*alphabet);
    }
    return ans;
}

//n번째 문자열 구하기
string get_str(long long num){
    
    string ans = "";
    
    while (num > 0){
        int remain = num % 26; // 나머지
        long long int quote = num / 26; // 몫
        
        string target;
        
        if (remain == 0){
            target = "z";
            num-=26;
            quote-=1;
        }
        else{
            target = string(1, char(int('a') + remain -1));
        }
        
        ans = target + ans;    //ans 앞에 나머지 붙이기
        
        if (quote == 0)
            break;
        else if(quote <= 26){
            target = string(1, char(int('a') + quote -1));
            ans = target + ans;
            break;
        }
        else{
            num/=26;
        } 
    }
    return ans;
    
}

bool cmp(const string &a, const string &b){
    if (a.length() != b.length()) 
        return a.length() < b.length();
    return a < b;
}

string solution(long long n, vector<string> bans) {
    string answer = "";
    
    sort(bans.begin(), bans.end(), cmp);
    
    for (int i=0; i<bans.size(); i++){
        string ban = bans[i];
        long long target = get_num(ban);   //target 대응 숫자 구하기        
        
        if(target <= n) n++;  
    }
    
    //이렇게 했을 때 n번째 문자열 구하기
    answer = get_str(n);
    return answer;
}