백준(10815, 1874, 11650)

문제 11650번 (실패)

풀이 접근

1. 2차원 배열을 통해서 x와 y 좌표를 입력 받음
2. Arrays.sort함수에 Comparator interface를 추가하여 조건에 맞게 정렬
3. 출력

소스코드

import java.io.*;
import java.util.*;
public class boj11650 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][2];
        StringTokenizer st;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr, new Comparator<int[]>(){
            public int compare(int[] o1, int []o2){
                if(o1[0] == o2[0])
                    return Integer.compare(o1[1], o2[1]);
                    return Integer.compare(o1[0],o2[0]);
            }
        });
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i][0] + " " + arr[i][1]);
        }
    }
}

문제의 핵심

• Comparator를 사용할 줄 아는가
• Overide가 잘 되었는가

문제 1874번 (실패)

풀이 접근

1. stack의 구조를 이해한다.
2. 스택은 오름차순으로 push 되어야하며 한 번 들어갔던 숫자는 다시 들어갈 수 없다.
3. 스택을 통해 배열을 만들 수 없는 경우 예외처리를 한다.
4. 예외처리 대상이 아닐 경우 출력한다.

소스코드

import java.io.*;
import java.util.Stack;
public class boj1874 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        Stack<Integer> stack = new Stack<>();
        int n = Integer.parseInt(br.readLine());
        int start = 0;
        boolean isTrue = true;
        int[] input = new int[n];
        for (int i = 0; i < n; i++) {
            input[i] = Integer.parseInt(br.readLine());
        }
        for (int i = 0; i < n; i++) {
            if(input[i] > start){
                for (int j = start+1; j <= input[i]; j++) {
                    stack.push(j);
                    sb.append("+" + "\n");
                }
                start = input[i];
            }else if(stack.peek() != input[i]){
                System.out.println("NO");
                isTrue = false;
                break;
            }
            stack.pop();
            sb.append("-" + "\n");
        }
        if(isTrue) {
            System.out.println(sb);
        }
    }
}

문제의 핵심

* 스택 자료구조를 제대로 이해하고 있는가 (LIFO)

문제 10815번 (성공)

풀이 접근

1. 상근이의 카드에 대한 배열을 만든다.
2. 이분탐색을 위해 상근이의 카드 배열을 오름차순으로 정렬한다.
3. 이분탐색을 통해 비교할 카드들을 비교한다.
4. 결과를 StringBuilder로 출력한다.

소스코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class boj10815 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        String input = br.readLine();
        StringTokenizer st = new StringTokenizer(input);
        int[] firstarr = new int[n];
        for (int i = 0; i < n; i++) {
            firstarr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(firstarr);
        int m = Integer.parseInt(br.readLine());
        input = br.readLine();
        st = new StringTokenizer(input);
        for (int i = 0; i < m; i++) {
            int a = Integer.parseInt(st.nextToken());
            sb.append(binarySearch(firstarr, n, a) + " ");
        }
        System.out.println(sb);
    }
    private static int binarySearch(int[] firstarr, int n, int a) {
        int first = 0;
        int last = n -1;
        int mid = 0;
        while(first<= last){
            mid = (first + last)/2;
            if(firstarr[mid] ==a){
                return 1;
            }
            if(firstarr[mid] <a){
                first = mid +1;
            }else{
                last = mid -1;
            }
        }
        return 0;
    }
}

문제 핵심

• 시간복잡도를 줄였는가
• 이분탐색을 구현할 수 있는가