문제
https://leetcode.com/problems/valid-parentheses/
풀이
1안
class Solution {
public boolean isValid(String s) {
int length = s.length();
if(length % 2 != 0) return false;
HashMap<Character, Character> map = new HashMap<>();
map.put(')', '(');
map.put(']', '[');
map.put('}', '{');
Stack<Character> stack = new Stack<>();
for(Character c : s.toCharArray()) {
if(c == '(' || c == '[' || c == '{') {
stack.push(c);
} else {
if(stack.isEmpty() || stack.pop() != map.get(c)) {
return false;
}
}
}
return stack.isEmpty();
}
}
속도면에서는 빠르지만, HashMap을 사용해서 메모리를 많이 차지했다.
2안
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for(Character c : s.toCharArray()) {
if(c == '(' || c == '{' || c == '[') {
stack.push(c);
} else {
if(stack.isEmpty()) return false;
if(c == ')' && stack.pop() != '(') {
return false;
} else if(c == '}' && stack.pop() != '{') {
return false;
} else if(c == ']' && stack.pop() != '[') {
return false;
}
}
}
return stack.isEmpty();
}
}
메모리는 적게 사용했지만, 속도가 이전보다 살짝 느려졌다.
3안
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for(Character c : s.toCharArray()) {
if(c == '(') {
stack.push(')');
} else if(c == '{') {
stack.push('}');
} else if(c == '[') {
stack.push(']');
} else {
if(stack.isEmpty()) return false;
if(stack.pop() != c) return false;
}
}
return stack.isEmpty();
}
}
속도는 1안 과 같지만, 메모리는 HashMap을 쓰지 않아 덜 차지하였다.
근데 사실, 그래프로 봐서 그렇지 별 차이는 안나는 것 같.ㅇ...
스택
스택(Stack)은 "쌓다"라는 의미로 하나씩 쌓아올리고, 뺄 때는 위에서부터 빼는 구조이다. LIFO(Last In First Out) 구조라고도 한다. 반대로는 큐(Queue) 구조가 있는데 먼저 들어간 것이 먼저 나오는 구조이다. FIFO(First In First Out) 구조라고도 한다.
당장 우리가 하는 코딩에도 스택구조가 떡하니 있다.
메소드 안에서 메소드를 호출하고, 또 메소드를 호출했다고 생각해보자.
A() {
B()
}
B() {
C()
}
C() {
...
}A를 호출하고 B를 호출하고 C를 호출하고, C가 끝나면 종료되고, B가 종료되고, A가 종료된다. 바로 이게 스택구조이다.
또한, 우리가 사용하는 웹 브라우저에서 '뒤로가기' 기능도 스택이 될 것이다.
스택에는 pop, push가 있다.
push는 삽입연산이다. 스택에 데이터를 삽입한다.
pop은 삭제연산이다. 스택에서 데이터를 뺀다. 이때, 가장 마지막에 들어갔던 데이터가 빠질 것이다.
자바에서 사용하는 메소드는 아래와 같다.
public E push(E item)
Pushes an item onto the top of this stack. This has exactly the same effect as:
addElement(item)
public E pop()
Removes the object at the top of this stack and returns that object as the value of this function.
public E peek()
Looks at the object at the top of this stack without removing it from the stack.
-> pop()은 제일 위에 있는 요소를 추출하면서 리턴도 해주는데, peek()은 리턴만 해주고 추출은 하지 않는다. 즉 그대로 스택에 남아있다.
public boolean empty()
Tests if this stack is empty.
[참고] https://docs.oracle.com/javase/8/docs/api/java/util/Stack.html
