10815번 (이진 탐색), 1874번 (스택), 11650번 (정렬)

10815번

 

인텔리제이에서는 잘 돌아갔는데 시간 초과 떠서 틀렸다ㅎ... 

찾아보니까 이진 탐색 사용해야 한다고 함

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Practice {
    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());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        List<Integer> list1 = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list1.add (Integer.parseInt(st.nextToken()));
        }
        int m = Integer.parseInt(br.readLine());
        List<Integer> list2 = new ArrayList<>();
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < m; i++) {
            list2.add(Integer.parseInt(st.nextToken()));
        }
        List<Integer> list = new ArrayList<>();
        for(int i : list2) {
            if(list1.contains(i)) {
                list.add(1);
            } else {
                list.add(0);
            }
        }
        for (int i : list) {
            sb.append(i).append(" ");
        }
        System.out.println(sb);
    }
}

 

이진 탐색 트리  (중복된 값 허용 X)

 

각 요소가 나무처럼 연결된 구조

범위 검색과 정렬에 유리하지만 데이터 삭제나 추가에 시간이 많이 걸린다

어떤 데이터를 찾더라도 최대 트리 높이 만큼의 탐색이 이루어진다

이진 트리는 모든 노드가 최대 두 개의 하위 노드를 가짐 (부모-자식 관계)

부모보다 작은 값을 왼쪽에, 큰 값은 오른쪽에 저장

이진 탐색은 정렬된 배열 또는 리스트에 적합한 고속 탐색 방법

배열의 중앙에 위치한 값을 조사하여 찾고자 하는 값이 왼쪽 또는 오른쪽 부분 배열에 있는지 알아내어 탐색의 범위를 반으로 줄인다. 찾고자 하는 값이 속해있지 않은 부분은 전혀 고려할 필요가 없어 속도가 빠름

 

어려워서 이해를 위해 만든 이진 탐색 로직 정리......

이진 탐색을 사용하기 전에 배열을 오름차순으로 정리해야 한다

이진 탐색을 위한 static 메서드를 선언

만약 이진 탐색을 진행했음에도 찾고자 하는 key 값이 나오지 않는다면 binarySearch 메서드는 -1를 반환

조건문을 사용하여 binarySearch가 -1을 반환하였다면 0을 출력하고 그 외에는 1을 출력하도록 함

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Practice {
    static int [] arr;
    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());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        arr= new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] =  (Integer.parseInt(st.nextToken()));
        }
        Arrays.sort(arr);
        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < m; i++) {
            int result = binarySearch(Integer.parseInt(st.nextToken()));
            if(result == -1) {
                sb.append(0).append(" ");
            } else {
                sb.append(1).append(" ");
            }
        }
        System.out.println(sb);
    }
    public static int binarySearch (int key) {
        int left = 0;
        int mid;
        int right = arr.length-1;
        while (left<=right) {
            mid = (left+right) / 2;
            if(key==arr[mid]) {
                return mid;
            } else if (key>arr[mid]) {
                left = mid+1;
            } else if (key<arr[mid]) {
                right = mid-1;
            }
        }
        return -1;
    }
}

 

Arrays.binarySeach() 메서드를 사용하면 더 빠르게 할 수 있다고 한다

Arrays.binarySearch(이진탐색을 당할 배열, 찾는 값);

찾는 값이 있으면 해당 인덱스(양의 정수)를 반환, 없으면 음수를 반환

>  조건문을 사용하여 0보다 작으면 0 출력, 그외에는 1 출력

 

1874 너무너무 어렵다...... 

 

 

스택은 마지막에 저장된 것을 제일 먼저 꺼내는 구조

 

<메서드>

 

empty() - 해당 스택이 비어 있으면 true를, 비어 있지 않으면 false를 반환함.

push()- 해당 스택의 제일 상단에 전달된 객체를 삽입

pop()- 맨 위에 저장된 객체를 반환 후 해당 객체를 스택에서 제거

peak()- 맨 위에 저장된 객체 반환(꺼내지 X)

search()- 해당 스택에서 전달된 객체가 존재하는 위치의 인덱스를 반환, 인덱스는 제일 상단에 있는(제일 마지막으로 저장된) 요소의 위치부터 0이 아닌 1부터 시작

 

 

4를 입력 받았다면 스택에 push하는 순서는 반드시 오름차순을 지켜야 하므로 스택에는 1, 2, 3, 4가 모두 push 되어야 함

 

만약 push된 숫자들을 pop을 통해 빼내면서 수열을 만든다면 스택에 쌓여 있는 것을 먼저 빼내야만 하므로 그림의 두 번째 줄 같이 스택에 4와 3만이 남아있는데 3을 먼저 빼내서 수열을 만들고자 한다면 이는 불가능하다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Practice {
    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());
        Stack<Integer> stack = new Stack<>();
        int first = 0;
        for(int i  = 0; i<n; i++) {
            int m = Integer.parseInt(br.readLine());
            if(m>first) {
                for(int j = first+1; j<=m; j++) {
                    stack.push(j);
                    sb.append("+"+"\n");
                }
                first = m;
            }
            else if(stack.peek()!=m && !stack.empty()) {
                System.out.println("NO");
                return; // 반복문을 포함하는 main 메서드 자체를 종료하고 밑의 코드를 실행하지 않음
            }
            stack.pop();
            sb.append("-"+"\n");
        }
        System.out.println(sb);
    }
}

11650번

 

comparator를 구현하는 문제이다

조건문을 통해 x 좌표가 같은 값을 가진다면 y좌표를 오름차순으로 정렬하고 그 외에는 x좌표를 오름차순으로 정렬

편의를 위해 좌표에 대한 클래스를 만들어 진행

list에 좌표 객체가 들어가도록 한다

좌표 클래스에서 String 클래스의 toString()을 오버라이딩하여 문제에 제시된 출력 모습과 같아지도록 한다

public class Practice {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int num = Integer.parseInt(br.readLine());
        List<Coordinate> list = new ArrayList<>();
        for (int i = 0; i < num; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            list.add(new Coordinate(x, y));
        }
        Collections.sort(list, new Comparator<Coordinate>() {
            @Override
            public int compare(Coordinate c1, Coordinate c2) {
                if (c1.getX() == c2.getX()) {
                    return c1.getY() - c2.getY(); // y좌표 오름차순
                } else {
                    return c1.getX() - c2.getX(); // x좌표 오름차순
                }
            }
        });
        for (Coordinate c : list) {
            sb.append(c).append("\n");
        }
        System.out.println(sb);
    }
}

class Coordinate {
    int x;
    int y;

    Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    @Override
    public String toString() {
        return x + " " + y;
    }
}