1. 스택 문제 (백준 10828)
문제
정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 다섯 가지이다.
- push X: 정수 X를 스택에 넣는 연산이다.
- pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- size: 스택에 들어있는 정수의 개수를 출력한다.
- empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
- top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
입력
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
출력
출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
예제 입력
7
pop
top
push 123
top
pop
top
pop예제 출력
-1
-1
123
123
-1
-1
내 제출:
#include <iostream> // 입출력을 위한 헤더
#include <vector> // 스택을 구현하기 위해 vector 사용
#include <string> // 명령어("push", "pop" 등)를 문자열로 처리하기 위해 사용
using namespace std;
int main() {
// C++ 입출력 속도 향상 (백준 필수 세팅)
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; // 명령의 개수를 저장할 변수
if (!(cin >> n)) return 0; // 입력이 실패하면 프로그램 종료
vector<int> st; // 스택 역할을 할 vector (후입선출, LIFO 구조)
string cmd; // 명령어를 저장할 변수
// 명령어 개수(n)만큼 반복
while (n--) {
cin >> cmd; // 명령어 입력
if (cmd == "push") {
// push X : 스택에 정수 X를 넣는 명령
int x;
cin >> x; // 넣을 값 입력
st.push_back(x); // 벡터의 맨 뒤에 삽입 (스택의 top에 넣는 것과 동일)
}
else if (cmd == "pop") {
// pop : 스택의 가장 위(top)에 있는 정수를 빼고 출력
if (st.empty())
cout << -1 << '\n'; // 스택이 비어있으면 -1 출력
else {
cout << st.back() << '\n'; // 맨 위 값 출력
st.pop_back(); // 맨 위 값 제거
}
}
else if (cmd == "size") {
// size : 스택에 들어있는 정수의 개수 출력
cout << st.size() << '\n';
}
else if (cmd == "empty") {
// empty : 스택이 비어있으면 1, 아니면 0 출력
cout << (st.empty() ? 1 : 0) << '\n';
}
else if (cmd == "top") {
// top : 스택의 가장 위에 있는 정수 출력 (제거는 안 함)
if (st.empty())
cout << -1 << '\n'; // 비어있으면 -1
else
cout << st.back() << '\n'; // 맨 위 값 출력
}
}
return 0; // 프로그램 정상 종료
}2. 요세푸스 문제 (백준 1158)
문제
요세푸스 문제는 다음과 같다.
1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)
출력
예제와 같이 요세푸스 순열을 출력한다.
예제 입력
7 3예제 출력
<3, 6, 2, 7, 5, 1, 4>내 제출:
#include <iostream>
#include <queue>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k; // N과 K 입력
queue<int> q; // 원을 표현하기 위한 큐
// 1 ~ N까지 큐에 순서대로 넣기
for (int i = 1; i <= n; i++) {
q.push(i);
}
cout << '<'; // 출력 형식의 시작 괄호
// 큐가 빌 때까지 반복 (모든 사람이 제거될 때까지)
while (!q.empty()) {
// K-1번째 사람까지 맨 뒤로 보냄
for (int i = 0; i < k - 1; i++) {
q.push(q.front()); // 맨 앞의 사람을 맨 뒤로 보내기
q.pop(); // 맨 앞 제거
}
// 이제 K번째 사람은 제거될 차례
cout << q.front(); // 제거되는 사람 출력
q.pop(); // 큐에서 제거
if (!q.empty()) cout << ", "; // 남은 사람이 있다면 쉼표 출력
}
cout << '>'; // 출력 형식의 끝 괄호
return 0;
}3. 괄호 문제 (백준 9012)
문제
괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.
여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.
입력
입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다.
출력
출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다.
예제 입력
6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(
예제 출력
NO
NO
YES
NO
YES
NO
내 제출:
#include <iostream>
#include <string>
#include <stack> // 스택 사용
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t; // 테스트 케이스 수
cin >> t;
while (t--) {
string s; // 괄호 문자열
cin >> s;
stack<char> st; // 괄호 검사용 스택
bool isValid = true; // 올바른 괄호 여부 판단 플래그
for (char c : s) {
if (c == '(') {
// 여는 괄호면 스택에 push
st.push(c);
}
else if (c == ')') {
// 닫는 괄호일 때
if (st.empty()) {
// 짝이 맞는 여는 괄호가 없으면 잘못된 문자열
isValid = false;
break;
}
st.pop(); // 짝이 맞으면 pop
}
}
// 모든 문자를 처리한 후에도 스택에 '('가 남아있으면 잘못된 괄호
if (!st.empty()) isValid = false;
cout << (isValid ? "YES" : "NO") << '\n';
}
return 0;
}
