Stack4 [Problem Solving] BOJ 16120: PPAP 문제 출처: https://www.acmicpc.net/problem/16120 문자열에 있는 P를 PPAP로 바꿀 수 있다고 할 때 이 과정을 반복해서 만들어진 문자열을 PPAP문자열이라고 한다. 주어진 문자열이 PPAP 문자열인지 판단하는 문제이다.이 문제는 스택을 사용하면 O(len(word))에 풀 수 있다. 문자열 왼쪽에서 오른쪽 순서로 stack에 추가한다.stack의 길이가 4개 이상이 되면 가장 최근에 들어간 4개의 문자열이 PPAP인지 확인하고 그렇다면 4개를 빼고 P를 넣는다.주어진 문자열이 PPAP 문자열이었다면 스택에는 P 하나만 남게 된다. 그렇다면 PPAP를 출력하고 그렇지 않다면 NP를 출력한다. import sysread = sys.stdin.readlineword = rea.. 2025. 6. 28. [Problem Solving] BOJ 2504 : 괄호의 값 문제 링크 : https://www.acmicpc.net/problem/2504 4개의 기호 (, ), [, ]를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.한 쌍의 괄호로만 이루어진 '() '와 '[]'는 올바른 괄호열이다.만일 X 가 올바른 괄호열이면 '(X)' 이나 '[X]'도 모두 올바른 괄호열이 된다.X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY 도 올바른 괄호열이 된다.예를 들어'(()[[]])'나 '(())[][]' 는 올바른 괄호열이지만 '([)]' 나 '(()()[]' 은 모두 올바른 괄호열이 아니다. 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호 값)을 아래와 같이 정의하고 값(X)로 표시한다.'()'인 괄호열의 값은 2이다.'[]' 인 괄호.. 2025. 1. 27. [Problem Solving] BOJ 2812 : 크게 만들기 문제 링크 : https://www.acmicpc.net/problem/2812 N자리 수에서 K개의 수를 제외했을 때 가장 큰 값을 만드는 문제이다. 스택을 이용하여 풀 수 있다. 1. 높은 자리 수 부터 스택에 넣을 것인데, 스택의 최상단 값이 넣으려는 값 보다 크거나 같으면 넣는다.2. 스택의 최상단 값이 넣으려는 값 보다 작다면 넣으려는 값보다 크거나 같은 값이 나올 때 까지 제외시킨다. 이 때 최대 K개 만큼 제외 시킨다.3. K개 만큼 제외 시켰다면 스택 최하단 ~ 최상단값과 남은 숫자들을 이어 붙인 것을 출력하면 정답이다.4. K개 만큼 제외시키지 못했다면 스택 최하단 ~ 최상단값과 남은 숫자들을 이어 붙인 뒤 맨 뒤에서 (K - 제외된 수의 개수) 만큼 제외하고 출력한다. #include .. 2024. 8. 16. [Data Structures] Stack and Queue (스택과 큐) Stack입력과 출력이 한 곳(Top)에서만 발생하는 자료구조이다.LIFO(Last In First Out) : 가장 나중에 들어간 것이 가장 먼저 나온다.함수의 콜 스택, DFS 등에서 사용된다. 다음은 스택의 ADT이다.struct Node;typedef struct Node *PtrToNode;typedef PtrToNode Stack;typedef int ElementType;typedef int bool;struct Node{ ElementType Element; PtrToNode Next;};Stack CreateStack();bool isEmpty(Stack);void MakeEmpty(Stack);void Push(ElementType, Stack);ElementType Top(.. 2024. 7. 11. 이전 1 다음