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

 

 

 

---

프로그래머스

 

문제 풀이 설명 (summary)

• 금지된 목록을 모두 숫자로 변환하고 오름차순으로 정렬
• 최대 금지 항목이 30만개 이므로 이분 탐색으로 정렬하여 현재 n값보다 작은 갯수가 몇개인지 파악하여 추가
• 금지항목 갯수만큼 n에 추가하고, 추가값도 반복해서 카운팅하고
• 최종 카운트를 문자열로 바꿔서 출력한다. 

 

문제 풀이 접근법

• 26진법을 사용한다. 
• 알파벳 하나하나 숫자로 해시맵에 저장
• 문자열을 숫자로 변환하는 메서드 활용
• 숫자를 문자열로 변환하는 메서드 활용

 

풀이 코드 (Code)

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Main {

    public static void main(String[] args) {


        int n = 7388;
//        String[] bans = {"d", "e", "bb", "aa", "ae"};

        String[] bans = {"gqk", "kdn", "jxj", "jxi", "fug", "jxg", "ewq", "len", "bhc"};

        solution(n, bans);

    }

    private static void solution(int n, String[] bans) {

        HashMap<String, Integer> map = new HashMap<>();

        // 1. map 에 a-z 정리
        for (int i = 0; i < 26; i++) {
            char key = (char)('a' + i);
            map.put(String.valueOf(key), i + 1);
        }

        // 2. bans 목록 인덱스화
        int[] bannedNums = new int[bans.length];
        for (int i = 0; i < bans.length; i++) {
            bannedNums[i] = getNumber(bans[i], map);
        }

        // 2. 정렬
        Arrays.sort(bannedNums);

//        System.out.println(getAlphabet(7395));
//        System.out.println(getNumber("ab", map));

        // 3. 이분 탐색
        int left = 0;
        int right = bannedNums.length;
        while (left < right) {
            int mid = (left + right) / 2;
            if (bannedNums[mid] <= n) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        int count = countBannedLessThanOrEqualTo(n, bannedNums);

        int realN = n + count;
        while (isBanned(count, realN, bannedNums)) {
            realN++;
            count++;
            System.out.println("realN = " + realN);
        }

        System.out.println(getAlphabet(realN));
    }



    static int getNumber(String ban, HashMap<String, Integer> map) {
        String[] split = ban.split("");

        int result = 0;
        for (int i = 0; i < split.length; i++) {
            result += (int) Math.pow(26, split.length -1 -i) * map.get(split[i]);
        }
        return result;
    }

    static String getAlphabet(int num) {
        StringBuilder sb = new StringBuilder();

        while (num > 0) {
            num--; // 1을 빼야 0부터 시작하는 a~z 매칭이 가능
            int remainder = num % 26;
            char c = (char) ('a' + remainder);
            sb.append(c);
            num /= 26;
        }

        return sb.reverse().toString(); // 앞뒤 반전해서 리턴
    }

    // 이분탐색으로 bannedNums에서 n 이하 개수를 구함
    private static int countBannedLessThanOrEqualTo(int n, int[] bannedNums) {
        int left = 0;
        int right = bannedNums.length;

        while (left < right) {
            int mid = (left + right) / 2;
            if (bannedNums[mid] <= n) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    // realN이 금지어인지 확인 (이분탐색)
    private static boolean isBanned(int count, int num, int[] bannedNums) {
        int left = count;
        int right = bannedNums.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (bannedNums[mid] <= num) {
                return true;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}

 

문제 링크 (Link)

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

프로그래머스