[프로그래머스] (Java) 같은 숫자는 싫어 문제 풀이 (스택/큐)

 

1. 문제설명

배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다. 예를 들면,

• arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다.
• arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다.

배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.

제한사항

• 배열 arr의 크기 : 1,000,000 이하의 자연수
• 배열 arr의 원소의 크기 : 0보다 크거나 같고 9보다 작거나 같은 정수

 

---

2. 접근방식

 

2-1. 문제 단순화

 
주어진 배열에서 인접한 요소가 중복일 때, 중복값은 삭제한 배열을 반환받는 프로그램을 구현하는 문제이다. 명시적으로 큐/스택 문제이기 때문에 스택을 사용하면 어렵지 않게 풀 수 있다.

스택은 LIFO 구조로 한 마디로 한 쪽만 뚫려 있는 자료구조이다. 한 쪽으로만 삽입과 추출이 가능하기 때문에 나중에 들어온 요소가 먼저 빠지는 특징이 있다.
 

 
하지만 만약 이 문제가 스택인 걸 몰랐다면?
 
처음에는 '간단하게 배열을 set으로 바꾸는 메서드가 있다면 set으로 바꾸면 되지 않을까?' 생각했다. 왜냐하면 set은 중복이 허용되지 않는 자료형이기 때문이다.

하지만 생각해 보니 set은 요소들의 순서를 유지하지 않기 때문에 결국 배열에 값이 순서대로 나오지도 않을 뿐더러 문제를 자세히 읽어 보면, 같은 값이라도 연속으로 붙어 있는 것만 아니면 해당 요소는 리턴할 값에 포함을 해 줘야 한다. 사실상 인접한 값만 아니면 배열내 중복값이 허용되는 것으로 set은 답이 아니다.
 
그래서 생각한 건 ArrayList를 사용하는 방법이다. ArrayList를 선언하고, 리스트에 배열의 첫 번째 값을 넣어 주고 그 이후로는 배열의 요소가 리스트의 마지막 요소랑 다를 때만 ArrayList에 요소를 추가하는 것이다.

2-2. 해결법

Loop를 돌리면서 조건에 맞는 값(전에 등장한 적 없는 값)만 ArrayList 또는 Stack 에 추가
결과값은 int[]로 변환하여 리턴
 

---

3. 문제 풀이

3-1. ArrayList 를 활용하여 문제풀이

ArrayList answer 선언 후, 배열의 첫 번째 요소를 answer에 담아 주고, 그 이후부터는 arr[i]값이 arr[i-1]과 다른 경우에만 answer에 해당 요소를 추가하는 방법으로 코드를 짰다. 처음 시도는 실패했다. 그 이유는 return 할 때 ArrayList를 int 타입의 배열로 변환하지 않고 리턴했기 때문이다. 

 
ArrayList answer를 int 타입의 배열 result로 변환후 리턴(정답코드)

import java.util.*;

public class Solution {
    public int[] solution(int []arr) {
    	// 1. 배열에서 값을 빼와서 담아줄 ArrayList answer 선언
        ArrayList<Integer> answer = new ArrayList<>();
        
        // 2. 빈 ArrayList에 배열의 첫번째 요소 담기
        answer.add(arr[0]);
        
        // 3. 두 번째 요소부터는 loop 돌려가면서 조건에 맞는 것만 담기
        // 현재 배열 요소가 이전 요소와 같지 않을 때만 담기
        for (int i = 1; i < arr.length; i++) {
            if(arr[i]!=arr[i-1]) {
                answer.add(arr[i]);
            }
        }
        
        // ArrayList를 int[] 로 변환
        int[] result = new int[answer.size()];
        for(int i = 0; i < answer.size(); i++) {
            result[i] = answer.get(i);
        }
        return result;
    }
}

 
 

3-2. Stack(스택) 를 활용하여 문제풀이

ArrayList와 마찬가지로, Loop를 돌려 주면서 stack에 배열 요소를 push
 
✅ 배열 첫번째 요소는 무조건 스택에 들어가야 하므로 스택이 비어있다면 첫번째 요소를 push
✅ stack의 최상단의 값(peek)이 arr[i]의 값과 일치하는지 확인 -> 일치하지 않을 경우에만 stack에 해당 값 push
✅ stack의 사이즈만큼 Loop를 돌려서 값을 pop 한다. 
✅ stack에서 pop한값의 역순으로 배열에 담아야 하므로 loop의 범위는 stack size()-1부터 0까지 i--

 

import java.util.*;

public class Solution {
    public int[] solution(int []arr) {
    
    	// 1. 결과값 담아줄 int형 배열
        int[] answer;
        
        // 2. 스택 st 선언
        Stack<Integer> st = new Stack<>();
        
        // 3. 배열 길이가 0보다 크면(즉, 배열에 요소가 하나라도 있다면)
        // 스택에 배열의 첫번째 값 추가
        if (arr.length > 0) {
            st.add(arr[0]);
        }
        
        // 4. 2번째 요소부터는 스택의 최상단 요소와 같지 않을때만 스택에 추가
        for (int i = 1; i < arr.length; i++) {
            if (st.peek() != arr[i]) {
                st.push(arr[i]);
            }
        }
        
        // 5. 결과를 담을 배열 answer의 사이즈는 stack의 사이즈와 동일
        answer = new int[st.size()];
        
        // 6. 스택에서 먼저 꺼내온 요소를
        // 배열 맨 뒤부터 앞으로 순차적으로 담기(역순으로 담기)
        for (int i = st.size() - 1; i >= 0; i--) {
            answer[i] = st.pop();
        }
        
        return answer;
    }
}

 

---

4. 같은 유형 문제(스택/큐)

 

[프로그래머스] (Java) 주식가격 (스택/큐)

[프로그래머스] (Java) 다리를 지나는 트럭 (스택/큐)

[프로그래머스] (Java) 프로세스 문제풀이 (스택/큐)

[프로그래머스] (Java) 올바른 괄호 문제풀이 (스택/큐)

[프로그래머스] (Java) 기능개발 (스택/큐)