백준 10799, 2805, 10816

문제 10799번 (성공, 40분 소요)

소스코드

import java.io.*;
import java.util.*;
public class boj10799 {
    public static void main(String[] args) throws IOException{
        Stack<Integer> stack = new Stack();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String ac = br.readLine();
        char[] input = ac.toCharArray();
        ArrayList<Integer> razer = new ArrayList();
        int n = 0;
        int result =0;
        while(n <input.length){
            if(input[n] == '('){
                stack.push(n);
            }else{
                if(input[n-1] == '('){
                    int a = stack.pop();
                    razer.add(a);
                }else{
                    int a = stack.pop();
                    boolean isTrue = false;
                    for (int i = 0; i < razer.size(); i++) {
                        if(razer.get(i) > a){
                            result++;
                            isTrue = true;
                        }
                    }
                    if(isTrue){
                        result++;
                    }
                }
            }
            n++;
        }
        System.out.println(result);
    }
}

풀이 접근

1. 문제에서는 VPS를 만족하는 입력만 주어진다는 사실을 기억하자
2. stack에 '('입력에는 해당 인덱스 값을 push한다
3. 만약 ')'가 입력 된다면, 전에 '('가 나왔을 경우에는 razer가 해당 됨으로 n-1 인덱스를 razer에 add한다.
   4.')'가 입력 되었지만, 3번의 경우가 아니라면 스택의 가장 위의 값을 pop하면서 값을 a에 저장한다.
4. razer를 돌면서 razer에 있는 변수가 a보다 클 경우에는 result를 증가 시키고, isTrue 변수를 true로 바꾼다.
5. isTrue가 true인 경우는 해당 막대기가 레이저에 부서졌을 때를 가리킴으로 해당 경우에는 result를 1만큼 추가로 증가한다.
6. 반복문을 String의 길이만큼 반복한다.
7. 나온 result 값을 출력시킨다.

문제 핵심

• VPS가 만족하는 입력만 주어진다는 사실을 알고 작성하는지
• 시간복잡도를 줄이는 방법으로 코딩할 수 있는지
• stack을 잘 활용할 수 있는지

문제 2805번

소스코드

import java.io.*;
import java.util.*;
public class boj2805 {
    public static long search(int[] input, int n ,int m, int a){
        int first = 0;
        int last = a;
        while(first <= last){
            int mid = (first +last) / 2;
            long result = 0;
            for (int i = 0; i < input.length; i++) {
                int b = input[i] - mid;
                if(b>0){
                    result += b;
                }
            }
            if(m <= result){
                first = mid +1;
            }else{
                last = mid -1;
            }
        }
        return last;
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int[] input = new int[n];
        int a = 0;
        for (int i = 0; i < n; i++) {
            input[i] = Integer.parseInt(st.nextToken());
            a = Math.max(a, input[i]);
        }
        System.out.println(search(input, n, m, a));
    }
}

풀이 접근

1. 탐색이 필요하고 n과 m의 범위가 넓어 시간이 많이 소요될 것 같은 문제임을 확인한다.
2. input배열을 받으면서 배열 내부의 최댓 값을 a라는 변수로 계속해서 최신화 시킨다.
3. 이분탐색을 위한 함수인 search함수를 통해 원하는 값을 출력한다.

문제 핵심

• 문제의 조건에 맞는 탐색 방법을 선택할 수 있는가

문제 10816번(실패, 시간초과)

• 풀어서 수정하겠습니다.
  

정답을 위한 참고 블로그

https://comain.tistory.com/270

소스코드 (실패한 코드입니다.)

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class boj10816 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int m = Integer.parseInt(br.readLine());
        int[] arr = new int[m];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int t = Integer.parseInt(br.readLine());
        ArrayList<Integer> arr2 = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < t; i++) {
            int a = Integer.parseInt(st.nextToken());
            // 여기서 result 값은 탐색해서 찾아낸 개수의 값이 아니다! 고치자!
            int result = Arrays.binarySearch(arr, a);
            if(result <0){
                sb.append(0 +" ");
            }else {
                sb.append(result + " ");
            }
        }
        System.out.println(sb);
    }

풀이 접근

문제 핵심