[Java] 프로그래머스 : 큰 수 만들기(StringBuilder 사용)

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

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

 

StringBuilder

 : 문자열을 더해주는 클래스

 · "문자열" + "문자열"도 가능하지만 메모리 할당, 해제를 발생시키며 성능적으로 좋지 않음

 · String과 문자열을 더할 때 새로운 객체를 생성하는 것이 아니라 기존의 데이터에 더하는 방식을 사용하기 때문에

    속도도 빠르며 상대적으로 부하가 적다

 

StringBuilder sb = new StringBuilder();

//StringBuilder에선 append속성을 통해 문자열을 더해준다. 
sb.append("안녕").append("하세요");

ArrayList<String> list = new ArrayList<>();
for(int i = 0; i < list.size(); i++){
    sb.append(list.get(i));
}

처럼 쓸 수 있음!

 

 

문제

 

 

* 첫번째 for문의 범위

 - 가장 큰 숫자를 정하기위해 돌리며, 자릿수가 K이므로 K보다 적게 남는 자리의 숫자를 선택할 수 없다.

(숫자는 놓여있는 순서대로 선택되어야한다. 뒤에 배치된 숫자를 선택 후 앞으로 갈 수 없음)

 ex_ 12345678일때 k가 3이면 적어도 첫번째 숫자는 6이 선택되어야 3자리 선택이 가능

(7or8이 선택될 경우 숫자가 3개 이상이 남아 있지 않기에 선택불가)

class Solution {
    public String solution(String number, int k) {
        int index = 0;
        char max;
        StringBuilder answer = new StringBuilder();

        for(int i = 0; i < number.length() - k; i++) {
            max = '0';
            for(int j = index; j <= k + i; j++) {
            	    // 조건 index 범위 내에서 가장 큰 값을 찾아 max에 대입
                    // index = j + 1 : 가장 큰 값의 인덱스 다음부터 반복하기 위해
                    if(max < number.charAt(j)) {
                        max = number.charAt(j); 
                        index = j + 1;
                    }
            }			
            answer.append(max);
        }
            return answer.toString();
    }
}

 

 

 

<Stack>을 이용한 코드 

 - https://hanyeop.tistory.com/394 블로그 참고

import java.util.*;

class Solution {
    public String solution(String number, int k) {
        String answer = "";
        int count = 0;
        Stack<Integer> s = new Stack<Integer>();
        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < number.length(); i++){            
            int value = (number.charAt(i) - '0');

            while(true){

                if(s.size() == 0){
                    s.add(value);
                    break;
                }

                if(count >= k || s.peek() >= value){
                    s.add(value);
                    break;
                }

                if(s.peek() < value){
                    s.pop();
                    count++;
                }
            }
        }

        while(count != k){
            s.pop();
            count++;
        }

        while(!s.isEmpty()){
            sb.append(s.pop());
        }

        answer = sb.reverse().toString();
        return answer;
    }
}