프로그래머스 괄호 변환 C++

 

 

문제 해석

다른 개발자가 작성한 소스 코드를 분석해 문제점을 찾고, 수정하는 업무를 진행중이다.

소스 코드 내 작성된 괄호가 개수는 맞지만 짝이 맞지 않은 형태로 되어 있어 오류가 생긴다는 것을 알게 되었고

모든 괄호를 뽑아 올바른 순서대로 배치된 괄호 문자열을 알려주는 프로그램을 개발 할려고 한다.

 

() 로 이루어진 문자열은 균형잡힌 괄호 문자열

() 짝이 맞는 경우는 올바른 괄호 문자열이라고 한다.

 

예시

1. ((()))( = 균형잡힌 괄호

2. (())() = 균형잡힌 괄호 & 올바른 문자열

 

해당 프로그램을 작성하는 방법이 주어진다.

 

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환해준다.

2. w를 균형잡힌 문자열이라고 한다면, u, v로 분리해 준다.

3. u는 더 이상 분리할 수 없어야 하며, v는 빈문자열 일수도 있다.

3-1. u가 올바른 문자열이라면, 문자열 v에 대해 1단게부터 다시 수행한다

4. 문자열 u가 올바른 괄호가 아닌 경우

4-1. 빈 문자열에 첫 번째 문자로 ( 를 이어 붙인다.

4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙인다.

4-3. 결과가 나오면 ) 를 이어 붙여준다.

4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙여준다.

4-5. 생성된 문자열을 본문에 반환하여 준다

 

균형잡힌 괄호 p가 매개변수로 주어 질 때, 위의 알고리즘 조건에 따라 올바른 괄호를 반환하는 프로그램을 작성한다.

 

문제 풀이 

우선 재귀를 활용해야 하기 때문에 

1. 함수를 만들어 주고 알고리즘 1번에 따라 문자열이 비어 있는지 확인 해준다.

2.다음 괄호 문자열을 빠르게 검사하기 위해 투 포인터 방식을 이용하여 u와 v를 분리 하여준다.

3-1 올바른 괄호인지 확인을 위해 따로 함수를 만들어 확인한다

      만약 올바르다면 u에 재귀함수에 v를 넣어 나온 문자열을 + 해주고 리턴해준다.

 

4. 올바르지 않은경우 

4-1. 문자열 str ( 선언해주고

4-2. 위에서 선언한 문자열 str에 v에 대해 재귀함수를 통한 결과를 + 해준다

4-3. 그리고 str에 += )  해준다

4-4 반복문을 1부터 size-1까지 첫번째와 마지막 문자를 제거하고

       u[i]가 ( 인 경우    ) 더해주고   아니라면 ( 더해주어  나머지 문자열의 괄호 방향을 뒤집어서

       str에 붙여준다.

4-5. 해당 결과를 반환 해준다

 

코드