[프로그래머스] 봉인된 주문 - java

문제 설명 :

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

프로그래머스

 

문제 요약 :

1. 사전순 문자열 리스트에 대해 특정 문자열을 삭제 한 후의 특정 인덱스의 문자열 구하기

 

문제 풀이 시간 : 1시간 30분

문제 성공 여부 : 실패

 

접근 방법(실패) :

1. n을 26진수로 변환하여 해당하는 String을 구한다.
2. 해당 String 보다 작은 ban 개수를 파악한다.
3. 해당 String에서 보다 작은 ban 개수를 뺀 String을 구해준다.

 

실패 이유 :

우선 26진수 변환 코드부터 잘못된 부분이 있었다.

while(){
    mod = n % 26;
    n /= 26;
    
    arr26.add(mod);
}

 

다음과 같이 26진수로 변환하였는데, 이 경우 z에 대한 계산이 불가능해진다.

 

예를 들어, n이 26일 경우

z가 되어야 정상이지만 내 경우 aa가 되어버린다.

 

이상함을 깨달았지만 결국 주어진 시간 내에 해결책을 떠올리지 못하였다.

 

 

다음으로는, 해당 String보다 작은 ban 개수를 파악하는 과정에 문제가 있다.

 

예를 들어 n이 5이고, b,c,f를 제거해야 할 때, 내 로직은 5는 e이므로 b,c만 제거하게 된다.

하지만 정상적인 로직대로라면, b,c가 제거된 만큼 다음 문자열들이 앞으로 당겨지기 때문에 f도 제거해주어야 한다.

 

내 코드는 이 경우를 놓치고 있었다.

 

결국 오류를 찾고 해결하는 과정에서 제한 시간 1시간을 넘겨버려 실패하게 되었다.

 

접근방법(성공)

1. n보다 작은 ban을 삭제해야할 때, n의 값을 증가시켜준다.(동기화)
2. 이를 반복하여 삭제 가능한 모든 ban의 개수를 더한 n을 문자열로 변경한다.

 

이전 방법에 비해 시간은 더 소모될 수 있지만, 코드적으로 매우 효율적인 로직이다.

 

bans는 최대 30만 이기때문에 O(n)으로도 충분한 시간복잡도가 나온다.

 

import java.util.*;
class Solution {
    public String solution(long n, String[] bans) {
        Arrays.sort(bans, (o1, o2) -> { // bans 사전순 정렬
            if(o1.length() == o2.length()) return o1.compareTo(o2);
            return o1.length() - o2.length();
        });
        
        for(int i=0; i<bans.length; i++){ // ban와 n 문자열 비교
            String ban = bans[i];
            String s = getString(n);
            
            int b_len = ban.length();
            int s_len = s.length();
            
            if(b_len > s_len) break;
            
            // ban이 n문자열보다 작을 경우 n+1을 해준다.
            if(b_len < s_len) n++;
            else if(b_len == s_len && ban.compareTo(s) <=0) n++;
        }
        
        return getString(n); // 마지막 n에 대한 문자열을 반환해준다.
    }
    
    static String getString(long n){ 숫자 n을 26진법으로 변환하여 문자열로 반환
        StringBuilder s = new StringBuilder();
        while(n>0){
            int mod = (int)(n%26);
            n/=26;
            if(mod == 0){ // 26의 배수일 경우 z로 변환하고 다음 비트 -1을 해준다.
                s.append('z');
                n--;
            }
            else{ // 0 : a, ... 로 가기 때문에 -1을 수행해준다.
                s.append((char)('a'+ mod-1));
            }
        }
        return s.reverse().toString();
    }
}