⚒ 자료구조 스터디 ⚒
📂스택
✅스택이란
- 대표적인 후입선출(LIFO)의 자료구조
- 단방향으로 삽입, 삭제를 진행한다.
❓어디서 쓰나요❓
- 웹 브라우저 뒤로가기
- 실행 취소 (되돌리기)
- 역순 문자열 생성
- 후위 표기법 계산
📂자바에서의 스택
✅구현
- java.util.Stack 클래스를 사용
- 배열이나 연결리스트 사용
🔎 스택 하위 메서드
🔽 push()
데이터를 스택에 추가하고, 해당 값을 반환한다.
🔽 pop()
스택의 마지막 요소를 동시에 삭제 및 반환한다.
🔽 peek()
스택의 마지막 요소를 반환한다.
🔽 empty()
스택이 비어있는지의 여부를 반환한다. 비어있으면 true, 들어있으면 false 값이 반환된다.
🔽 search()
인자를 스택에서 검색하여 해당 위치를 반환한다. 여러 값이 존재시에 마지막 위치를 반환한다. 찾는 값이 없으면 -1을 반환한다.
📐문제풀이
🚩백준: 실버4 - Q28278 스택2
문제
Q. 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령
1 X: 정수 X를 스택에 넣는다. (1 ≤ X ≤ 100,000)2: 스택에 정수가 있다면 맨 위의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
3: 스택에 들어있는 정수의 개수를 출력한다.
4: 스택이 비어있으면 1, 아니면 0을 출력한다.
5: 스택에 정수가 있다면 맨 위의 정수를 출력한다. 없다면 -1을 대신 출력한다.
입력
첫째 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000)
둘째 줄부터 N개 줄에 명령이 하나씩 주어진다.
출력을 요구하는 명령은 하나 이상 주어진다.
예시
🔻 입력값 🔻
9
4
1 3
1 5
3
2
5
2
2
5
🔻 출력값 🔻
1
2
5
3
3
-1
-1
✅백준 문제풀이
🎯 처음 구상도
1. 자바의 Stack 선언
2. 명령어를 받아주는 변수와 스위치문 작성
3. StringTokenizer를 이용해서 " "를 기준으로 입력을 잘라서 저장
4. 각 조건에 맞는 switch문 case에 필요 if문 작성
5. StringBuilder를 사용해서 각각의 결과값들을 저장 및 "\n"을 추가해 줄 바꿈
6. StringBuilder 값 출력
❓개념문제다 보니, 구상만 잘 짜면 완성 가능하다.
💻결과 코드
public class Silver4_Q28278 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
Stack<Integer> stack = new Stack<>();
int N = Integer.parseInt(br.readLine());
while (N > 0){
st = new StringTokenizer(br.readLine());
int input = Integer.parseInt(st.nextToken());
; switch (input){
case 1:
stack.push(Integer.parseInt(st.nextToken()));
break;
case 2:
if (!stack.empty()){
sb.append(stack.pop()).append("\n");
} else {
sb.append(-1).append("\n");
}
break;
case 3:
sb.append(stack.size()).append("\n");
break;
case 4:
if (!stack.empty()){
sb.append(0).append("\n");
} else {
sb.append(1).append("\n");
}
break;
case 5:
if (!stack.empty()){
sb.append(stack.peek()).append("\n");
} else {
sb.append(-1).append("\n");
}
break;
}
N--;
}
System.out.println(sb);
}
}🚩프로그래머스 : Level 2 - 올바른 괄호
문제
Q. 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다.
예를 들어
"()()" 또는 "(())()" 는 올바른 괄호입니다.")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.
🔻입출력 예시🔻
| 입력 | 출력 |
|---|---|
| "()" | true |
| "(())()" | true |
| ")()(" | false |
| "(()(" | false |
✅프로그래머스 문제풀이
🎯 처음 구상도
1. 스택 생성
2. 왼쪽 열린 괄호, 오른쪽 열린 괄호, 명령 실행 횟수, 결과값 boolean 변수 생성 (결과값은 기본값으로 true)
3. 입력받은 값을 char 형태로 나눠서 스택에 집어넣기
4. stack의 크기만큼 반복해서 ')' 인지 '('인지 판별
5. 만약, 처음부터 '('가 나오면 false를 저장후 반복문 종료
6. 반복 도중에 오른쪽 괄호 횟수가 많으면 false 저장후 반복문 종료
7. 반복문 종료 후, 결과값 반환
❓ 간단한 개념으로 응용하는거라 쉽게 구현을 했지만, 테스트케이스 2와 6에서 자꾸 실패.
❌ 실패 이유 분석
처음 구상도에서 ")()()", "))(())와 같은 경우를 고려 안함.
⭕ 해결
반복문 종료 후, 왼쪽 괄호와 오른쪽 괄호의 횟수를 비교하여 같지 않으면 false를 결과값에 저장한다.
💻결과 코드
public class PGM_Level01 {
public static void main(String[] args) throws IOException {
Stack<Character> stack = new Stack<>();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int leftCount = 0, rightCount = 0, count = 0;
boolean result = true;
String s = br.readLine();
char[] charArray = s.toCharArray();
for (char c : charArray) {
stack.push(c);
}
while (!stack.empty()){
char pop = stack.pop();
if ((pop == '(' && count == 0) || (rightCount > leftCount)){
result = false;
break;
}
switch (pop){
case ')':
leftCount++;
break;
case '(':
rightCount++;
break;
}
count++;
}
// 테스트 2, 6 케이스 이걸 고려 못함
if (leftCount != rightCount){
result = false;
}
System.out.println(result);
}
}
