문제 설명

괄호는 여는 괄호와 닫는 괄호가 한 묶음을 이루는 특징을 가지며 다양한 괄호가 존재합니다.

아래의 규칙에 맞추어 입력된 임의의 문자열에 대해 괄호가 올바르게 사용되었는지 확인할 수 있는 해결책을 제시해주세요.

제한사항

• 임의의 문자열 inputString이 입력됩니다.

• 공백으로만 이루어진 문자열은 입력되지 않습니다.

• 입력 문자열의 길이는 1 이상입니다.

• 최대 길이는 명시되지 않습니다.

• 괄호들이 정상적으로 사용되었는지 검증 결과를 반환합니다.

• 괄호는 네 가지 종류 (), {}, [], <> 가 있다고 가정합니다.

• 괄호는 여닫는 특징만을 검증하며, 열려있는 어떤 괄호에 대하여 짝이 달느 닫히는 괄호에 영향을 주지 않습니다.

• 예를 들면 ([]), ([)]은 모두 잘 열고 닫았기 때문에 정상입니다.

• 정상이라면 총 괄호의 수, 비정상(괄호 쌍이 정상적으로 표현되지 않은 경우)이라면 -1을 반환합니다.

Solution

알고리즘 문제에 자주 등장하는 괄호 쌍 검증 문제이다. 다만 기존의 문제들과 조금 다른 점이 있다면 이번 문제는 괄호 쌍이 총 4 쌍 이라는 점과 주어진 문자열이 괄호만으로 이루어져 있지 않는 임의의 문자열에서 괄호들을 검증한다는 점이다.

하지만 문제 차제가 난해하거나 어렵지 않기 때문에 주어진 문제 그대로 구현을 진행하면 쉽게 풀리는 문제이기도 하다.

나같은 경우 먼저 주어진 문자열에서 괄호에 해당하는 경우에 대하여 로직을 진행해야 하기 때문에 처음에는 List를 이용하여 괄호 검증을 진행하였다.

예를들면,

List<Character> open = Arrays.asList('(', '{' ,'[', '<');
List<Character> close = Arrays.asList(')', '}', ']', '>');

와 같이 open, close에 대한 괄호들을 각각 저장하여 주어진 문자열의 문자 하나하나를 검증하는 방향으로 구현하였다.

그러다 보니 어쩔수 없이 List.contains, List.indexOf와 같은 오퍼레이션을 많이 사용하게 되었고, contains, indexOf와 같은 메서드의 구현은 for loop를 사용하기 때문에 조금 더 효율적인 방법이 없을까 고민하기 시작했다.

그러던 중 생각해낸 방법이 HashMap을 이용하여 푸는 방법이었다.

HashMap.get은 List.contains, List.IndexOf와 비교하면 효율성 측면에서 좀 더 좋은 성능을 기대할 수 있을것 같았다.

코드는 아래와 같다.

Code

List를 이용하여 풀이

HashMap을 이용하여 풀이

몇줄 평

어떤 자료구조를 사용해서 문제를 풀이할지 조금만 고민해보면 크게 어렵지 않은 문제였다.

참고 및 출처

• 프로그래머스