알고리즘 공부(1) - 자료구조(스택,큐)

요즘 매일 아침마다 알고리즘을 하나씩 풀면서 느낀점은 자료구조를 잘 쓸수있어야 한다는점이다.

자바에서 자료구조를 어떻게 쓰는지 하나씩보자. 이건 내가 공부하면서 그냥 나혼자 볼생각으로 적어본다.

자바에서 사용하는 자료구조에는 어떤게 있을까?

자바에는 자료구조를 표현하는 인터페이스인 컬렉션(Collection)이 있다.

컬렉션을 구현한 자료구조는 List, Set, Queue, Stack, Map이 있다.

https://kimchanjung.github.io/etc/2020/01/15/java-collection/

JAVA - 자료구조, Collection 별 특징 정리

여기서 알고리즘을 풀며 자주 사용하는것들만 정리해보려 한다.

ㅇ 스택(Stack)

ㅁ 스택의 특징

- 후입선출(LIFO)의 구조 : 프링글스의 통이라고 생각하자. 가장 먼저 들어간 감자칩은 가장 마지막에 나오게 된다.

- 단방향 입출력 구조 : 입구와 출구는 같다.

- 데이터는 하나씩만 넣고 뺄 수 있다.

- 재귀함수의 동작 흐름과 구조가 같다.

- Stack, ArrayDeque..

 

ㅁ 스택의 선언

//Stack<T> 스택이름 = new Stack();
Stack<Integer> sInt = new Stack();
Stack<String> sStr = new Stack();
Stack<Boolean> sBool = new Stack();

ㅁ 스택에 값 추가 및 제거

Stack<Integer> s = new Stack();
//값 삽입
s.push(1);
s.push(2);
s.push(3);
//[1,2,3]
//값 제거
s.pop();	//마지막에 들어간 3 제거.
//[1,2]
//값 삽입
s.add(1);
s.add(2);
s.add(3);
[1,2,1,2,3]
//빠져나오는순서반환
System.out.println(s.search(3)); 	// 첫번째이므로 1을 출력
System.out.println(s.search(2));	// 2가 여러개니 가장 먼저나오는2는 두번째이므로 2출력
System.out.println(s.search(4));	// 찾는 데이터는 없으므로 -1 출력
//맨위의값 반환
System.out.println(s.peek());	// 반환만 하므로 데이터는 변화없음
//비어있는지의 여부
System.out.println(s.isEmpty());	// false 출력
//데이터 모두 제거
s.clear();
//비어있는지의 여부 = true
System.out.println(s.isEmpty());	// true 출력 clear 했기 때문.

push 와 add는 둘다 같은 추가 메서드다. 하지만 push메서드는 Stack, LinkedList에서만 사용된다. add 메서드는 다른 자료구조에서도 사용된다. 둘의 리턴값은 다르다. push의 리턴값은 <E>, add의 리턴값은 boolean이다.

push, pop, add, search, peek, isEmpty, clear 가 있다.

알고리즘 문제를 풀다보면 가장 많이 쓰는게 push, pop, peek, isEmpty가 가장 많이 사용되니 꼭 알아두자.

 

ㅁ 스택의 사용

스택을 사용할땐, 값을 조건문으로 필터링해서 push 해놓고, isEmpty가 true가 나올때까지 pop하는 경우가 많다.

Stack<Integer> sInt = new Stack();
        
        sInt.add(10);		// 10
        sInt.push(20);		// 20 10
        sInt.push(30);		// 30 20 10
        
        while(!sInt.isEmpty()){
            System.out.println(sInt.pop());
        }

while문을 보면 조건이 !sInt.empty()다. !sInt.empty가 참인동안 

System.out.println(sInt.pop()); 를 수행한다는건데, 반복문에서 첫번째 !sInt.isEmpty()는 [30,20,10] 이 있기때문에 false이지만 !이 붙었기때문에 true. 그렇게 pop을 해서 모두 pop 되면 !sInt.isEmpty()는 false가되면서 반복문이 종료된다. 자주쓰이기때문에 무조건 눈에 익혀두자.

 

ㅁ empty vs isEmpty

스택에대해 찾아보다가 블로그마다 empty, isEmpty를 혼용해서 사용하길래 찾아보니 잘 정리되어있는 블로그 포스팅도 발견했다.

결론은 동일하지만 isEmpty를 권장한다는 것이다.

https://velog.io/@baekgom/Java-Stack-%EC%97%90%EC%84%9C-empty-vs-isEmpty

Java Stack 에서 empty() vs isEmpty()

ㅁ 스택을 사용하는 알고리즘 문제

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

프로그래머스

이 문제는 스택을 사용하는 문제다. 위의 메서드 설명을 잘 숙지하면 쉽게 풀수있을것이다.

public class Solution {
    public int[] solution(int []arr) {
    	//빈 스택을 만들어준다.
        Stack<Integer> stack = new Stack<>();
        //중복되지 않는 조건을 걸고 빈 스택에 arr에서 하나씩 빼서 넣어준다.
        for (int num : arr) {
            if (stack.isEmpty() || stack.peek() != num) {
                stack.push(num);
            }
        }
        // 정답으로 반환할 빈 배열을 만들어주고
        int[] answer = new int[stack.size()];
        // 스택은 LIFO 이므로 반대순서대로 넣어준다.
        for (int i = stack.size() - 1; i >= 0; i--) {
            answer[i] = stack.pop();
        }
        return answer;
    }
}

 

ㅇ 큐(Queue)

ㅁ 큐의 특징

- 선입선출(FIFO)의 구조 : 가장 먼저 들어온 데이터가 가장 먼저 나간다.

- 넓이 우선 탐색에서 사용됨

- 맨첫번째 데이터는 front로 삭제연산만 수행하고, 맨뒤 데이터는 rear로 삽입연산만 수행함

- Queue, ArrayDeque...

 

ㅁ 큐의 선언

import java.util.LinkedList; //import
import java.util.Queue; //import
Queue<Integer> q = new LinkedList<>();
Queue<String> q = new LinkedList<>();

자바에서 큐는 링크드리스트를 이용한다. 그래서 두개 임포트 해주고 사용한다

 

ㅁ 큐의 메서드

Queue<Integer> q = new LinkedList<>();
//데이터 추가
q.add(1);		//삽입 실패시 예외발생, 성공시 true 반환
q.offer(2);		//삽입 실패시 false, 성공시 true 반환
q.offer(3);
//[1,2,3]
//데이터 제거
q.poll();       // q에 첫번째 데이터 반환하고 제거, 비어있다면 null 반환 [2,3]
q.remove();     // q에 첫번째 데이터 제거[3]
q.clear();      // q에 모든 데이터 제거[]
q.add(1);		// [1]
q.add(2);		// [1 , 2]
q.peek();		// front 반환. 첫번째값 1 반환 만약 빈큐면 null 반환
q.element();	// front 반환. 첫번째값 1 반환 만약 빈큐면 예외발생
q.isEmpty(); 	// [1,2] 가 있으므로 false반환
q.contains(1);	// 1이 있으니 true반환. 없으면 false반환

ㅁ 큐 예제

내가 푼 문제다.

풀이는
https://thcoding.tistory.com/127

프로세스

코드는

import java.util.*;
class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 0;
        Queue<Pair> q = new LinkedList<>();
        for (int i = 0; i < priorities.length; i++) {
            q.add(new Pair(priorities[i],i));
        }

        int order = 0; // 처리 순서를 나타내는 변수

        while (!q.isEmpty()) {
            Pair currentPair = q.poll();
            int current = currentPair.value;
            int idx = currentPair.index;
            boolean isBigger = true;

            for (Pair elementPair : q) {
                if (current < elementPair.value) {
                    isBigger = false; // current 가 작을 때
                    break;
                }
            }

            if (isBigger) {
                order++; // 처리 순서 증가
                if (idx == location) {
                    return order;
                }
            } else {
                q.add(currentPair); // 작을 때, 큐 뒤에 다시 넣음
            }
        }

        return answer;
    }
    static class Pair {
        int value;
        int index;

        public Pair(int value, int index) {
            this.value = value;
            this.index = index;
        }
    }
}

 

일단 스택,큐만 작성했다. 다른 자료구조에대해서도 추후에 추가적으로 작성하겠다.