백준 18115,2798,1929

git : https://github.com/phc09188

문제18115번(시간초과)

소스코드(원본) = 시간초과

import java.io.*;
import java.util.*;
public class boj18115 {
    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());
        Stack<Integer> stack = new Stack();
        int[] x = new int[n];
        for (int i = 1; i <= n; i++) {
            x[i-1] = Integer.parseInt(st.nextToken());
            stack.add(i);
        }
        int cnt = 0;
        boolean[] a = new boolean[n];
        int[] result = new int[n];
        while(cnt<n){
            switch(x[cnt]){
                case 1:
                    int temp = stack.pop();
                    for (int i = 0; i < n; i++) {
                        if(!a[i]){
                            result[i] = temp;
                            a[i] = true;
                            break;
                        }
                    }
                    cnt++;
                    break;
                case 2:
                    if(stack.size() >=2) {
                        int temp2 = stack.pop();
                        int c = 0;
                        for (int i = 0; i < a.length; i++) {
                            if(!a[i]){
                                if(c ==1){
                                    result[i] = temp2;
                                    a[i] = true;
                                    break;
                                }else{
                                    c++;
                                }
                            }
                        }
                    }
                    cnt++;
                    break;
                case 3:
                    if(stack.size() >=2){
                        int temp3 = stack.pop();
                        for (int i = a.length-1; i >= 0; i--) {
                            if(!a[i]){
                                result[i] = temp3;
                                a[i] = true;
                                break;
                            }
                        }
                    }
                    cnt++;
                    break;
            }
        }
        for(int i : result){
            sb.append(i + " ");
        }
        System.out.println(sb);
    }
}

소스코드 (수정본)

import java.io.*;
import java.util.*;
public class boj18115 {
    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());
        int[] arr = new int[n];
        int[] result = new int[n+1];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int num = n;
        int idx1 = 0; int idx2 =1; int idx3 = n-1;
        for (int i = 0; i < n; i++) {
            if(arr[i] == 1){
                result[idx1] = num;
                if(result[idx1+1] == 0) idx1 +=1;
                else idx1 = idx2+1;
            }else if(arr[i] == 2){
                if(result[idx1+1] == 0) idx2 = idx1+1;
                else idx2 +=1;
                result[idx2] = num;
            }else if(arr[i] == 3){
                result[idx3] = num;
                idx3 -= 1;
            }
            num--;
        }
        for (int i = 0; i < n; i++) {
            sb.append(result[i] + " ");
        }
        System.out.println(sb);
    }
}

풀이 접근

• 1. 입력 받은 n개를 길이로 가지고 있는 int배열과 boolean배열을 만든다.
     5부터 하나씩 stack에서 꺼내와서 case에 따라 pop한 값을 문제의 조건에 맞춰 넣는다.
     이 때, 결과 배열에 넣으면서, 해당 배열의 boolean값을 true로 바꿔준다.
     결과를 출력한다. == 시간초과
• 2. 입력받은 n개를 길이로 가지고 있는 int형 배열 2가지를 만들고 첫 번째에는 방법을, 두 번째에는 빈 결과 배열을 만든다.
     idx1은 시작부분 idx3는 끝부분 idx2 는 2번째 자리 수를 의미한다.
     해당 반복문을 돌면서 배열을 통해서 결과를 result 배열에 저장한다.

문제핵심

• 배열에 비해서 stack이나 queue같은 자료구조는 시간이 많이 걸린다.

문제 1929번 (시간초과)

소스코드(원본)

import java.io.*;
        import java.util.*;
public class boj1929 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        boolean[] isTrue = new boolean[m+1];
        for (int i = n; i < m; i++) {
            if(i<2){
                return;
            }
            isTrue[0] = isTrue[1] = true;
            for (int j = 2; j <= Math.sqrt(m); j++) {
                if(isTrue[j] == true){
                    continue;
                }
                for (int k = j*j; k < isTrue.length; k = k +j) {
                    isTrue[k] = true;
                }
            }
        }
        for (int i = n; i < isTrue.length; i++) {
            if(isTrue[i] == false){
                System.out.println(i);
            }
        }
    }
}

소스코드(수정본)

import java.io.*;
import java.util.*;
public class boj1929 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        boolean[] isTrue = new boolean[m+1];
        for (int i = 2; i <= m; i++) {
            if(isTrue[i]) continue;
            if(i>=n) sb.append(i + "\n");
            for (int j = i+i; j <= m; j +=i) {
                isTrue[j] = true;
            }
        }
        System.out.println(sb);
    }
}

풀이 접근

• 1. 에라토스테네스의 채 방식을 사용해서 소수가 아닌 숫자를 true로 바꾸고 입력에서 주어진 범위에서 false인 값만 프린트한다.
• 2. 1번에서 풀었던 접근법과 같은 접근이지만 좀 더 간결하고 시간을 줄이기 위해서 하나의 반복문으로 에라토스테네스의 채 방식을 만들었다.
     참고 : 소수 구하는 알고리즘

문제핵심

• 소수를 구하는 다양한 알고리즘 중에 시간복잡도를 줄일 수 있는 알고리즘을 사용했는가

문제 2798번 (성공)

소스코드

import java.io.*;
import java.util.*;
public class boj2798 {
    static int max = -1;
    static int limit =0;
    public static void combination(int[] arr, boolean[] visited, int depth, int n, int r){
        if(r == 0){
            int sum = 0;
            for (int i = 0; i < n; i++) {
                if (visited[i]) {
                    sum += arr[i];
                }
            }
            if(sum > max && sum <= limit){
                max = sum;
            }
            return;
        }
        if(depth ==n){
            return;
        }
        visited[depth] = true;
        combination(arr, visited, depth+1, n, r-1);
        visited[depth] = false;
        combination(arr, visited, depth+1, n, r);
    }
    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());
        limit = m;
        int[] arr = new int[n];
        boolean[] visited = new boolean[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        combination(arr,visited,0,n,3);
        System.out.println(max);
    }
}

풀이접근

1. 문제에서 이야기하는 부분은 nC3을 구하라는 뜻으로 판단한다.
2. combination함수를 구현하면서, 경우의 수 마다 합을 구한다.
3. 합한 값이 limit를 넘어가지 않는 선에서 최댓값을 구한다.
4. 해당 값을 출력한다.

문제핵심

• Combination함수를 구현 할 수 있는가
• 전역변수 사용법을 알고 있는가