C# 코딩테스트 강좌, 스택과 큐

서론

안녕하세요! 이번 강좌에서는 C#을 사용하여 스택과 큐를 활용한 알고리즘 문제를 풀어보겠습니다.
스택과 큐는 컴퓨터 과학에서 가장 기본적이고 중요한 데이터 구조 중 하나로, 다양한 알고리즘 문제를 해결하는 데 널리 사용됩니다.
이 강좌를 통해 스택과 큐의 기본 개념을 이해하고 실제 코딩 테스트에서 자주 출제되는 문제를 풀면서
이 두 가지 구조에 대한 깊은 이해를 심화할 수 있길 바랍니다.

스택(Stack)과 큐(Queue)의 기본 개념

스택은 후입선출(LIFO, Last In First Out) 구조를 가지며, 마지막에 들어온 데이터가 가장 먼저 나갑니다.
큐는 선입선출(FIFO, First In First Out) 구조를 가지고 있으며, 가장 먼저 들어온 데이터가 가장 먼저 나갑니다.
이 두 가지 구조는 다양한 프로그래밍 문제를 해결하는 데 있어서 중요하게 사용됩니다.

문제: 괄호 균형 검사하기

문제 설명: 주어진 문자열에서 같은 종류의 괄호가 올바르게 열리고 닫혔는지 검사하는 함수를 작성하세요.
올바른 괄호의 예는 “()[]{}”, 그리고 잘못된 괄호의 예는 “(]”, “([)]”입니다.

입력

문자열 s (1 <= s.length <= 100) – 소문자 및 대문자, 숫자와 괄호로 이루어져 있습니다.

출력

모든 괄호가 올바르게 열리고 닫히면 true를, 아니면 false를 반환합니다.

예제

    입력: s = "()"
    출력: true

    입력: s = "([)]"
    출력: false

문제 풀이 과정

이 문제를 풀기 위해 스택 자료구조를 사용할 것입니다. 스택에 열린 괄호를 푸시(push)하고 닫힌 괄호가 나올 때마다
스택의 최상위 요소와 비교하여 올바른 괄호인지 검사할 것입니다.
과정은 다음과 같습니다:

괄호의 쌍을 저장하는 맵을 생성합니다. 예를 들어, { ‘)’: ‘(‘, ‘]’: ‘[‘, ‘}’: ‘{‘ }과 같이 정의합니다.
스택을 초기화합니다.
문자열을 하나씩 순회합니다.
만약 현재 문자가 열린 괄호라면 스택에 푸시합니다.
닫힌 괄호라면 스택이 비어 있는지 확인하고, 비어 있지 않다면 스택의 최상위 요소와 매칭되는지 검사합니다.
문자열을 모두 순회한 후, 스택이 비어 있다면 true, 아니라면 false를 반환합니다.

C# 코드 구현


    using System;
    using System.Collections.Generic;

    public class Solution
    {
        public bool IsValid(string s)
        {
            // 괄호 쌍을 저장하는 딕셔너리
            Dictionary<char, char=""> parentheses = new Dictionary<char, char="">()
            {
                { ')', '(' },
                { ']', '[' },
                { '}', '{' }
            };

            Stack stack = new Stack(); // 스택 초기화

            foreach (char c in s)
            {
                if (parentheses.ContainsKey(c)) // 닫힌 괄호인지 확인
                {
                    // 스택이 비어있거나 최상위 요소가 맞지 않으면 false
                    if (stack.Count == 0 || stack.Pop() != parentheses[c])
                    {
                        return false;
                    }
                }
                else // 열린 괄호인 경우
                {
                    stack.Push(c); // 스택에 푸시
                }
            }

            return stack.Count == 0; // 스택이 비어있으면 true 반환
        }
    }
    </char,></char,>

코드 설명

위의 코드는 문자열 `s`를 입력받아 괄호의 균형을 검사하는 함수 `IsValid`를 정의합니다.
먼저, 괄호 쌍을 정의하고, 스택을 초기화합니다. 그 후, 입력된 문자열을 순회하며 열린 괄호는 스택에 푸시하고,
닫힌 괄호에 대해서는 스택의 최상위 요소와 비교하여 올바른 매칭인지 확인합니다.
모든 문자를 확인한 후 스택이 비어 있다면 모든 괄호가 올바르게 열리고 닫힌 것으로 판단하여 true를 반환합니다.

추가 예제

예제 1

    입력: s = "{[]}"
    출력: true

설명: ‘{‘로 시작해서 ‘}’로 끝나며, 중간에 ‘[‘와 ‘]’가 올바르게 매칭되어 있습니다.

예제 2

    입력: s = "({[})"
    출력: false

설명: ‘(‘가 열린 후 ‘]’가 바로 나오므로 올바른 쌍이 아닙니다.

복습 문제

이번 강좌에서는 스택을 활용하여 괄호 균형 검사 문제를 풀어보았습니다.
여러분이 이제 스택과 큐에 대해 좀 더 잘 이해할 수 있게 되었겠길 바랍니다.
다음으로 시도해볼 만한 문제는 “스택을 이용해 큐 구현하기”입니다.
이는 스택의 기본 개념과 그 활용을 더욱 깊이 있게 배울 수 있는 문제입니다.
직접 구현해보고, 코드를 작성해보시길 추천드립니다!

결론

스택과 큐는 알고리즘 및 프로그래밍에서 매우 중요한 자료 구조입니다.
이 두 가지 자료 구조를 활용하여 해결할 수 있는 문제의 종류는 많습니다.
이번 강좌가 여러분이 향후 프로그래밍 문제를 푸는 데 많은 도움이 되었기를 바랍니다!
계속해서 스택과 큐의 활용을 공부해보세요.

서론