[백준 1436/10815/11054/16139/16928] 자바

(title: [백준 1436/10815/11054/16139/16928] 자바)

A. 영화감독  BOJ 1436

https://www.acmicpc.net/problem/1436

1436번: 영화감독 숌

난이도	Silver 5
풀이 시간	10 분
분류	구현
시간복잡도	O(N)
공간복잡도	.

import java.io.*;
import java.util.StringTokenizer;


public class Main {

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk;

        int n = Integer.parseInt(br.readLine());

        int cnt = 0; long ans = 1; String answer = "";
        while(cnt!=n){
            String str = String.valueOf(ans);
            if(str.contains("666")){
                cnt++;
                answer = str;
            }
            ans++;
        }
        bw.write(answer+"\n");

        bw.flush();
        bw.close();
    }

}

 

 

 

B. 숫자카드 BOJ 10815

https://www.acmicpc.net/problem/10815

10815번: 숫자 카드

난이도	Silver 5
풀이 시간	5분
분류	Binary Search
시간복잡도	O(nlogn)
공간복잡도	O(n)

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main {

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk;

        int n = Integer.parseInt(br.readLine());
        int[] card = new int[n];
        stk = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            card[i] = Integer.parseInt(stk.nextToken());
        }
        Arrays.sort(card);
        int m = Integer.parseInt(br.readLine());
        stk = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < m ; i++){
            int target= Integer.parseInt(stk.nextToken());
            if(binary_search(card, target)!=-1)
                bw.write("1 ");
            else bw.write("0 ");
        }
        bw.flush();
        bw.close();
    }

    private static int binary_search(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        int mid = 0;
        int midVal = 0;
        while (left <= right) {
            mid = (left + right) / 2;
            midVal = arr[mid];
            if(midVal < target){
                left = mid+1;
            } else if(midVal > target){
                right = mid-1;
            } else { // midVal == target
                return mid;
            }
        }
        return -1;
    }
}

 

 

 

C. 가장 긴 바이토닉 부분 수열 BOJ 11054

https://www.acmicpc.net/problem/11054

11054번: 가장 긴 바이토닉 부분 수열

난이도	Gold 4
풀이 시간	1시간
분류	DP, LIS
시간복잡도	O(N^2)
공간복잡도	O(1000*2)

import java.io.*;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main {

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk;

        int n = Integer.parseInt(br.readLine()); // 수열의 크기가 주어진다.
        int[] arr = new int[n+1];
        int[] dp = new int[n+1];
        for (int i = 0; i <= n; i++) {
            dp[i] = 1;
        }
        stk = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(stk.nextToken());
        }

        int max = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                if (arr[j] < arr[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        int[] revdp = new int[n+1];
        for (int i = 0; i <= n; i++) {
            revdp[i] = 1;
        }

        max = 0;
        for (int i = n; i >= 0; i--) {
            for (int j = n; j > i; j--) {
                if (arr[j] < arr[i]) {
                    revdp[i] = Math.max(revdp[i], revdp[j] + 1);
                }
            }
        }

        int ans = 0;
        for(int i = 1; i<=n; i++){
            ans = Math.max(ans, dp[i]+revdp[i]);
        }

        bw.write((ans-1)+"\n");
        bw.flush();
        bw.close();
    }

}

 

D. 인간-컴퓨터 상호작용 BOJ 16139

https://www.acmicpc.net/problem/16139

16139번: 인간-컴퓨터 상호작용

난이도	Silver 1
풀이 시간	30 분
분류	누적합
시간복잡도	O(N*26)  ~= O(N)
공간복잡도	O(26*200001)

import java.io.*;
import java.util.StringTokenizer;


public class Main {

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk;

        String input = br.readLine();
        int [][] dp = new int[26][200001];
        int [][] arr = new int[26][200001];
        for(int i = 0 ; i < input.length(); i++){
            int idx = input.charAt(i)-'a';
            arr[idx][i]++;
        }

        for(int i = 0; i<26; i++){
            dp[i][0] = arr[i][0];
            for(int j = 1; j<=input.length(); j++){
                dp[i][j] = dp[i][j-1] + arr[i][j-1];
            }
        }

        int q = Integer.parseInt(br.readLine());
        while(q>0){
            q--;
            stk = new StringTokenizer(br.readLine());
            String st = stk.nextToken();

            int idx = st.charAt(0)-'a';
            int left = Integer.parseInt(stk.nextToken());
            int right = Integer.parseInt(stk.nextToken());
            int sum = dp[idx][right+1] - dp[idx][left];
            bw.write(sum+"\n");
        }

        bw.flush();
        bw.close();
    }

}

 

E. 뱀과 사다리 게임 BOJ 16928

https://www.acmicpc.net/problem/16928

난이도	Gold 5
풀이 시간	50분
분류	그래프 탐색(DFS/BFS)
시간복잡도	O(V+E=200)
공간복잡도	.

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {
    static int[] info;
    static int[] dist;

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk;

        info = new int[101];
        dist = new int[101];

        stk = new StringTokenizer(br.readLine());
        int ladder = Integer.parseInt(stk.nextToken());
        int snake = Integer.parseInt(stk.nextToken());

        for (int i = 0; i < ladder + snake; i++) {
            stk = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(stk.nextToken());
            int end = Integer.parseInt(stk.nextToken());
            info[start] = end;
        }

        Queue<Node> q = new LinkedList<>();

        q.add(new Node(1, 0));
        while (!q.isEmpty()) {
            Node now_node = q.poll();
            int pos = now_node.pos;
            int cnt = now_node.cnt;

            for (int i = 1; i <= 6; i++) {
                int next_pos = pos+i;
                if(next_pos==100){
                    // 도착지점에 도달한 경우
                    System.out.println(cnt+1);
                    return;
                } else if(next_pos<100){
                    while(info[next_pos]!=0){
                        // 연결된 지점을 탐색
                        // 있으면 거기로 이동
                        next_pos = info[next_pos];
                    }
                    if(dist[next_pos]==0){ // 처음 방문한 곳이면
                        q.add(new Node(next_pos, cnt+1));
                        dist[next_pos] = 1; // 방문
                    }
                }
            }
        }
//        bw.flush();
//        bw.close();
    }

    static class Node {
        int pos;
        int cnt;

        public Node(int pos, int cnt) {
            this.pos = pos;
            this.cnt = cnt;
        }
    }
}