[프로그래머스 스택/큐] 같은 숫자는 싫어

스택과 큐를 이용하는 문제

분명 스택/큐 열심히 배웠었는데 또 막상 문제로 활용하려니 메소드들이 기억이 안났다...(T.T)

 

 

---

간단하게 개념 정리를 해야겠다.

 

💥 1) 스택 (Stack)

: LIFO(last in first out) 선입후출의 방식으로 데이터 저장& 접근한다.

>> 컵 모양을 생각하면 쉽다!!  (마지막에 넣은 것을 첫 번째로 빼는 컵 !!)

• push() : 인덱스상 맨 끝에 항목 추가 
• pop() : 인덱스상 맨 끝의 항목을 구조에서 제거하고 반환
• peek() : 인덱스상 맨 끝의 데이터 반환 

💥 2) 큐 (Queue)

: FIFO(first in first out) 선입선출의 방식으로 데이터 저장&접근한다.

>> 빨대 모양을 생각하면 쉽다!! (넣은 순서대로 밀려 나오는 빨대)

인덱스 접근이 불가능.

• offer() : 구조의 맨 끝에 항목 추가
• poll() : 맨 앞 항목을 구조에서 제거하고 반환
• peek() : 맨 앞 데이터 반환

💥 3) 데크 (Deque)

: 양방향 접근이 가능한 Queue의 확장 인터페이스. FIFO, LIFO 둘 다 가능하며 상황에 따라 원하는 입출방식을 정할 수 있다. 인덱스 접근이 불가능.

• addFirst() / addLast() : 맨 앞/ 맨 끝에 항목 추가
• removeFirst() / removeLast() : 맨 앞/ 맨 끝에 항목 제거반환
• pollFirst() / pollLast() : 맨 앞/ 맨 끝 항목을 구조에서 제거하고 반환
• peekFirst() / peekLast() : 맨 앞/ 맨 끝 반환만

 

---

이 개념들을 활용하여 문제를 풀어보자!

 

1) 스택을 생성하고

2) for문을 활용하여 배열의 값을 모두 확인

3) 스택이 채워진 상태여야 비교할 수 있으므로 > stack.empty() 메소드 활용

4) 인덱스 맨 끝의 항목을 반환하여 배열값과 비교해야 하므로 > stack.peek() 메소드 활용

5) 3번과 4번을 확인한 후 조건을 만족하였을 때 그 항목은 겹치는 항목이므로 빼야함 > stack.pop() 메소드 활용

6) for문을 돌며 무조건 그 배열값을 스택에 넣는다. > stack.push() 메소드 활용

import java.util.*;

public class Solution {
    public Stack solution(int []arr) {
    	// 스택 생성
        Stack<Integer> stack = new Stack<>();

	// for문 돌며 배열의 각 인덱스 확인
        for (int i=0; i<arr.length; i++) {
        // 스택이 비어있지 않으며, 인덱스 맨 끝의 항목과 배열의 값과 비교하여 같으면 그 항목을 제거.
            if (!stack.empty() && stack.peek()==arr[i]) {
                stack.pop();
            }
            // 기본적으로 스택에 배열값을 스택에 넣는다.
            stack.push(arr[i]);
        }
        return stack;
    }
}

 

** 생각방식을 또 바꿔보면 이미 그 항목이 스택에 있으면 아예 추가를 안하는 방법도 있다!

 

import java.util.*;

public class Solution {
    public Stack solution(int []arr) {
    	//1) 스택 생성
        Stack<Integer> stack = new Stack<>();

	// 2) for문 돌며 배열의 각 인덱스 확인
        for (int i=0; i<arr.length; i++) {
       	// 스택이 비어있지 않으며, 인덱스 맨 끝의 항목과 배열의 값과 비교하여 같으면 스킵.
            if (!stack.empty() && stack.peek()==arr[i]) {
                continue;
            } else { //그렇지 않으면 스택에 그 배열값을 추가하기.
                stack.push(arr[i]);
            }
        }
        return stack;
    }
}

 

+ Deque를 활용해서도 만들 수 있을 것 같다.

스택/큐 문제를 풀려면 스택/큐의 메소드 여러가지를 알아두는 것이 필수인듯 하다!