코딩테스트는 현대의 IT 기업에서 필수적인 절차입니다. 많은 지원자들이 알고리즘과 자료구조를 이해하고, 이를 바탕으로 문제를 해결하는 능력을 평가받기 위해 준비하고 있습니다. 이 글에서는 C#을 활용하여 알고리즘 문제를 해결하는 방법에 대해 자세히 살펴보겠습니다.
문제: 유효한 괄호 문자열
주어진 문자열이 유효한 괄호 문자열인지 판단하는 문제입니다. 문자열은 ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ 및 ‘]’ 문자로만 구성됩니다. 유효한 괄호 문자열은 다음 조건을 만족해야 합니다:
- 모든 열린 괄호는 닫힌 괄호로 닫혀야 합니다.
- 닫힌 괄호는 항상 그에 해당하는 최근의 열린 괄호와 짝을 이루어야 합니다.
- 괄호의 닫힘이 열림 이전에 발생하지 않아야 합니다.
예를 들어, 문자열 “{[()]}”는 유효한 괄호 문자열이며, “{[(])}”는 유효하지 않습니다.
문제 해결 과정
1. 문제 분석
이 문제를 해결하기 위해서 스택 자료구조를 사용할 수 있습니다. 스택은 후입선출(LIFO) 방식으로 작동하므로, 열린 괄호를 스택에 추가하고, 닫힌 괄호를 만날 경우 스택에서 가장 최근의 열린 괄호를 제거하는 방식으로 진행하면 됩니다. 모든 괄호를 확인한 후 스택이 비어 있다면 올바른 괄호 문자열입니다.
2. 알고리즘 설계
이 문제를 해결하기 위한 알고리즘은 다음과 같습니다:
- 괄호의 짝을 정의한다:
{ '(': ')', '{': '}', '[': ']' } - 문자열을 순회하면서 열린 괄호는 스택에 추가한다.
- 닫힌 괄호를 만났을 경우, 스택에서 최근 열린 괄호를 꺼내서 짝이 맞는지 확인한다.
- 스택이 비어 있지 않거나 짝이 맞지 않는 경우, 유효하지 않은 문자열로 판단한다.
- 문자열을 모두 탐색 이후, 스택이 비어 있으면 유효한 문자열이다.
3. C# 코드 구현
using System;
using System.Collections.Generic;
public class ValidParentheses
{
public static bool IsValid(string s)
{
Stack stack = new Stack();
Dictionary parentheses = new Dictionary()
{
{'(', ')'},
{'{', '}'},
{'[', ']'}
};
foreach (char c in s)
{
// 열린 괄호일 경우 스택에 추가
if (parentheses.ContainsKey(c))
{
stack.Push(c);
}
else
{
// 닫힌 괄호일 경우 스택 비어있으면 검증 실패
if (stack.Count == 0 || parentheses[stack.Pop()] != c)
{
return false;
}
}
}
// 스택이 비어있다면 유효한 괄호 문자열
return stack.Count == 0;
}
}
class Program
{
static void Main()
{
string input = "{[()]}";
bool result = ValidParentheses.IsValid(input);
Console.WriteLine($"\"{input}\"는 유효한 괄호 문자열인가? {result}");
}
}
4. 알고리즘 분석
위 코드는 스택을 사용하여 문자열을 한 번 순회하는 방식으로, 시간 복잡도는 O(n)입니다. n은 문자열의 길이입니다. 공간 복잡도 역시 O(n)입니다. 스택에 최대 n개의 열린 괄호가 쌓일 수 있기 때문입니다. 이 알고리즘은 입력 문자열이 길어져도 효율적으로 동작할 수 있습니다.
마무리
이번 글에서는 C#을 사용하여 유효한 괄호 문자열 문제를 해결하는 방법에 대해 알아보았습니다. 알고리즘 문제를 풀 때는 문제를 잘 분석하고, 적절한 자료구조를 선택하는 것이 중요합니다. 스택과 같은 간단한 자료구조를 활용하면 복잡한 문제도 효율적으로 해결할 수 있습니다. 더욱 다양한 문제를 통해 알고리즘적 사고를 키우는 데 도움이 되길 바랍니다.