WEEK 05 C언어 스택 앤 큐 5,6,7번 문제(4월16일 수요일)

오늘도 어김없이 10시에 코어타임을 진행했습니다.
각 문항에 대해 서로의 풀이 방식을 공유했습니다. 오늘은 목요일이 바로 다음 날이므로 문제들 위주로 풀어보는 시간을 가졌습니다.

5. C언어 Stack and Queue 5번

5. recursiveReverseQueue

문제 설명:

큐를 재귀적으로 뒤집는 C 함수 작성

함수 원형:

void recursiveReverseQueue(Queue *q);

예시:

입력 큐: (1, 2, 3, 4, 5) → 결과 큐: (5, 4, 3, 2, 1)

※ 구현 팁:

if (q->ll.head == NULL) return;
temp = dequeue(q);
recursiveReverseQueue(q);
enqueue(q, temp);

[풀이 방법]

큐가 size만큼 재귀적으로 뒤집어서 출력하면
뒤집어진 큐를 구현할 수 있지 않을까 생각했지만, 그냥 디큐, 인큐로 재귀적으로 풀면 풀린다.

[코드와 해설]

void recursiveReverse(Queue *q)
{
/*
큐가 size만큼 재귀적으로 뒤집어서 출력하면
뒤집어진 큐를 구현할 수 있다. 
*/
    if(q->ll.head == NULL)
    return;
    int temp = dequeue(q);
    recursiveReverse(q);
    enqueue(q, temp);
}

---

6. C언어 Stack and Queue 6번

6. removeUntilStack

문제 설명:

스택에서 특정 값이 나타날 때까지의 모든 값을 pop()하는 C 함수 작성

함수 원형:

void removeUntilStack(Stack *s, int value);

예시:

• (1, 2, 3, 4, 5, 6, 7), value = 4 → (4, 5, 6, 7)
• (10, 20, 15, 25, 5), value = 15 → (15, 25, 5)

[풀이 방법]

특정값(value)이 나오기 전까지 계속 peek을 수행한 후 특정값이 나오면 peek을 중단하고 빼온 값을 출력한다.
해당문제는 밑에 구현되어 있는 peek 함수를 활용하여 구현한다.

[코드와 해설]

void removeUntil(Stack *s, int value)
{
/*
특정값(value)이 나오기 전까지 계속 peek을 수행한 후
특정값이 나오면 pop을 중단하고 빼온 값을 출력한다.
*/
    while(!isEmptyStack(s) && peek(s) != value)  
    // 빌때까지, peek을 사용해서 스택의 가장 위에 있는 항목을 확인해서 값이 Value가 아니면 pop
    pop(s);   //pop 된값이 출력되어 value까지 값을 출력한다.
}

////////////////////////////
// peek은 스택의 가장 위에 있는 값을 반환한다.
int peek(Stack *s){
 // 스택이 비어있는지 확인
    if(isEmptyStack(s))
        // 비어 있으면 최소 정수값 반환 (오류나 없음 표시용)
        return MIN_INT;    
    else
         // 스택이 비어있지 않으면, 가장 위(top)에 있는 값을 반환 (삭제는 하지 않음)
        return ((s->ll).head)->item;
}

---

7. C언어 Stack and Queue 7번

7. balanced

문제 설명:

문자열이 괄호가 균형을 이루는지 확인하는 함수 작성.

허용된 괄호는 ()[]{}
※ 반드시 스택을 사용해야 합니다.

함수 원형:

int balanced(char *expression);

예시 - 균형 잡힌 괄호:

• ()
• ([])
• {[]()[]}

예시 - 균형 잡히지 않음:

• {{)]
• [({{)])

※ 구현 팁:

if {[(: push into stack
else if }]) matches top of stack then pop
마지막에 스택이 비었는지 확인

[풀이 방법]

주어진 소, 중, 대 괄호에 대해 짝이 맞는지 확인하여 짝이 맞다면 balanced를 출력합니다.
스택을 통해서 하나씩 순회하며 짝이 맞는지 확인합니다.
그 이후 짝이 맞으면 수를 1 올리고, 짝이 맞지 않으면 에러를 출력합니다.

[코드와 해설]

int balanced(char *expression)
{
/*
주어진 소, 중, 대 괄호에 대해 짝이 맞는지 확인하여 짝이 맞다면 balanced를 출력합니다.
스택을 통해서 하나씩 순회하며 짝이 맞는지 확인합니다.
그 이후 짝이 맞으면 수를 1 올리고, 짝이 맞지 않으면 에러를 출력합니다.
*/

Stack stack;
stack.ll.head = NULL;
stack.ll.size = 0;
int i = 0;

while(expression[i]) {
    char exp = expression[i];   // expression 자료형은 char

    // 여는 괄호 스택의 push
    if (exp == '(' || exp =='{' || exp =='[') {
        push(&stack, exp);
    }

    // 닫는 괄호 시, 스택에서 짝이 맞는지 확인후 pop
    else if (exp == ')' || exp == '}' || exp ==']') {
        if (isEmptyStack(&stack))
        return 1;

        char top = peek(&stack);

        if ((exp == ')' && top == '(') || (exp == '}'  && top == '{') || (exp == ']'  && top == '[')) {
            pop(&stack);
        }
        else {
            return 1;
        }
    }
    i++;
}
// 모든 괄호가 정상적으로 짝이 맞으면 스택은 비워 있어야한다. 중복이면 안되므로
return isEmptyStack(&stack) ? 0 : 1;
}

[아스키 코드 사용하기]

int balanced(char *expression) {
Stack stack;
stack.ll.head = NULL;
stack.ll.size = 0;
int i = 0;

//ASCII - () -> 40,41 [] -> 91,93 {} -> 123,125 
while(expression[i])
{
    char exp = expression[i];   // expression 자료형은 char로 아스키코드가 담길 것이다.
    // 해당부분에서 현재 읽고 있는 닫힌 괄호.

    if(peek(&stack) == exp -1 || peek(&stack) == exp -2)    //ASCII 코드에서 1, 2차이 나는 경우
    // peek(&stack) 해당부분에서 마지막에 들어간 열린 괄호에 대해 검사(스택의 top)
        pop(&stack);
    else
        push(&stack,exp);

    i += 1;
}

if(isEmptyStack(&stack))
    return 0;        //균형이 잡혀있다를 의미
else
    return 1;
}

스택 앤 큐 마지막 문제는 색다르게 풀어보았습니다.

---

하루 일정

15:00 ~ 16:10
백승현 코치님 재귀 알고리즘, 포인터 관련 특강이 있었다. 아이패드에 정리를 해두긴했는데, 명확하게 이해되지 않은 부분이 있어서 재정리가 필요하다.

16:10 ~ 18:00
다시 스택 큐 마지막 문제부터 풀어보고 있다. 두 가지 방식이 있어서 두가지 방식을 모두 이해와 기록하였다.

18:00 ~19:20
식사와 휴식을 취했다. 휴식 종료 후 남은 문제들을 이어서 풀어보겠다.

Binary Tree도 몇문제 풀었는데, 해당 관련 내용은 다음 포스팅에 이어서 작성하겠다.