프로그래머스 큰 수 만들기

programmers.co.kr/learn/courses/30/lessons/42883

코딩테스트 연습 - 큰 수 만들기

처음에 bfs로 접근하는 등의 삽질을 겁나게 하다가...

문제의 조건들을 다시 고려해보았다.

 

여기서 팁은

1. 숫자의 순서는 무조건 주어진 순서대로 간다는 것.(역순으로 막 뒤집어서 숫자 만들고 안그럼)

2. 순서대로 높은 숫자를 탐색하다가 그 숫자가 위치해야할 자릿수를 고려해야 함.

    public String solution(String number, int k) {
        int start = 0;							// 탐색 시작 범위
        int numberLength = number.length();     
        int limit = numberLength-k;             // 제한범위
        int remainCount = limit;                // 남은 숫자 자리 수
        StringBuilder sb = new StringBuilder();
		
        // 제한범위까지 채워지면 out
        while(sb.length() != limit) {
            int maxNum = 0;
            
            // 시작범위부터 (길이-남은 숫자 자리 수)까지 최대값 산출
            // ex. 1231234의 첫번째 탐색은 인덱스 0부터 3까지 탐색 가능함
            //     그래야 3번째가 최대값이여도 자릿수를 맞출 수 있음
            for (int i = start; i <= numberLength - remainCount; i++) {
                maxNum = Math.max(maxNum, Character.getNumericValue(number.charAt(i)));
            }
            // 남은 자리수 -
            remainCount--;
            sb.append(maxNum);
            시작 값을 최대값의 인덱스 +1부터 시작해야함
            start = number.indexOf(String.valueOf(maxNum), start)+1;
        }
        return sb.toString();
    }

 

 

 

 

참고할만한 소스

   public String solution(String number, int k) {
        char[] result = new char[number.length() - k];
        Stack<Character> stack = new Stack<>();

        for (int i=0; i<number.length(); i++) {
            char c = number.charAt(i);
            while (!stack.isEmpty() && stack.peek() < c && k-- > 0) {
                stack.pop();
            }
            stack.push(c);
        }
        for (int i=0; i<result.length; i++) {
            result[i] = stack.get(i);
        }
        return new String(result);
    }