[level1, Stack/Queue] 같은 숫자는 싫어

1. 문제

 

 

 

 

 

 

 

2. 문제 해결 논리

1. 문제 이해
   • 주어진 것
     • int[] arr    //0보다 크거나 같고 9보다 작거나 같은 정수를 원소로 하는 배열
   • 요구되는 것
     • int[] answer     //중복된 원소만 제거된 배열
2. 데이터 구조 결정
   • 방법 1. List, ArrayList 구조 사용
     • Collection 인터페이스를 구현하고 있는 List 인터페이스의 사용
       • List 인터페이스의 주요 메서드
         
         • add(E element) -> 반환 값 boolean
         • get(int index) -> 반환 값 E element
         • isEmpty() -> 반환 값 boolean
         • size() -> 반환 값 int
         • sort(Comparator<? super E> c) -> 반환 값 default void
   • 방법 2. Stack 구조 사용
     • List 인터페이스를 구현하는 Vector 클래스, 그리고 이를 확장하는 Stack 클래스의 사용
     • Stack은 (List 인터페이스를 구현 및 확장하므로) List에서 정의된 메서드도 사용 가능
       • Stack 클래스의 주요 메서드
         • push(E item) -> 반환 값 E
         • pop() -> 반환 값 E
         • peek() -> 반환 값 E
   • 방법 3. Queue, LinkedList 구조 사용 
     • (Collection 인터페이스를 확장하는) Queue 인터페이스, 그리고 이를 구현하는 LinkedList 클래스 사용
     • LinkedList는 (List와 Queue 인터페이스를 구현하므로) List, Queue에 정의된 메서드도 사용 가능 
       • Queue 인터페이스의 주요 메서드
         • add(E e) -> 반환 값 boolean, Queue 구조의 끝에 추가하는 메서드, 큐에 공간이 없어 추가할 수 없으면 IllegalStateException 발생
         • offer(E e) -> 반환 값 boolean, Queue 구조의 끝에 추가하는 메서드, 큐에 공간이 없어 추가할 수 없으면 false를 반환.
         • poll() -> 반환 값 E, Queue 구조의 제일 앞의 요소를 반환 및 제거
         • peek() -> 반환 값 E, Queue 구조의 제일 앞의 요소를 확인만하는 메서드
       • LinkedList 클래스의 주요 메서드
         
         • List 류의 메서드 특징 : 비어있는 경우, 예외 발생
           • get(int index) -> 반환 값 E, 리스트의 특정 위치의 요소를 반환, 인덱스가 범위를 벗어나면 IndexOutOfBoundsException 예외 발생
           • getFirst() -> 반환 값 E, 리스트의 제일 앞의 요소를 반환, 리스트가 비어있다면 NoSuchElementException 예외 발생
           • getLast() -> 반환 값 E, 리스트의 제일 뒤의 요소를 반환, 리스트가 비어있다면 NoSuchElementException 예외 발생 
           • push(E e) -> 반환 값 void, 리스트의 제일 앞에 요소 추가
           • pop() -> 반환 값 E, 리스트의 제일 앞의 요소를 반환 및 제거, 리스트가 비어있다면 NoSuchElementException 예외 발생, remove(), removeFirst()와 동일한 기능 수행
         • Queue 류의 메서드 특징 : 비어있는 경우, null 반환
           • offer(E e) -> 반환 값 boolean, 리스트의 제일 뒤에 요소를 추가, offerLast와 동일
           • offerFirst(E e) -> 반환 값 boolean, 리스트의 제일 앞에 요소를 추가
           • offerLast(E e) -> 반환 값 boolean, 리스트의 제일 뒤에 요소를 추가
           • peek() -> 반환 값 E, 리스트의 제일 앞 요소를 반환, 리스트가 비어있다면 null 반환, peekFirst와 동일
           • peekFirst() -> 반환 값 E, 리스트의 제일 앞 요소를 반환, 리스트가 비어있다면 null 반환
           • peekLast() -> 반환 값 E, 리스트의 제일 뒤 요소를 반환, 리스트가 비어있다면 null반환
           • poll() -> 반환 값 E, 리스트의 제일 앞 요소를 반환, 리스트가 비어있다면 null 반환, pollFirst와 동일
           • pollFirst() -> 반환 값 E, 리스트의 제일 앞 요소를 반환 및 제거, 리스트가 비어있다면 null반환
           • pollLast() -> 반환 값 E, 리스트의 제일 뒤 요소를 반환 및 제거, 리스트가 비어있다면 null반환
           • 예외
             • remove() ->  반환 값 E, 리스트의 제일 앞의 요소를 반환 및 제거, 리스트가 비어있다면  NoSuchElementException 예외 발생
             • removeFirst() -> 반환 값 E, remove() 메서드와 동일한 기능, 동일한 예외 발생
             • removeLast() -> 반환 값 E, 리스트의 제일 뒤의 요소를 반환 및 제거, 위와 동일한 예외 발생
         • indexOf(Object o) -> 반환 값 int, 해당 객체의 인덱스 반환, 없다면 -1 반환
         • size() -> 반환 값 int, 리스트의 크기 반환
3. 알고리즘 설계
   1. 선택한 구조 생성
   2. 주어진 배열에서 조건을 추가해 선택한 구조로 변환
   3. 선택한 구조에서 다시 배열로 변환

 

 

 

 

 

 

3. 코드 구현

    3-1. List, ArrayList 구조 사용

import java.util.*;
public class Solution {
    public int[] solution(int []arr) {
        //List와 ArrayList 구조 사용
        List<Integer> list = new ArrayList<>();
        
        //list에 arr의 첫 번째 값 대입
        list.add(arr[0]);
        for (int i=1; i<arr.length;i++) {
            //arr의 원소가 중복되지 않는 경우, list에 원소 대입
            if (arr[i-1] != arr[i]) {
                list.add(arr[i]);
            }
        }
        
        int[] answer = new int[list.size()];
        
        //list -> int[]로의 변환
        for (int i = 0; i < list.size(); i++) {
            answer[i] = list.get(i);
        }

        return answer;
    }
}

 

 

 

 

 

    3-2. Stack 구조 사용

import java.util.*;

public class Solution {
    public int[] solution(int []arr) {
        //Stack 구조 사용
        Stack<Integer> stack = new Stack<>();

        //arr 배열을 순회하며 stack에 push
        for (int num : arr) {
            //stack이 비어있거나, stack의 마지막 원소가 arr의 원소와 같지 않다면 push
            if (stack.isEmpty() || stack.peek() != num) {
                stack.push(num);
            }
        }

        int[] answer = new int[stack.size()];

        //stack의 pop은 마지막 원소를 꺼내므로
        //answer 배열의 마지막 인덱스부터 대입
        for (int i = answer.length; i > 0; i--) {
            answer[i - 1] = stack.pop();
        }
        
        
        //Stack은 List 인터페이스를 구현하므로 get메서드를 써서 다음의 풀이도 가능
        //for (int i = 0; i < answer.length; i++) {
        //    answer[i] = stack.get(i);
        //}

        return answer;
    }
}

 

 

 

 

 

    3-3. Queue, LinkedList 구조 사용

import java.util.*;

public class Solution {
    public int[] solution(int []arr) {
        //Queue와 LinkedList 구조 사용
        Queue<Integer> queue = new LinkedList<>();
        
        //arr배열 순회하며 대입
        for (int num : arr) {
            //queue가 비어있거나 queue의 마지막 원소 값이 num과 같지 않은 경우 대입
            if (queue.isEmpty() || ((LinkedList<Integer>)queue).peekLast() != num) {
                queue.offer(num);
            }
        }

        int[] answer = new int[queue.size()];
        
        
        //다음과 같이 인덱스를 부여하여 while문 사용 가능
        //int index = 0;
        //while (!queue.isEmpty()) {
        //    answer[index++] = queue.poll();
        //}
        
        
        //다음과 같이 for문 사용 가능
        //그러나 반복 조건에서 queue.size()를 쓰면 안된다
        //queue.poll()은 Queue 구조의 사이즈를 변경시키기 때문
        //이는 Stack 구조의 pop()에서도 마찬가지
        for (int i = 0; i < answer.length; i++) {
            answer[i] = queue.poll();
        }

        return answer;
    }
}

 

 

 

 

 

 

 

 

* Reference

https://school.programmers.co.kr/learn/courses/30/lessons/12906

프로그래머스