PS(Problem Solving)/C++

문제 링크 https://www.acmicpc.net/problem/10799 문제 정보 입력 한 줄에 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 공백없이 주어진다. 괄호 문자의 개수는 최대 100,000이다. 출력 잘려진 조각의 총 개수를 나타내는 정수를 한 줄에 출력한다. 풀이 생각이 어려웠고 구현은 쉬웠던 문제였다. 여는 괄호는 스택에 push 해주고 닫는 괄호일 때 바로 앞에 괄호가 여는 괄호인지, 닫는 괄호인지를 통해 레이저와 쇠 막대기의 끝을 구별하면 된다. 소스 코드 #include using namespace std; int main(void) { ios::sync_with_stdio(0); cin.tie(0); string str; cin >> str; stack S; int ans..

문제 링크 https://www.acmicpc.net/problem/9012 문제 정보 입력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다. 출력 출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다. 풀이 스택을 활용해서 수식의 괄호 쌍을 해결하는 알고리즘을 이용하면 된다! 소스 코드 #include using namespace std; int main(void) { ios::sy..

문제 링크 https://www.acmicpc.net/problem/3986 문제 정보 입력 첫째 줄에 단어의 수 N이 주어진다. (1 ≤ N ≤ 100) 다음 N개 줄에는 A와 B로만 이루어진 단어가 한 줄에 하나씩 주어진다. 단어의 길이는 2와 100,000사이이며, 모든 단어 길이의 합은 1,000,000을 넘지 않는다. 출력 첫째 줄에 좋은 단어의 수를 출력한다. 풀이 스택을 활용하여 해결 할 수 있는 문제다. 스택이 비어있을 경우에 스택을 추가하고 스택의 top과 문자를 비교해서 같으면 pop하고 다르면 push 하는 것을 통해 스택이 비어있으면 좋은 단어이고, 스택이 비어있지 않으면 좋은 단어가 아니다. 소스 코드 #include using namespace std; int main(void)..

문제 링크 https://www.acmicpc.net/problem/4949 문제 정보 입력 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마지막에 점 하나(".")가 들어온다. 출력 각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다. 풀이 스택을 활용하여 수식의 괄호 쌍 문제를 해결 할 수 있다. 수식의 괄호 쌍 알고리즘은 블로그 내 글을 통해 확인할 수 있다. - 스택의 활용(수식의 괄호 검사) 소스 코드 #include using namespace std; int main(void) { ios::sync_wi..

문제 링크 https://www.acmicpc.net/problem/1021 문제 정보 입력 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다. 출력 첫째 줄에 문제의 정답을 출력한다. 풀이 문제를 이해하는 것이 상당히 힘들었다. 양방향 순환 큐라는 것을 통해 덱을 이용해서 풀이할 수 있다는 것을 생각할 수 있다. 예시를 들어서 문제를 이해해보자. 만약 n = 10에서 4를 뽑아야 한다고 생각해보자. 덱 : 1 2 3 4 5 6 7 8 9 10 여기에서 4를 뽑을려면 왼쪽으로 이동해..

문제 링크 https://www.acmicpc.net/problem/10866 문제 정보 입력 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다. 출력 출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다. 풀이 STL Deque를 이해하면 쉽게 해결할 수 있다! 소스 코드 #include using namespace std; int main(void) { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; deque DQ; while (n--) { stri..

문제 링크 https://www.acmicpc.net/problem/2164 문제 정보 입력 첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다. 출력 첫째 줄에 남게 되는 카드의 번호를 출력한다. 풀이 문제의 조건을 잘 읽어서 큐로 풀어야 한다는 것을 파악하면 쉽게 해결할 수 있다. 문제에서 1부터 n까지의 카드를 1이 제일 위로 오게 순서대로 밑으로 놓여져 있고, 제일 위에 있는 카드를 버린다는 것을 통해 먼저 들어간 것이 먼저 나오는 (FIFO) 구조를 떠올릴 수 있다. 소스 코드 #include using namespace std; int main(void) { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; queue Q; for (int..

문제 링크 https://www.acmicpc.net/problem/10845 문제 정보 입력 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다. 출력 출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다. 풀이 STL Queue를 이해하면 쉽게 해결할 수 있다! 소스 코드 #include using namespace std; int main(void) { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; queue Q; while (n--) { strin..