프로그래머스-올바른 괄호

목차

1.문제

2.해결 과정

3.타인의 코드 분석

 

1.문제

 

2.해결 과정

2-1. 문제의 요구사항

• 괄호가 '()'순으로 찍혀 있는지를 확인을 해서 맞으면 true 아니면 false 로 return을 한다.
• 괄호는 '()' 이렇게 열어서 닫히는 패턴으로 해야되며 괄호안에 괄호가 있는 형태인 '(())'로 되어도 괄호로 인정되는 형태여야 한다. 

2-2. 문제 분석

 

이 문제의 묻는 점은 괄호와 괄호안의 괄호를 어떻게 체크를 할 것인가? 라고 생각을 했습니다. 문제의 예시를 봐서는 다음과 같은 규칙을 볼수 있었습니다. 

• '('으로 시작을 한다. -> ')'으로 시작을 하면 괄호가 성립을 하지 않기 때문입니다.
• 괄호의 순서는 '('이 먼저 그 다음은 ')'이 짝을 이룰 것 그리고 문자열 중간에는 '(' 의 갯수가 문자열에서 ')'보다 많을것
• 최종적으로는 모든 문자를 처리한 뒤 '('와')'의 갯수가 같을것.

이를 종합해 보면 다음과 같은 결론이 나옵니다.

• 괄호 문자열은 가장 최근에 열린 괄호가 가장 먼저 닫혀야 하는 구조를 가집니다.
• 현재 문자열을 검사할 때 직전에 처리한 '('의 상태를 유지해야 하며, 이를 위해서 LIFO 특성을 가진 스택을 사용하기로 했습니다. ')'가 등장했을 때 스택이 비어 있다면 즉시 유효하지 않은 상태로 판단할 수 있어 중간 실패를 빠르게 처리할 수 있기 때문입니다.

2-3. 문제 의사코드 순서

 

제가 생각한 의사 코드는 아래와 같습니다. 

 

1.입력 문자열을 char배열로 전환을 한다.

2.char배열을 반복문으로 돌리면서 조건문을 걸고 '('가 나온다면 스택에 push를 한다. 

3.'('이 아닌 경우(else부분)에는 스택이 비어있는지를 확인을 하고 확인 여부인 answer 를 false로 전환을 하고 break를 한다.

4.else 부분에 ')'이면 스택을 pop을 한다.

5.마지막 return 부분에 답이 되는 answer 와 스택이 비어있는지를 같이 return 문에 and조건으로 작성한다. 

 

이 순서대로 작성한 코드는 아래와 같습니다. 

3.타인의 코드 분석

제가 풀었던 방식은 스택을 활용해서 풀었던 방식인데 다른 분들이 제출한 코드의 경우에는 스택을 사용하지 않고 문자열로 문제를 푼 방식이 있었습니다. 코드는 대체적으로는 대동소이했습니다만 여러개를 봤을때 대표적인 코드를 아래에 같습니다.

 

 

1. 접근 방식의 차이

• 스택(Stack) 활용: 자료구조를 사용하여 괄호 간의 관계와 중첩 순서를 추적. 범용적이며 괄호 종류가 다양해져도 대응 가능함.
• 카운터(Counter) 활용: count 변수를 사용해 여는 괄호와 닫는 괄호의 개수 차이만 확인. 개별 요소의 관계보다는 전체적인 균형에 집중함.

2. 도출된 인사이트

• 해당 문제의 경우에는 단일 괄호 유형임을 전제로 하므로, 불필요한 스택 공간을 할당하지 않는 카운터 방식이 메모리 효율성 측면에서 훨씬 유리함을 알았습니다. 
• 단, 추후 다양한 괄호 유형이 포함되는 확장된 문제(예: {[()]})라면 스택 방식을 사용해야 정합성을 보장할 수 있습니다.

 

 

 

문제 출저

https://school.programmers.co.kr/learn/courses/30/lessons/12909

프로그래머스