[프로그래머스] 같은 숫자는 싫어 (JAVA)

프로그래머스

 

풀이

 

어제 유튜브 알고리즘에 걸린 영상을 보고 난 뒤에 제대로 공부하고 있는게 맞나? 하는 생각에 이전에 풀었던 문제들을 다시 풀고, 풀이를 남기고, 다른 사람들은 코드를 어떻게 짰는지 보고 배울 생각이다.

 

1. Stack을 사용한 이유

배열 내에서 연속적으로 위치한 숫자의 경우 한가지의 경우로만 생각한다고 한다.

예를들면, [1, 1, 1]의 경우 [1]로만 인식한다는 것. 이건 이후에 들어온 숫자들은 무시한다고 받아들였다.

 

Stack은 후입선출이기때문에, 이전의 숫자를 꺼내서 비교하는데 용이하다고 판단했다.

 

2. 다른 사람들은 어떻게 코드를 짰는가

for문을 돌면서, 숫자로만 비교한 경우도 있고, return 타입을 Stack<Integer>로 바꿔서 출력한 경우도 있었다.

 

3. 헷갈렸던 Stack 문법

Stack<Integer> stack = new Stack<>();
stack.add()     // stack에 값 추가
stack.push()    // stack에 값 추가

stack.pop()     // 맨 위에 있는 값(=제일 나중에 넣은) 뽑기(제거)

stack.peek()    // 맨 위에 있는 값 조회(제거X)

stack.search(1) 
// 메서드의 인자를 스택에서 검색해 해당 위치를 반환. 여러개일 경우 마지막 위치를 반환한다.
// 여기서 위치는 빠져나오는 순서를 말한다.
// stack안에 [1, 2, 3, 1] 순서로 저장되어있고 stack.search(1)을 한다면 4가 출력된다.
// stack.search(2)를 한다면 3이 출력되고, stack.search(5)를 하면 -1이 출력된다.(값이 없기 때문)

 

4. Stack의 특징

• 후입선출의 구조를 가진다. (LIFO)
• 재귀함수의 동작 흐름과 같은 흐름을 가진다.
• DFS에서 사용된다.

5. Stack의 시간복잡도 Big O

• 삽입/삭제 O(1)
• 검색 O(n)

삭제나 삽입시 맨 위의 데이터를 삽입하거나 삭제하기 때문에 시간복잡도는 늘 O(1) 의 시간복잡도를 가진다. 하지만 특정 데이터를 찾을 때는 특정 데이터를 찾을 때까지 수행을 해야하므로 O(n) 의 시간 복잡도를 가짐.

 

 

전체코드

import java.util.*;
import java.io.*;

public class Solution {
    public List<Integer> solution(int []arr) {
        Stack<Integer> stack = new Stack<>();
        for(int i=0; i<arr.length; i++){
            if(stack.size() == 0){
                stack.add(arr[i]);
            }else{
                int now = stack.peek();
                if(now != arr[i]){
                    stack.add(arr[i]);
                }
            }
        }

        ArrayList<Integer> answer = new ArrayList<>();
        while(!stack.isEmpty()){
            answer.add(stack.pop());
        }
        Collections.reverse(answer);
        return answer;
    }
}