[do it 알고리즘] 백준 1541 (그리디2)

문제 설명

 

풀기 전 생각

• 한 줄로 받은 수식을 각각 숫자 배열, 기호 배열에 나눠 저장
• 가장 처음은 양수인 숫자이므로 sum = 숫자 배열[0]로 초기화
• 기호 배열을 기준으로 반복문을 돌기 ( 기호 배열의 Index + 1 = 숫자 배열의 Index )
• '-'가 나오면 그다음 '-'가 나올 때까지 계속 빼주기
• 이외 '+'가 나오면 더해주기

코드

import java.util.*;
public class Baek1541 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String express = sc.next();
        String[] strArr = express.split("\\+|-");
        char[] charArr = express.replaceAll("[0-9]", "").toCharArray();
        int sum = Integer.parseInt(strArr[0]);
        boolean flag = true;

        for(int i = 0; i < charArr.length;i++){
            if(charArr[i] == '-' && flag == true){
                flag = false;
                sum -= Integer.parseInt(strArr[i+1]);
            }else if(charArr[i] == '+' && flag == false){
                sum -= Integer.parseInt(strArr[i+1]);
            }else if(charArr[i] == '-' && flag == false){
                flag = true;
                sum -= Integer.parseInt(strArr[i+1]);
            }else{
                sum += Integer.parseInt(strArr[i+1]);
            }
        }

        System.out.println(sum);
    }
}

오류 및 개선

• 예제는 다 통과했지만 실패
• 반례
  테스트케이스: 1-2-3+4
  결괏값: 0
  기댓값: -8
• '-'가 나오면 빼주기
• '-'가 나온 후  '+'가 나오면 빼주기
• 나머지 상황은 더해주기

최종 코드

import java.util.*;
public class Baek1541 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String express = sc.next();
        String[] nums = express.split("\\+|-");
        char[] symbols = express.replaceAll("[0-9]", "").toCharArray();
        int sum = Integer.parseInt(nums[0]);
        boolean flag = true;

        for(int i = 0; i < symbols.length;i++){
            if(symbols[i] == '-'){
                flag = false;
                sum -= Integer.parseInt(nums[i+1]);
            }else if(symbols[i] == '+' && flag == false){
                sum -= Integer.parseInt(nums[i+1]);
            }else{
                sum += Integer.parseInt(nums[i+1]);
            }
        }
        System.out.println(sum);
    }
}

강의 분석 

• 가장 작은 최솟값을 만들기 위해선 가능한 한 큰 수를 빼기
• '+' 해당하는 부분을 괄호 쳐서 먼저 계산한 후 빼기 

강의 코드

import java.util.Scanner;

public class Main{
    static int answer = 0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String express = sc.nextLine();
        String[] str = express.split("-"); // -를 기준으로 나누기
        for(int i = 0; i < str.length; i++) {
            int temp = mySum(str[i]); // 도형안에 숫자의 합 구하는 함수
            if(i==0)answer += temp; // 첫번째이면 양수이므로 더해주기
            else answer -= temp; // 나머지는 빼주기
        }
        System.out.println(answer);
    }
    public static int mySum(String express){ // 도형안에 숫자의 합 구하는 함수
        int sum = 0;
        String[] str = express.split("\\+"); // +로 나누기
        for(int i = 0; i < str.length; i++){ // 더해주기
            sum += Integer.parseInt(str[i]);
        }
        return sum;
    }
}