프로그래머스 - 괄호변환(Java)

roach·2021년 2월 5일

알고리즘

목록 보기

3/4

코딩테스트를 하기전 가져야 할 필수 덕목

문제를 열심히 읽어라 ⇒ 사실 문제에 풀이 방식이 써져있는 경우가 가끔씩 있다.
테스트 케이스를 파악하라 ⇒ 아래 문제에서도 설명하겠지만, 테스트 케이스만 잘봐도 이상한 로직으로 빠져들지 않는다
문제의 요구사항을 정확히 파악한 뒤 코드를 작성하라 ⇒ 요구사항을 정확하게 모른 뒤 작성하면 나중에 뒤엎는 비용이 발생할 수 있다. 그냥 처음부터 제대로 읽어라
일단 자신의 방식대로 푼뒤 남의 방식을 참조하여 좋은 부분들을 공부하고 다시한번 풀어보자

요구사항⁉️

카카오에 신입 개발자로 입사한 콘은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 
소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 
소스를 컴파일하여 로그를 보니 대부분 소스 코드 내 작성된 괄호가 개수는 맞지만 짝이 맞지 않은 
형태로 작성되어 오류가 나는 것을 알게 되었습니다.
수정해야 할 소스 파일이 너무 많아서 고민하던 콘은 소스 코드에 작성된 모든 괄호를 뽑아서 
올바른 순서대로 배치된 괄호 문자열을 알려주는 프로그램을 다음과 같이 개발하려고 합니다.

균형잡힌 괄호 문자열 p가 매개변수로 주어질 때, 주어진 알고리즘을 수행해 올바른 괄호 문자열로 변환한 결과를
return 하도록 solution 함수를 완성해 주세요.

문제 내에서 사용되는 용어

'(' 와 ')' 로만 이루어진 문자열이 있을 경우, '(' 의 개수와 ')' 의 개수가 같다면 이를 균형잡힌 괄호 문자열

균형잡힌 괄호 문자열은 말 그대로 일반적으로 우리가 수가 맞다고 생각되는 문자열을 말한다.

근데 이런 문자는 "(()))(" 균형은 잡혀있지만 문법상 올바르지 않다고 느낄 수 있다. 따라서 해당 문자열은

올바른 괄호 문자열 은 아니라고 한다. 우리의 목적은 올바른 괄호 문자열을 빼내주는 것이다 . 그렇다면 어떻게 문제 로직을 처리하여야 할까?

문제에서 주어진 로직

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 
2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상
	 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 
3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 
  3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. 
4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 
  4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다. 
  4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다. 
  4-3. ')'를 다시 붙입니다. 
  4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 
  4-5. 생성된 문자열을 반환합니다.

여기서 키포인트 두가지가 있다. 문자열을 U(최소한의 균형잡힌 문자열 ⇒ 더이상 분리 불가능), V 는 빈 문자열이 될 수 있다. 자 이게 문제에 어느정도 답안을 써놓은게 "더이상 분리 불가능?" ⇒ 이건 그냥 분리 될때까지 재귀 혹은 어떤식으로든 반복을 시키라는 것이다. 그래서 다 나눠지면 V 는 빈 문자열일 수도 있어 라고 말해주는 것이다.
사실 문제 자체는 어려운 것 같은데, 저런 키포인트 힌트 때문에 2단계에 종착해 있지않나 싶기도하다.
여튼 그러면 우리의 관심사는 일단 어떻게 최소한의 균형잡힌 문자열을 배출해 내는 것인가?
- 문제를 읽어보면 일단 균형잡힌 괄호문자열 이 주어지고, 해당 알고리즘을 수행해서 올바른 괄호 문자열 로써 우리가 변환해 내는게 목표이다.
- 일단 간단히 생각했을때 균형잡힌 문자열에서 ( 가 나오면 특정 수를 ++ 하고, ) 나오면 특정수를 -- 한다고 해보자. 그리고 특정수가 0이 될때마다, 또 다른 특정수를 ++ 해준다. 그러면 우리가 적어도 몇개의 균형잡힌 괄호 문자열이 있는지 알 수 있을 것이다. 예를 들면 )))(((() 의 경우에는 처음에는 -3 이 되었다가 이윽고나오는 ( 3개 연속으로 0이 될테고, 그때의 문자열을 뽑아내면 )))((( 최소한의 균형잡힌 문자열이 된다.
- 그렇다면 u = )))((( 될테고, v = () 이 될것이다. 그러면 우리는 위의 로직을 코드로 구현해야 할것이다. 그래서 나는 위의 로직을 아래와 같이 구성했다.
```
public int splitString(String p){
	    String[] splitString = p.split("");
	    int count = 0;
	    int index = 0;
	    for(int i = 0; i < splitString.length; i++){
	        if(splitString[i].equals("(")) count++;
	        else count--;
	
	        if(count == 0){
	            index = i + 1;
	            break;
	        }
	    }
	    return index;
	}
```
- 그럼 이제 해당 로직에서 나온 인덱스를 기반으로 문자열을 Split 해주기만 하면 된다.
```
int index = splitString(p);
String u = p.substring(0, index);
String v = p.substring(index);
```
- 자이제 문제 키포인트의 반절은 왔다. 그러면 위에서 설명했듯이, 일단 올바른 괄호 문자열 인지를 구분하는 함수를 작성해야 한다. 위의 함수랑 헷갈려서는 안된다. 일단 올바른 괄호 문자열의 제일 간단한 조건을 생각해보면 무조건 ( 가 먼져 나온다. 그러므로 if(count < 0) return false; 문을 위반 할 수가 없다. 만약 위반한다면, 균형만 잡혀있지, 올바르지 않은 괄호 문자열이라는 것이다. 만약 해당 조건문을 통해서 올바르다면, 바로 정답 문자열에 추가해줘도된다. (그래서 정답 문자열은 StringBuilder 를 사용했다.)
```
public boolean validateString(String p){
      String[] split = p.split("");
      int count = 0;
      for(String s : split){
          if(s.equals("(")) count++;
          else count--;

          if(count < 0) return false;
      }
      return true;
  }
```
- 자 그러면 우리의 1차적인 로직은 완성됬다. 최소한의 균형잡힌 문자열의 분리와, 올바른 괄호 문자열인지 알아내는 함수까지 작성했다. 그런데 우리의 목적은 올바른 괄호 문자열 을 생성해 내는 것이다. 그래서 우리는 올바른 괄호 문자열로끔 바꿔줄 로직이 필요하다. 이 로직은 무엇이냐 아까 위에서 설명한 것과 같다. 무조건 ( 가 먼져이므로, ) 가 먼져 나온다면 문자열에 ( 를 추가한다. 그리고 ( 가 나온다면 ) 을 추가해준다. 그니까 치환해준다고 생각하면 된다. 근데 여기서 그럼 이런생각이 들수가 있다. (()) 이 들어오면.. 맞는데도 이상하게 바뀌는거 아니에요? 걱정안해도 되는게 여기는 틀린 문자열만 들어올 것이기 때문에 상관이 없다. 그럼 우리의 조건식도 채워졌다. 틀린 문자열일 경우 setValidateGrammer 로 들어와! 라는 조건문을 메인 로직에서 실행시켜주면 된다.
- (step 4-4 참고 int i = 1; i < split.length - 1;)
```
public String setValidateGrammer(String p){
      String[] split = p.split("");
      StringBuilder sb = new StringBuilder();
      for(int i = 1; i < split.length - 1; i++){
          if(split[i].equals("(")) sb.append(")");
          else sb.append("(");
      }
      return sb.toString();
  }
```
  메인 로직 (Step-4 의 로직수행)
```
    public String getValidateString(String p){
        int index = splitString(p);
        String u = p.substring(0, index);
        String v = p.substring(index);

        if(validateString(u)) sb.append(u);
        else {
            sb.append("(");
            if(!v.equals("")){
               getValidateString(v);
               v = "";
            }
            sb.append(")");
            sb.append(setValidateGrammer(u));
        }
        if(!v.equals("")){
            getValidateString(v);
        }

        return sb.toString();
    }
```
- 처음에 U / V 분리를 마친뒤에 최소한의 균형잡힌 문자열이 올바른 문자열인지 확인한다.
- 맞다면 정답(sb) 에 append 해준다.
- 아니라면 정답에 ( 을 추가해준다
- v 는 빈 문자열이 될때까지 재귀를 해주어야 하므로, v 가 빈 문자열이 아니라면 재귀적으로 실행시킨다.
- 그리고 문자열에 ) 를 추가해준다.

느낀점

풀이 방법이 문제에 주어지는 터라 어렵지는 않은 문제 같으나.
어떻게 요구사항을 정리하고, 어떤 방식으로 문제를 풀어나가는 것이 좋은지를 공유하기 위해 적어보았다.
토요일 코딩 테스트 화이팅~! 🔥

roach

모든 기술에는 고민을

이전 포스트

프로그래머스 - 카카오컬러링북

다음 포스트