0과 1의 쉼터

풀이 입력된 괄호이후 막대기의 개수를 top라고 하고, 다음과 같은 조건에 의해 result에 막대기의 개수를 더해주면 된다. ')'이전에 '('가 입력되었으면, 쇠막대기가 아니라 레이저이므로 --top한 값을 result에 더해준다. 쇠막대기를 의미하는 ')'만 입력 되었으면, 쇠막대기의 끝 부분에 도달한 것 이기 때문에 1개만 더하고, 현재 막대기의 개수를 1개 감소시킨다. 소스코드 #include #define MAX 100001 int main(){ char stack[MAX]; int top = 0, result = 0; scanf("%s", stack); for (int i = 0; stack[i] != '\0'; i++) if (stack[i] == '(') top++; else{ if (i..

풀이 Deque(Double Ended Queue)는 Stack와 Queue의 특징을 모두 갖는 이중 연결 리스트(Doubly Linked List)의 구조이다. 쉽게말해 방향이 반대인 Stack 두개를 붙인 것과 같다. 역방향 Stack 0 1 " " " 4998 4999 front 정방향 Stcak 5000 5001 " " " 10000 10001 rear 역방향 Stack과 정방향 Stcak를 합치고, 중간 index(4999~5000)에서 front를 감소, rear를 증가시키는 방식으로 구현했다. 0 1 " " " 4998 4999 5000 5001 " " " 10000 10001 front rear 단, front와 rear이 일치하는 경우는 없다는 점에 유의하자. front + 1이 rear..

풀이 입력되는 괄호가 쌍을 이루는지 묻는 문제이다. 괄호의 개수가 같아도 항상 쌍을 이루는 것이 아님을 유의하자. ex) : ( ) ) ) ( ( ( ) stack 구조에서 top변수를 통해 몇 개의 값을 가지고 있는지 알 수 있었다. 이번 문제에서도 top변수를 이용해 '('와 ')'의 구성비를 알아내 문제를 해결할 수 있다. '('일 때 top++, ')'일 때 top-- 를 하여 stack 구조를 이용한다. (top == 0 일 때 VPS이다.) '('가 ')'보다 적으면 VPS가 아니고 (top == -1), '('가 ')' 보다 많을 때도 VPS가 아니다.(top > 0) 따라서 , top가 0이 아니면 VPS가 아님을 알 수 있다. 소스코드 #include #include int main() ..