백준 10828번 | 스택 문제 풀이 (Java)

문제

 

제출 코드

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

public class Main {
    
    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        
        Stack<String> st = new Stack<>();
        
        for(int i = 0; i < N; i++) {
            String[] arr = br.readLine().split(" ");
            String cmd = arr[0];
            
            switch(cmd) {
                    case "push":
                    st.push(arr[1]);
                    break;
                    case "pop":
                    if(st.isEmpty()) {
                        bw.write("-1\n");
                    } else {
                        bw.write(st.pop()+"\n");                        
                    }                    
                    break;
                    case "size":
                    bw.write(st.size()+"\n");
                    break;
                    case "empty":
                    if(st.isEmpty()) {
                        bw.write("1\n");
                    } else {
                        bw.write("0\n");
                    }                                        
                    break;
                    case "top":
                    if(st.isEmpty()) {
                        bw.write("-1\n");
                    }else {
                        bw.write(st.peek()+"\n");
                    }                    
                    break;
            }
        }
            
            bw.flush();
            bw.close();
            br.close();
    }
    
}

 

 

자바 Stack 내부로직

 

push 내부 로직

1. 현재 저장된 요소 개수(s)와 배열(elementData)의 크기를 비교

2. 배열이 꽉 찼으면 크기 증가(grow())

-> grow()는 기존 배열보다 더 큰 크기의 새 배열을 만들고 데이터를 복사

3. s 위치에 새 데이터 저장

4. s(현재 요소 개수) 증가하여 새로운 요소를 추가할 수 있도록 함

 

private void add(E e, Object[] elementData, int s) {
	if(s == elementData.length) {
		elementData = this.grow();
	}
	elementData[s] = e;
	this.elementCount = s + 1;
}

 

size 내부 로직

1. 현재 저장된 요소 개수 반환

-> elementCount 변수 사용 하는 이유는 O(1) 연산으로 빠르게 요소 개수를 반환하기 위해

public synchronized int size() {
    return this.elementCount;
}

 

peek 내부 로직

1. 스택이 비어있으면 EmptyStackException 발생

2. 스택의 최상단 요소를 반환

public synchronized E peek() {
    int len = this.size();
    if(len == 0) {
        throw new EmptyStackException();
    } else {
        return (E) this.elementAt(len - 1);
    }
}

...

E elementData(int index) {
    return (E) this.elementData(index);
}

 

pop 내부 로직

 

1. 삭제하려는 index가  올바른 범위인지 확인

2. 삭제할 요소 뒤에 몇 개의 요소가 남아 있는지 계산(this.elementCount - index - 1)

3. index 이후의 요소들을 한 칸 앞으로 당겨 빈 공간을 메움

4. 요소 개수 감소(--elementCount)

5. 배열 마지막 요소를 null로 설정하여 메모리 해제(GC 대상이 되도록 처리)

public synchronized void removeElementAt(int index) {
    if (index >= this.elementCount) {
        throw new ArrayIndexOutOfBoundsException((index + " >= " + this.elementCount));
    } else if (index < 0) {
        throw new ArrayIndexOutOfBoundsException(index);
    } else {
        int j = this.elementCount - index - 1;
        if( j > 0) {
            System.arraycopy(this.elementData, index + 1, this.elementData, index, j);
        }

        ++this.modCount;
        --this.elementCount;
        this.elementData[this.elementCount] = null;
    }
}

 

 

Stack 이외

- ArrayList

ArrayList<T> list = new ArrayList();

// push
public void push(T item) {
	list.add(item);
}

// pop
public void pop() {
	if(list.isEmpty()) throw RuntimeException("Stack is Empty");
    return list.remove(list.size() - 1);
}

// peek
public void peek() {
	if(list.isEmpty()) throw RuntimeException("Stack is Empty");
	return list.get(list.size() - 1);
}

// size
public int size() {
	return list.size();
}

 

- LinkedList

LinkedList<T> list = new LinkedList();

// push
public void push(T item) {
	list.addFirst(item);
}

// pop
public void pop() {
	if(list.isEmpty()) throw RuntimeException("Stack is Empty");
    return list.removeFirst();
}

// peek
public void peek() {
	if(list.isEmpty()) throw RuntimeException("Stack is Empty");
	return list.getFirst();
}

// size
public int size() {
	return list.size();
}

 

- ArrayDeque

ArrayDeque<T> deque = new ArrayDeque();

// push
public void push(T item) {
	deque.push(item);
}

// pop
public void pop() {
    return deque.pop();
}

// peek
public void peek() {
	return deque.peek();
}

// size
public int size() {
	return deque.size();
}

 

 

 

문제 의도

- 스택의 기본 동작 이해

 

문제 출처