[Algorithm] 프로그래머스 Lv2 큰 수 만들기

안녕하세요 rosepurple입니다. :)

오늘 푼 알고리즘 문제 풀이를 작성해보도록 하겠습니다!

문제

오늘은 아래 문제를 풀어봤습니다. (약 45분 소요)

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

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

풀이

처음에는 스택을 사용해서 풀어보려고 했습니다.

그런데 자바 스택은 peek 기능이 마지막 하나만 볼 수 있어서 로직이 꼬이는 것을 느꼈습니다. (인덱스 접근이 어렵기 때문에..)

그래서 ArrayList를 활용해서 풀었습니다!

 

String[] strings = number.split("");
int[] numberArray = new int[number.length()];
for (int i = 0; i < strings.length; i++) {
    numberArray[i] = Integer.parseInt(strings[i]);
}

우선 인자로 입력받는 number를 String으로 쪼개서 다시 int 배열에 저장하는 과정입니다.

 

ArrayList<Integer> answerList = new ArrayList<>();
answerList.add(numberArray[0]);

그다음은 사용할 ArrayList를 생성해주고 숫자 배열의 맨 첫 번째 숫자를 추가합니다.

 

for (int i = 1; i < numberArray.length; i++)

그다음부터는 for문을 순회할 것입니다.

이미 맨 처음 숫자를 ArrayList에 저장했으므로 인덱스 1부터 순회합니다.

 

if (k == 0) {
    for (int j = i; j < numberArray.length; j++) {
        answerList.add(numberArray[j]);
    }
    break;
}

만약 k가 0이라면 제거할 숫자가 없으므로 숫자 배열의 나머지를 모두 ArrayList에 추가하고 for문을 빠져나옵니다.

 

answerList.add(numberArray[i]);

k가 0이 아니라면 i번째 인덱스 숫자를 ArrayList에 추가해줍니다.

 

그 후의 과정이 이 문제의 핵심입니다.

if (answerList.get(answerList.size() - 1) > answerList.get(answerList.size() - 2)) {
    while (answerList.size() != 1
            && answerList.get(answerList.size() - 1) > answerList.get(answerList.size() - 2)
            && k > 0) {
        answerList.remove(answerList.get(answerList.size() - 2));
        k--;
    }
}

제일 마지막 숫자와 마지막 숫자의 앞 숫자를 비교해 봤을 때, 마지막 숫자가 크다면 실행되는 구문입니다.

k가 0이 아니고 ArrayList가 1이 아니며 마지막 숫자가 그 앞 숫자보다 클 때 ArrayList의 끝에서 두 번째 숫자를 지우고 k를 하나 감소시킵니다.

 

위의 과정을 그림으로 그려보면 아래와 같습니다. (number = "1924", k = 2)

 

 

String answer = "";
int len = number.length() - k;

for (int i = 0; i < len; i++) {
    answer += answerList.get(i);
}

마지막으로 정답 길이만큼 ArrayList의 처음부터 answer을 더해주고 return 해주면 됩니다.

📎  for문을 순회하면서 k값을 감소시켜줬기 때문에 len을 초기화시켜주는 것은 for문 이전에 해주어야 합니다.

전체 코드

class Solution {
    public String solution(String number, int k) {
        String[] strings = number.split("");
        int[] numberArray = new int[number.length()];
        for (int i = 0; i < strings.length; i++) {
            numberArray[i] = Integer.parseInt(strings[i]);
        }

        ArrayList<Integer> answerList = new ArrayList<>();
        answerList.add(numberArray[0]);

        String answer = "";
        int len = number.length() - k;

        for (int i = 1; i < numberArray.length; i++) {
            if (k == 0) {
                for (int j = i; j < numberArray.length; j++) {
                    answerList.add(numberArray[j]);
                }
                break;
            }

            answerList.add(numberArray[i]);

            if (answerList.get(answerList.size() - 1) > answerList.get(answerList.size() - 2)) {
                while (answerList.size() != 1
                        && answerList.get(answerList.size() - 1) > answerList.get(answerList.size() - 2)
                        && k > 0) {
                    answerList.remove(answerList.get(answerList.size() - 2));
                    k--;
                }
            }
        }

        for (int i = 0; i < len; i++) {
            answer += answerList.get(i);
        }

        return answer;
    }
}

마무리

저는 큰 수, 숫자 빼기 더하기 이런 관련 문제는 Stack 개념을 사용해서 푸는 것에 익숙해져있습니다.

그래서 이번 문제도 크게 어려움 없이 풀었습니다.

 

처음에는 테스트 케이스 12번만 실패해서 어리둥절했지만, 마지막에 정답 길이만큼 리스트의 처음부터 정답을 저장하는 것으로 코드를 수정하고 나니 정답을 맞히게 되었습니다.

 

이번 포스팅도 읽어주셔서 감사합니다. :)