[2021.01.13] 모각코 3회 - Brute-Force

1. 학습 목표

- 큐와 스택에 대해 알아보기2 + 백준 이런 저런 문제들 풀기

 

2. 후기

- 이전에는 풀지 못하고 틀렸던 문제들을 다시 풀어보았다.

두 문제는 해결했지만 한 문제는 48%에서 시간초과가 계속 발생했다.

다른 방법으로 접근해서 시간을 더 줄여봐야겠다.

 

3. 학습 내용

- <백준 6588 JAVA> 골드바흐의 추측

import java.io.*;

public class Main {
	
	static boolean isPrimeNumber(int x) {
        if(x == 1) {
            return false;
        }
        for(int i=2; i*i<=x; i++) {
            if(x % i == 0) {
                return false;
            }
        }
        return true;
    }
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in));
		boolean result;
		int N = Integer.parseInt(br.readLine());
		while(N!=0){
			result = false;
			for(int i = 1; i<=N/2; i++){
				if(isPrimeNumber(i)&&isPrimeNumber(N-i)){
					System.out.println(N+" = "+i+" + "+(N-i));
					result = true;
					break;
				}
			}
			if(!result){
				System.out.println("Goldbach's conjecture is wrong.");
			}
			N = Integer.parseInt(br.readLine());
			if(N==0){
				break;
			}
		}
		
		br.close();
		
	}

}

 

- <백준 10989 JAVA> 수 정렬하기 3

import java.io.*;

public class Main {
	
	public static void main(String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	    int n = Integer.parseInt(br.readLine());
	    int[] arr = new int[10000001];

	    for(int i = 0; i < n; i++) {
	        arr[Integer.parseInt(br.readLine())]++;
	    }

	    for(int i = 0; i < 10000001; i++) {
	        if(arr[i] == 0) {
	        	continue;
	        }

	        for(int j = 0; j < arr[i]; j++) {
	            bw.write(i + "\n");
	        }

	    }

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

}

 

- <백준 11004 JAVA> K번째 수(실패)

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

public class Main {
	public static void swap(int[] a, int i, int j) {
		int ai = a[i], aj = a[j]; 
		if (ai == aj) {
			return; 
		}
		a[i] = aj;
		a[j] = ai; 
	}
	static int partition(int arr[], int low, int high) { 
		int pivot = arr[high];
		int i = (low-1); // index of smaller element 
		for (int j=low; j<high; j++) { 
			// If current element is smaller than or equal to pivot 
			if (arr[j] <= pivot) { 
				i++; 
				int a = arr[i];
				int b = arr[j];
				arr[i] = b;
				arr[j] = a;
			}
		}
		int a = arr[i+1];
		int b = arr[high];
		arr[i+1] = b;
		arr[high] = a;
		return i+1;
	}
	static void Quicksort(int[] A, int p, int r){
		if (p<r) {
			int q = partition(A, p, r); 
			//small ones on left
			//lager ones on right
			Quicksort(A, p, q-1);
			Quicksort(A, q+1, 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 k = Integer.parseInt(st.nextToken());
		 int arr[] = new int[n];
		 
		 st = new StringTokenizer(br.readLine());
		 for(int i=0;i<n;i++) {
			 arr[i] = Integer.parseInt(st.nextToken());
			 
		 }
		 
		 Quicksort(arr,0,n-1);
	       
		 System.out.println(arr[k-1]);
	}

}