[Java] 배열 만들기 4

문제 설명

정수 배열 arr가 주어집니다. arr를 이용해 새로운 배열 stk를 만드려고 합니다.

변수 i를 만들어 초기값을 0으로 설정한 후 i가 arr의 길이보다 작으면 다음 작업을 반복합니다.

• 만약 stk가 빈 배열이라면 arr[i]를 stk에 추가하고 i에 1을 더합니다.
• stk에 원소가 있고, stk의 마지막 원소가 arr[i]보다 작으면 arr[i]를 stk의 뒤에 추가하고 i에 1을 더합니다.
• stk에 원소가 있는데 stk의 마지막 원소가 arr[i]보다 크거나 같으면 stk의 마지막 원소를 stk에서 제거합니다.

위 작업을 마친 후 만들어진 stk를 return 하는 solution 함수를 완성해 주세요.

Pseudo Code

 

1. 초기화
   • stk → 결과 배열
   • idx → arr 순회 인덱스
2. 반복 조건
   • idx < arr.length 동안 반복
3. 조건 처리
   • stk가 비어 있으면 arr[idx] 추가 → idx증가
   • 마지막 원소 < arr[idx] → 추가 → idx증가
   • 마지막 원소 ≥ arr[idx] → 마지막 원소 제거 → idx 증가 X
4. 최종 반환
   • 만들어진 stk 반환

 

내 코드

class Solution {
    public int[] solution(int[] arr) {
        ArrayList<Integer> stk = new ArrayList<>();
        int idx = 0;
        while(idx < arr.length) {
            int len = stk.size();
            if(len == 0) {
                stk.add(arr[idx]);
                idx ++;
            } else {
                if(stk.get(len-1) < arr[idx]) {
                    stk.add(arr[idx]);
                    idx ++;
                } else {
                    stk.remove(len-1);
                }
            }
        }
        return stk.stream().mapToInt(i->i).toArray();
    }
}

내 코드를 보면 stk의 마지막 원소만 접근하면서 ArrayList로 스택을 흉내낸 코드처럼 보인다. 물론 정답이었지만 제출하자마자 deque로 더 가독성있는 코드 작성이 가능했다는걸 알아서 개선해보았다.

개선된 코드

class Solution {
    public int[] solution(int[] arr) {
        Deque<Integer> stk = new ArrayDeque<>();
        int idx = 0;
        while (idx < arr.length) {
            if (stk.isEmpty() || stk.peekLast() < arr[idx]) {
                stk.addLast(arr[idx++]);
            } else {
                stk.removeLast();
            }
        }
        return stk.stream().mapToInt(i -> i).toArray();
    }
}

 

• peekLast() → 마지막 원소 확인
• addLast() → 마지막에 추가 (push)
• removeLast() → 마지막 제거 (pop)