백준 1541번 잃어버린 괄호

문제

나의 풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        ArrayList<Integer> num = new ArrayList<>();
        ArrayList<Integer> sign = new ArrayList<>();
        boolean minus = false;
        int cur = 0;
        sign.add(1); // 가장 앞의 숫자는 +로 생각
        for(char x : s.toCharArray()) {
            if(x == '+' || x == '-') { // 연산자인 경우
                if(x == '+') { // 더하기인 경우
                    sign.add(1);
                } else { // 빼기인 경우
                    sign.add(-1);
                }
                num.add(cur); 
                cur = 0;
            } else {
                cur = cur * 10 + (x - '0');
            }
        }
        num.add(cur);
        
        int answer = 0;
        minus = false;
        for(int i = 0; i < num.size(); i++) {
            if(sign.get(i) == -1) {
                minus = true;
            }
            if(minus) {
                answer -= num.get(i);
            } else {
                answer += num.get(i);
            }
        }
        System.out.println(answer);
    }
}

최소가 되게 하기 위해선 -를 발견하면 그 뒤에 +가 있는 식들을 괄호로 묶으면 모두 -로 만들 수 있다. 해당 성질을 이용하여 해결해주면 된다.

결과

백준 1744번 수 묶기

문제

나의 풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ArrayList<Integer> plus = new ArrayList<>();
        ArrayList<Integer> minus = new ArrayList<>();
        int zero = 0;
        int one = 0;
        for(int i = 0; i < n; i++) {
            int x = sc.nextInt();
            if(x == 1) {
                one += 1;
            } else if(x > 0) {
                plus.add(x);
            } else if(x < 0) {
                minus.add(x);
            } else {
                zero += 1;
            }
        }
        Collections.sort(plus);
        Collections.sort(minus); // 오름차순 정렬
        Collections.reverse(plus); // 내림차순 정렬
        if(plus.size() % 2 == 1) { // 양수 짝이 맞지 않는 경우
            plus.add(1); // 1 추가해주기 (변함 없도록)
        } 
        if(minus.size() % 2 == 1) { // 음수 짝이 맞지 않는 경우
            minus.add(zero > 0 ? 0 : 1); // 0이 있으면 0 추가, 없으면 1 추가
        }
        
        int answer = one; // 1의 개수로 초기화
        for(int i = 0; i < plus.size(); i += 2) {
            answer += plus.get(i) * plus.get(i + 1);
        }
        for(int i = 0; i < minus.size(); i += 2) {
            answer += minus.get(i) * minus.get(i + 1);
        }
        System.out.println(answer);
    }
}

양수는 큰수끼리 음수는 작은수끼리 1은 묶지 않는 것이 최대가 된다.
묶이지 않는 음수가 있는 경우 0과 묶게 하면 된다.

결과

인프런 최대길이 바이토닉 수열

문제

나의 풀이

import java.util.ArrayList;

public class BitonicSequence {
    static public int solution(int[] nums) {
        int answer = 0;
        int n = nums.length;
        ArrayList<Integer> peaks = new ArrayList<>(); // 봉우리 지점 저장
        for(int i = 1; i < n - 1; i ++) {
            if(nums[i - 1] < nums[i] && nums[i] > nums[i + 1]) { // 봉우리 찾기
                peaks.add(i);
            }
        }
        for(int x : peaks) {
            int left = x;
            int right = x;
            int count = 1; // 길이
            while(left - 1 >= 0 && nums[left - 1] < nums[left]) { // 감소하는 부분일 때 까지 (왼쪽)
                left--;
                count++; // 길이 증가
            }
            while(right + 1 < n && nums[right] > nums[right + 1]) { // 감소하는 부분일 때 가지 (오른쪽)
                right++;
                count++; // 길이 증가
            }
            answer = Math.max(answer, count); // 최장 길이 찾기
        }
        return answer;
    }

    public static void main(String[] args) {
        System.out.println(BitonicSequence.solution(new int[]{1, 3, 2, 5, 7, 4, 2, 5, 1}));
        System.out.println(BitonicSequence.solution(new int[]{1, 1, 2, 3, 5, 7, 4, 3, 1, 2}));
        System.out.println(BitonicSequence.solution(new int[]{3, 2, 1, 3, 2, 4, 6, 7, 3, 1}));
        System.out.println(BitonicSequence.solution(new int[]{1, 3, 1, 2, 1, 5, 3, 2, 1, 1}));
    }
}

먼저, 봉우리 지점이 될 수 있는 인덱스를 찾아서 배열에 넣어준다. 봉우리 지점이 될 수 있는 조건은 바로 앞과 뒤의 수보다 커야한다.
그런 다음 봉우리 지점에 대해서 앞으로 가면서 감소할 때 까지 반복하는 while문 하나와 뒤로 가면서 감소할 때 까지 반복하는 while문 하나를 돌게 하여 이들의 길이를 구하게 한다.
그런 다음 가장 긴 길이를 정답으로 출력시키게 하면 된다.

결과