[ Programmers ] 배열 만들기 4 ( java ) 35 / 124

[ Programmers ] 배열 만들기 4 ( java ) 35 / 124

프로그래머스

 

 

 

 

📚 Table of Contents

 

 

 

 

문제

문제 설명

정수 배열 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 함수를 완성해 주세요.

 

 

제한사항

• 1 ≤ arr의 길이 ≤ 100,000
  • 1 ≤ arr의 원소 ≤ 100,000

 

 

입출력 예

 

 

 

 

문제 풀이

코드 설명

코드의 목적:

• 이 코드는 주어진 배열 arr에서 비내림차순으로 정렬된 부분 수열의 최대 길이를 계산하고, 그 부분 수열의 값들을 배열로 반환하는 알고리즘을 구현합니다.

 

코드의 주요 구조:

1. Import: Stack 클래스를 import 합니다.
2. 클래스 정의: Solution 클래스를 정의합니다.
3. 메서드 정의: solution 메서드를 정의합니다.

 

코드의 주요 알고리즘:

1. 스택 생성: st 변수를 Stack으로 생성하여 부분 수열을 저장할 스택을 준비합니다.
2. 배열 순회:
   • arr 배열의 각 요소를 순회하면서 다음을 수행합니다.
3. 스택이 비어있으면:
   • 현재 요소를 스택에 추가합니다.
4. 스택의 맨 위 요소보다 현재 요소가 크면:
   • 현재 요소를 스택에 추가합니다.
5. 스택의 맨 위 요소보다 현재 요소가 작거나 같으면:
   • 스택의 맨 위 요소를 제거합니다.
   • 배열의 인덱스를 하나 감소시켜 다음 반복에서 현재 요소를 다시 비교하도록 합니다.
6. 결과 반환:
   • 스택에 남아있는 요소들을 배열로 변환하여 반환합니다.

 

코드의 핵심:

• 스택을 사용하여 비내림차순 부분 수열을 관리합니다.
• 스택의 맨 위 요소와 비교하여 현재 요소가 더 크면 스택에 추가하고, 그렇지 않으면 스택에서 제거합니다.
• 스택의 특성을 활용하여 비내림차순 부분 수열을 효율적으로 구성합니다.

 

 

 

풀이

import java.util.Stack;

class Solution {
    public int[] solution(int[] arr) {
        // 부분 수열 저장할 스택
        Stack<Integer> st = new Stack<>();

        // 배열 순회
        for (int i = 0; i < arr.length; i++) {
            if (st.empty()) {  // 스택이 비어있으면 추가
                st.push(arr[i]);
            } else if (st.peek() < arr[i]) {  // 스택 맨 위 요소보다 크면 추가
                st.push(arr[i]);
            } else if (st.peek() >= arr[i]) {  // 스택 맨 위 요소보다 작거나 같으면 제거
                st.pop();
                i--;  // 현재 요소를 다음 반복에서 다시 비교하도록 인덱스 감소
            }
        }

        // 스택에 남아있는 부분 수열을 배열로 변환하여 반환
        return st.stream().mapToInt(Integer::intValue).toArray();
    }
}