백준 1541번
https://www.acmicpc.net/problem/1541
세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.
그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.
첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.
첫째 줄에 정답을 출력한다.
55-50+40
-35
문제만 봤을 때는 별로 어렵지 않은 문제같은데, 구현해보면 진짜 까다로운 부분이 많았습니다.
테스트케이스는 4개 정도를 썼는데, 기본으로 제공하는 테스트케이스 3개와
01+0-1
까지 4개의 테스트케이스를 사용하면 문제를 완벽하게 풀 수 있다고 생각합니다.
문제를 풀고나서 Greedy알고리즘인걸 알게됬는데, 다른 분들의 코드를 참고해서 다시 풀어봐야겠습니다.
String zero = "+";
// 처음 시작하는 부호가 -가 아닐경우 (양수일 경우)
// +를 앞에 붙여줌
if( !formula.startsWith("-")) {
zero += formula;
formula = zero;
}
들어오는 테스트케이스를 먼저 formula
변수에 저장한 뒤
시작하는 문자열이 -가 아닐 경우, 즉 처음 시작이 양수로 시작할 경우
formula
에 +기호를 붙여줍니다. 양수임을 판별하기 위해서 쓰입니다
int length = formula.length();
boolean open = false;
for(int i=0; i<length; i++) {
char ch = formula.charAt(i);
if(ch == '-' && open == false) {
open = !open;
list.add(ch + "(+");
}
// + 기호 인데, 괄호가 열려있음을 의미
else if(ch == '+' && open == true) {
list.add(String.valueOf(ch));
}
else if(ch == '-' && open == true) {
list.add(")" + ch + "(+");
}
else {
list.add(String.valueOf(ch));
}
// 마지막줄에 괄호가 열려있을 경우
if( i == length-1 && open == true) {
list.add(")");
}
}
먼저 설명에 앞서 가장위에 List<String>
를 생성해뒀습니다.
이유는 식을 수정할건데, 수정할 식의 길이가 어떻게 될지 모르기 때문에 동적할당을 위해서 list
를 만들었습니다. 이 list
에 새로운 식을 넣을겁니다.
식의 길이 만큼 반복하기 위해 length
변수를 만듭니다.
여기서 for문 안에 formula.length()
를 직접 넣으면 되는데, 왜 굳이length
변수를 만들어서 쓰시냐고 궁금하실수도 있는데, for문안에 length함수를 넣게되면,
for문이 반복되는 동안 i
값과 비교하기 위해서 계속해서 formula.length()를 호출하게됩니다. 반복이 적으면 상관없지만, 많은 양의 반복에서는 굉장히 비효율적이기때문에 for문안에서 length함수를 사용하는 것은 추천하지 않습니다.
open
은 괄호가 현재 열려있는지 닫혀있는지를 판단하기 위한 변수입니다.
기본값은 괄호가 현재 열려있지 않다로 false 입니다.
이제 ch
는 formula의 한글자씩 잘라서 if문으로 집어 넣습니다.
if(ch == '-' && open == false)
는 -인데 괄호가 열려있지 않은 경우 입니다.
이 경우는 -부호끼리 묶어서 +로 만들어주면 되기 때문에 "-(+" 를 list
에 넣어줍니다.
이렇게 하면 -(+40+30 의 모양으로 식을 만들수 있습니다. -가 시작되면서 괄호로 묶습니다.
else if(ch == '+' && open == true)
는 +인데 괄호가 열려있는 경우입니다.
이 경우는 괄호를 닫지 않고 그대로 list
에 집어 넣습니다. 최소값을 만들기 위한 괄호의 범위에 들어갑니다.
else if(ch == '-' && open == true)
는 -인데 괄호가 열려있는 경우입니다.
이제 다음 -가 나왔기 때문에 괄호를 닫아준후 다시 괄호를 열고 +를 붙여줘야 합니다.
즉, 중간에 -가 있을 경우 입니다.
예를 들면 -40 + 30 - 20 같은 경우 입니다. 이 식은 -(+40+30)-(+20)으로 바뀝니다.
그 외의 경우 else
는 식이 유지되기 위해서 그대로 list
에 넣어줍니다. list
가 String형 이기때문에 char형을 집어넣기 위해서는 String.valueOf()함수를 써서 넣어줘야 합니다.
가장 마지막줄인 if( i == length-1 && open == true)
은 마지막에 괄호가 열려있을 때, 괄호를 닫아주기 위한 조건문입니다.
formula = "";
for(String str : list) {
formula += str;
}
이렇게 해서 list
에 들어있는 식을 다시 formula
문자열로 넣습니다.
처음 식이 55-50+40 일 경우 수정하면 +55-(50+40) 형식으로 바뀝니다.
StringTokenizer st = new StringTokenizer(formula, "-");
int minus_sum = 0;
int plus_sum = 0;
while(st.hasMoreElements()) {
String temp = st.nextToken();
if( temp.contains("(")) {
temp = temp.replace("(", "");
temp = temp.replace(")", "");
StringTokenizer plus_token = new StringTokenizer(temp, "+");
while(plus_token.hasMoreElements()) {
minus_sum -= Integer.parseInt(plus_token.nextToken());
}
}
else if ( temp.contains("+")){
StringTokenizer plus_token = new StringTokenizer(temp, "+");
while(plus_token.hasMoreElements()) {
plus_sum += Integer.parseInt(plus_token.nextToken());
}
}
}
System.out.println(minus_sum + plus_sum);
음수의 합을 저장할 minus_sum
과 양수의 합을 계산할 plus_sum
을 만들어줍니다.
StringTokenizer st = new StringTokenizer(formula, "-");
수정된 식인 formula
가 +30-(+70)-(+20+40)-(+10+100+30)-(+35) 일 경우
일단 전체를 -를 토큰으로 나눕니다.
반복하여 분리된 토큰을 저장한temp
들은 아래와 같습니다.
temp
: +30
temp
: (+70)
temp
: (+20+40)
temp
: (+10+100+30)
temp
: (+35)
의 temp
값들을 가질 수 있습니다.
이제 여기서 알 수 있는 점은 "("가 있는 것들은 모두 음수값이 될 거라는 점이고"("가 없는 것은 그냥 양수 값이 된다는 것입니다.
그래서 temp
에 contain함수를 이용해 있는지 검사하여 true일 경우 "("가 있다로 판단합니다.
여기서 중요한 점은 if문의 순서도 중요합니다. 공통적으로 모두 +기호는 있지만, "("는 음수에만 해당하기 때문에 조건문인 if( temp.contains("("))
을 먼저 주어야합니다.
이제 음수의 합을 계산하기 위해서 "(" 와 ")"를 replace함수를 통해서 제거해줍니다.
이후에 남은 +기호를 다시 토큰값으로 지정해서 정수로 끊어준 후 plus_token
을 전체 순환하며 minus_sum
에 모두 합해줍니다.
StringTokenizer plus_token = new StringTokenizer(temp, "+");
while(plus_token.hasMoreElements()) {
minus_sum -= Integer.parseInt(plus_token.nextToken());
}
그 다음 else if ( temp.contains("+")){
오로지 + 기호만 있을 경우 입니다.
이 값은 모두 양수라는 의미이기 때문에 위 처럼 +기호를 토큰으로 해서 plus_sum
합을 구해줍니다.
이렇게 하면 음수의 합과 양수의 합을 구분지어서 구할 수 있습니다.
이제 결과 값은 minus_plus
와 plus_sum
을 빼주기만 하면 결과값이 됩니다.
이 문제는 생각할 부분이 적어서 다행입니다. - + ( ) 이 4가지의 경우만 생각하면 되서 이정도로 구현에 성공한 것 같습니다.
더 다양한 문자열의 경우가 있었다면, 실패할 수 있었다고 생각하기 때문에 다른 분들의 코드를 참고해서 학습이 필요할 것 같습니다.
솔직히 진짜 못 만든 코드이지만, 내가 생각한대로 구현에 성공했다는 데 의미가 있어서 기분이 좋습니다.
문자열 진짜 꼭 쉬운 문제 같은데 구현이 참 어려워
마치 길에서 아는사람을 마주쳤는데, 아 쟤 누구더라.. 하는 기분이랄까..
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); List<String> list = new ArrayList<>(); String formula = br.readLine(); String zero = "+"; // 처음 시작하는 부호가 -일 경우 (음수일 경우) if( !formula.startsWith("-")) { zero += formula; formula = zero; } int length = formula.length(); boolean open = false; for(int i=0; i<length; i++) { char ch = formula.charAt(i); if(ch == '-' && open == false) { open = !open; list.add(ch + "(+"); } // + 기호 인데, 괄호가 열려있음을 의미 else if(ch == '+' && open == true) { list.add(String.valueOf(ch)); } else if(ch == '-' && open == true) { list.add(")" + ch + "(+"); } else { list.add(String.valueOf(ch)); } // 마지막줄에 괄호가 열려있을 경우 if( i == length-1 && open == true) { list.add(")"); } } formula = ""; for(String str : list) { formula += str; } StringTokenizer st = new StringTokenizer(formula, "-"); int minus_sum = 0; int plus_sum = 0; while(st.hasMoreElements()) { String temp = st.nextToken(); if( temp.contains("(")) { temp = temp.replace("(", ""); temp = temp.replace(")", ""); StringTokenizer plus_token = new StringTokenizer(temp, "+"); while(plus_token.hasMoreElements()) { minus_sum -= Integer.parseInt(plus_token.nextToken()); } } else if ( temp.contains("+")){ StringTokenizer plus_token = new StringTokenizer(temp, "+"); while(plus_token.hasMoreElements()) { plus_sum += Integer.parseInt(plus_token.nextToken()); } } } System.out.println(minus_sum + plus_sum); } // End of main } // End of class