카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴파일하여 로그를 보니 대부분 소스 코드 내 작성된 괄호가 개수는 맞지만 짝이 맞지 않은 형태로 작성되어 오류가 나는 것을 알게 되었습니다.
수정해야 할 소스 파일이 너무 많아서 고민하던 "콘"은 소스 코드에 작성된 모든 괄호를 뽑아서 올바른 순서대로 배치된 괄호 문자열을 알려주는 프로그램을 다음과 같이 개발하려고 합니다.
import java.util.*;
import java.util.stream.*;
class Solution {
public String solution(String p) {
//수행한 결과를 그대로 리턴
return execute(new StringBuilder(p)).toString();
}
//메인 로직
public static StringBuilder execute(StringBuilder sb){
//빈 문자열이면 빈 문자열 리턴
if(sb.length()==0)
return sb;
//최소한의 길이의 균형 잡힌 문자열 구하기
int left=0;
int right=0;
for(int i=0; i<sb.length(); i++){
if(sb.charAt(i)=='(')
left++;
else
right++;
if(left==right)
break;
}
//u, v로 나누기
StringBuilder u=new StringBuilder(sb.substring(0, left+right));
StringBuilder v=new StringBuilder(sb.substring(left+right, sb.length()));
//u가 올바른 문자열이라면 v에 대해서 메인로직을 수행한 후 덧붙여서 리턴
if(isCorrect(u)){
u.append(execute(v));
return u;
}
//하라는 대로 실행
sb=new StringBuilder();
sb.append('(');
sb.append(execute(v));
sb.append(')');
u.deleteCharAt(0);
u.deleteCharAt(u.length()-1);
sb.append(reverse(u));
return sb;
}
//모든 괄호 문자열을 반대로 뒤집는 메서드
public static StringBuilder reverse(StringBuilder sb){
return new StringBuilder(sb.chars()
.mapToObj(o->{
if(o=='(')
return ")";
return "(";
})
.collect(Collectors.joining()));
}
//올바른 문자열인지 확인하는 메서드(스택 사용)
public static boolean isCorrect(StringBuilder sb){
if(sb.charAt(0)==')' || sb.length()%2!=0)
return false;
Stack<Character> stack=new Stack<>();
for(int i=0; i<sb.length(); i++){
if(stack.isEmpty()){
stack.add(sb.charAt(i));
continue;
}
if(stack.peek()!=sb.charAt(i))
stack.pop();
else
stack.add(sb.charAt(i));
}
return stack.isEmpty();
}
}
재귀적인 호출을 문제에서 요구하길래 재귀 호출하는 메서드를 만들어서 하라는 대로 구현했다! 카카오 문제 중에서 제일 쉬운 문제였다.
😁