[알고리즘] 프로그래머스 괄호 변환 Java(자바)
- 문제
https://programmers.co.kr/learn/courses/30/lessons/60058#
코딩테스트 연습 - 괄호 변환
카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를
programmers.co.kr
- 코드 설명
괄호 규칙이 어긋나는 문자열을 정상적으로 바꿔주는 문제입니다.
괄호를 만드는 규칙이 주어지고 이것을 코드로 변환하면 됩니다.
올바른 괄호 문자열을 판별하는 문제를 최근에 풀어서 체크하는 함수를 빠르게 만들 수 있었습니다.
재귀의 분기점을 잘 위치시키는게 중요하다고 생각이 들었네요.
여기서 실수한것이 concat을하고 반환값을 다시 넣어주어야하는데 그렇게 하지 못해서 이걸 찾는데 시간이 조금 걸렸습니다. 이런 사소한 실수가 모이면 실력이 되니 속도도 중요하지만 정확도도 중요!
다른사람들의 풀이를 보다가 Stinrg + String연산도 많이 보이길래 한번 비교해봤습니다.
참고
https://redfin.engineering/java-string-concatenation-which-way-is-best-8f590a7d22a8
concat 보다 String+의 연산이 성능상 우위를 보인다고 생각했는데 실제 결과는 조금 다르게 나오네요...
가독성 측면에서는 + 연산이 확실히 좋아 보입니다. 그래서 성능차이가 크지 않거나 우위를 점한다면 앞으로 +연산을 위주로 쓸려고 생각했습니다.
- String.concat() 이용
class Solution {
public String solution(String p) {
String answer = "";
answer = sol(p);
return answer;
}
static String sol(String p){
String u,v;
int idx = 0;
int count = 0;
if(check(p) == true) return p;
for(idx = 0; idx<p.length(); idx++){
if(p.charAt(idx) == '(') count++;
else if(p.charAt(idx) == ')') count--;
if(count == 0) break;
}
u = p.substring(0,idx+1);
v = p.substring(idx+1);
if(check(u) == true) return u.concat(sol(v));
else{
String temp = "("; //4-1
temp = temp.concat(sol(v)+")");// 4-2,4-3
//4-4
u = u.substring(1,u.length()-1);
for(String str : u.split("")){
if(str.equals("(") == true)
temp = temp.concat(")");
else if(str.equals(")") == true)
temp = temp.concat("(");
}
//4-5
return temp;
}
}
static boolean check(String p){
int len = p.length();
int count = 0;
for(int i=0; i<p.length(); i++){
if(p.charAt(i) == '(')
count++;
else if(p.charAt(i) ==')'){
count--;
}
if(count < 0) return false;
}
return true;
}
}- StringBuilder 이용
class Solution {
public String solution(String p) {
String answer = "";
StringBuilder sb = new StringBuilder(p);
answer = sol(sb).toString();
return answer;
}
static StringBuilder sol(StringBuilder p){
StringBuilder u,v;
int idx = 0;
int count = 0;
if(check(p) == true) return p;
for(idx = 0; idx<p.length(); idx++){
if(p.charAt(idx) == '(') count++;
else if(p.charAt(idx) == ')') count--;
if(count == 0) break;
}
u = new StringBuilder(p.substring(0,idx+1));
v = new StringBuilder(p.substring(idx+1));
if(check(u) == true) return u.append(sol(v));
else{
StringBuilder temp = new StringBuilder("("); //4-1
temp = temp.append(sol(v)+")");// 4-2,4-3
//4-4
u = new StringBuilder(u.substring(1,u.length()-1));
for(String str : u.toString().split("")){
if(str.equals("(") == true)
temp = temp.append(")");
else if(str.equals(")") == true)
temp = temp.append("(");
}
//4-5
return temp;
}
}
static boolean check(StringBuilder p){
int len = p.length();
int count = 0;
for(int i=0; i<p.length(); i++){
if(p.charAt(i) == '(')
count++;
else if(p.charAt(i) ==')'){
count--;
}
if(count < 0) return false;
}
return true;
}
}
- String에서 concat 대신 + 이용
class Solution {
public String solution(String p) {
String answer = "";
answer = sol(p);
return answer;
}
static String sol(String p){
String u,v;
int idx = 0;
int count = 0;
if(check(p) == true) return p;
for(idx = 0; idx<p.length(); idx++){
if(p.charAt(idx) == '(') count++;
else if(p.charAt(idx) == ')') count--;
if(count == 0) break;
}
u = p.substring(0,idx+1);
v = p.substring(idx+1);
if(check(u) == true) return u + (sol(v));
else{
String temp = "("; //4-1
temp = temp + sol(v)+ ")";// 4-2,4-3
//4-4
u = u.substring(1,u.length()-1);
for(String str : u.split("")){
if(str.equals("(") == true)
temp = temp + ")";
else if(str.equals(")") == true)
temp = temp + "(" ;
}
//4-5
return temp;
}
}
static boolean check(String p){
int len = p.length();
int count = 0;
for(int i=0; i<p.length(); i++){
if(p.charAt(i) == '(')
count++;
else if(p.charAt(i) ==')'){
count--;
}
if(count < 0) return false;
}
return true;
}
}- 결과
