[Programmers] 봉인된 주문 - Java

문제 

프로그래머스

 

풀이

기존에 생각했던 풀이는 다음과 같다.

1. 그냥 N번째에 해당하는 문자열을 찾는다.

2. ban에 있는 그 문자열보다 작은 애들의 개수를 센다.

3. 작은 애들 갯수 + N번째 문자열이 n번째 주문이라고 생각했다.

 

하지만 예외 상황이 존재했다.

O : ban 당하지 않은 문자열

X : ban 당한 문자열

이라고 가정해보자.

 

모두 사전순으로 바로 인접되게 정렬되어있다고 가정한다.(ab, ac와의 관계)

XXXOXXXOXXXXXXXX라고 했을때, 두번째 문자열을 구한다고 가정하면, ban이 당한 문자열이 반환이 될 수 있는 문제가 존재했다.

 

그리고 데이터의 순서를 보장하기 위해, Queue를 선택했다.(인덱스 변수 두고, 비교해도 동일하다고 생각한다.)

1. 정렬되어있는 데이터순으로 보여질 수 있으며,

2. 데이터를 삭제를 안해도 볼 수 있는 연산도 존재하는 장점이 있었기 때문이다.(peek 연산)

 

풀이는 다음과 같다.

1. 문자열의 길이 > 사전 순서대로 정렬한다.

2. 큐를 사용해서 정렬되어 있는 문자열을 넣는다.(순서 보장)

3. 삭제 문자열과 n번째 문자열을 비교하면서, n번째 문자열보다 삭제 문자열이 사전순으로 앞서거나, 길이가 작은 경우 n을 증가시키고, 다음 삭제 문자열을 비교한다.

4. while문을 빠져나왔을때의 n에 대한 문자열을 반환한다.

 

시간복잡도: O(26진법 만드는 연산(상수) * 300000)이다.

소스코드

import java.util.*;

class Solution {
    public String solution(long n, String[] bans) {
        Arrays.sort(bans, (s1, s2) -> {
            if (s1.length() == s2.length()) {
                return s1.compareTo(s2);
            }
            
            return s1.length() - s2.length();
        });
        
        ArrayDeque<String> queue = new ArrayDeque<>();
        
        for (String b : bans) { 
            queue.addLast(b);
        }
        
        while (!queue.isEmpty()) {
            //삭제 문자열
            String banStr = queue.peekFirst();
            
            //현재 n번째 문자열
            String order = createOrder(n);
            
            //제거되어야하는 글자 수가 더 작으면 밀려야함
            if (banStr.length() < order.length()) {
                queue.removeFirst();
                n += 1;
            //글자의 길이가 동일하면서, banStr이 동일하거나 사전순으로 앞이어도 밀어야함
            } else if (banStr.length() == order.length() && banStr.compareTo(order) <= 0) {
                queue.removeFirst();
                n += 1;
            //이 모든 조건이 아니면, 사전 순으로 지난 문자열이므로, while 루프를 빠져나옴
            } else {
                break;
            }
        }
        
        return createOrder(n);
    }
    
    private String createOrder(long n) {
        StringBuilder sb = new StringBuilder();
        int alphaCnt = 'z' - 'a' + 1;
        
        while (n != 0) {
            int rest = (int) (n % alphaCnt);
            n /= alphaCnt;
            
            //26으로 나누어 떨어지면, 'z'를 붙임
            if (rest == 0) {
                n -= 1;
                sb.append('z');
            } else {
                sb.append((char) ('a' + rest - 1));
            }
        }
        
        return sb.reverse().toString();
    }
}

 

큐를 사용하지 않고, 인덱스 변수 둔 코드도 구현해봤다.

import java.util.*;

class Solution {
    public String solution(long n, String[] bans) {
        Arrays.sort(bans, (s1, s2) -> {
            if (s1.length() == s2.length()) {
                return s1.compareTo(s2);
            }
            
            return s1.length() - s2.length();
        });
        
        int idx = 0;
        
        while (idx != bans.length) {
            //삭제 문자열
            String banStr = bans[idx];
            
            //현재 n번째 문자열
            String order = createOrder(n);
            
            //제거되어야하는 글자 수가 더 작으면 밀려야함
            if (banStr.length() < order.length()) {
                idx += 1;
                n += 1;
            //글자의 길이가 동일하면서, banStr이 동일하거나 사전순으로 앞이어도 밀어야함
            } else if (banStr.length() == order.length() && banStr.compareTo(order) <= 0) {
                idx += 1;
                n += 1;
            //이 모든 조건이 아니면, 사전 순으로 지난 문자열이므로, while 루프를 빠져나옴
            } else {
                break;
            }
        }
        
        return createOrder(n);
    }
    
    private String createOrder(long n) {
        StringBuilder sb = new StringBuilder();
        int alphaCnt = 'z' - 'a' + 1;
        
        while (n != 0) {
            int rest = (int) (n % alphaCnt);
            n /= alphaCnt;
            
            if (rest == 0) {
                n -= 1;
                sb.append('z');
            } else {
                sb.append((char) ('a' + rest - 1));
            }
        }
        
        return sb.reverse().toString();
    }
}