https://school.programmers.co.kr/learn/courses/30/lessons/181859
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 설명
0과 1로만 이루어진 정수 배열 arr가 주어집니다. arr를 이용해 새로운 배열 stk을 만드려고 합니다.
i의 초기값을 0으로 설정하고 i가 arr의 길이보다 작으면 다음을 반복합니다.
- 만약 stk이 빈 배열이라면 arr[i]를 stk에 추가하고 i에 1을 더합니다.
- stk에 원소가 있고, stk의 마지막 원소가 arr[i]와 같으면 stk의 마지막 원소를 stk에서 제거하고 i에 1을 더합니다.
- stk에 원소가 있는데 stk의 마지막 원소가 arr[i]와 다르면 stk의 맨 마지막에 arr[i]를 추가하고 i에 1을 더합니다.
위 작업을 마친 후 만들어진 stk을 return 하는 solution 함수를 완성해 주세요.
단, 만약 빈 배열을 return 해야한다면 [-1]을 return 합니다.
제한사항
- 1 ≤ arr의 길이 ≤ 1,000,000
- arr의 원소는 0 또는 1 입니다.
입출력 예
arrresult
| [0, 1, 1, 1, 0] | [0, 1, 0] |
| [0, 1, 0, 1, 0] | [0, 1, 0, 1, 0] |
| [0, 1, 1, 0] | [-1] |
입출력 예 설명
입출력 예 #1
- 각 작업을 마친 후에 배열의 변화를 나타내면 다음 표와 같습니다.
idxarr[idx]stk
| 0 | 0 | [] |
| 1 | 1 | [0] |
| 2 | 1 | [0, 1] |
| 3 | 1 | [0] |
| 4 | 0 | [0, 1] |
| 5 | - | [0, 1, 0] |
- 따라서 [0, 1, 0]을 return 합니다.
입출력 예 #2
- 각 작업을 마친 후에 배열의 변화를 나타내면 다음 표와 같습니다.
idxarr[idx]stk
| 0 | 0 | [] |
| 1 | 1 | [0] |
| 2 | 0 | [0, 1] |
| 3 | 1 | [0, 1, 0] |
| 4 | 0 | [0, 1, 0, 1] |
| 5 | - | [0, 1, 0, 1, 0] |
- 따라서 [0, 1, 0, 1, 0]을 return 합니다.
입출력 예 #3
- 각 작업을 마친 후에 배열의 변화를 나타내면 다음 표와 같습니다.
idxarr[idx]stk
| 0 | 0 | [] |
| 1 | 1 | [0] |
| 2 | 1 | [0, 1] |
| 3 | 0 | [0] |
| 4 | - | [] |
- 마지막에 빈 배열이 되었으므로 [-1]을 return 합니다.
이 코드는 주어진 배열 `arr`에서 연속된 중복된 숫자들을 제거하는 문제를 해결하는 Java 프로그램입니다.
코드를 이해하기 위해 주요 부분들을 하나씩 살펴보겠습니다.
1. `solution` 메서드:
public int[] solution(int[] arr) {
int[] answer = cal(arr);
return answer;
}
`solution` 메서드는 주어진 배열 `arr`을 파라미터로 받아 `cal` 메서드를 호출하고,
`cal` 메서드의 반환값인 배열을 `answer`에 저장하여 반환합니다.
2. `cal` 메서드:
private static int[] cal(int[] arr) {
Stack<Integer> stack = new Stack<>();
int index = 0;
while (index < arr.length) {
if (stack.isEmpty()) {
stack.push(arr[index]);
index++;
continue;
}
if (stack.peek() == arr[index]) {
stack.pop();
index++;
} else {
stack.push(arr[index]);
index++;
}
}
if (stack.size() == 0) {
return new int[]{-1};
}
int[] result = new int[stack.size()];
for (int i = stack.size() - 1; i >= 0; i--) {
result[i] = stack.pop();
}
return result;
}
`cal` 메서드는 중복된 숫자를 제거하는 로직을 구현합니다. 이를 위해 `Stack` 자료구조를 사용합니다.
- `Stack<Integer> stack = new Stack<>();`: 정수형 값을 저장하는 스택을 선언합니다.
- `int index = 0;`: 배열을 탐색하기 위한 인덱스를 초기화합니다.
다음으로, `while` 루프를 통해 배열을 순회하면서 중복된 숫자를 스택에 저장하거나 제거합니다.
배열을 순회하면서 현재 인덱스(`index`)를 이용하여 배열의 끝까지 탐색합니다.
1. `if (stack.isEmpty())`: 스택이 비어있다면, 현재 숫자를 스택에 넣고 다음 인덱스로 이동합니다.
2. `if (stack.peek() == arr[index])`: 스택의 top과 현재 숫자가 같다면, 스택에서 중복된 숫자를 제거하고 다음 인덱스로 이동합니다.
3. `else`: 스택의 top과 현재 숫자가 다르다면, 현재 숫자를 스택에 넣고 다음 인덱스로 이동합니다.
스택에 남아있는 숫자들은 중복이 제거된 상태입니다.
따라서 `stack`의 사이즈를 확인하여 중복이 없으면 `-1`을 반환하고, 중복이 있으면
`stack`에 있는 숫자들을 배열에 옮겨 저장하여 반환합니다.
위의 코드는 중복된 숫자를 제거하는 로직을 스택을 이용해 구현한 것이므로,
예를 들어 `int[] arr = {1, 2, 2, 3, 3, 3, 4, 5, 5}`와 같이 중복된 숫자가 있는 배열을 주면
`int[] result = {1, 4}`와 같이 중복이 제거된 결과를 반환할 것입니다.
중복이 없는 경우에는 `int[] result = {-1}`을 반환합니다.
