18115번(덱), 2798번, 1929번(소수)

18115번

 

 

수열 A를 뒤집어서 풀이하면 된다

1번 > 2번 > 3번 > 3번 > 2번 순서로 기술을 실행

 

1. deque의 맨 앞에 1을 집어 넣음

2. deque의 맨 앞에 있는 1을 잠시 버리고 앞에 2를 집어 넣은 후 다시 맨 앞에 1을 넣는다

3. deque의 맨 뒤에 숫자 3을 넣는다

4. deque의 맨 뒤에 숫자 4를 넣는다

5. deque의 맨 앞에 있는 1을 잠시 버리고 앞에 5를 집어 넣은 후 다시 맨 앞에 1을 넣는다 

 

 

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


public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Deque<Integer> deque = new ArrayDeque<>();
        List <Integer> list = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        for(int i = 0; i<n; i++) {
            list.add(Integer.valueOf(st.nextToken()));
        }
        Collections.reverse(list);
        int num = 1;
        for(int i = 0; i<n; i++) {
            if(list.get(i) == 1) {
                deque.offerFirst(num);
            } else if (list.get(i) == 2) {
                int tmp = deque.pollFirst();
                deque.offerFirst(num);
                deque.offerFirst(tmp);
            } else {
                deque.offerLast(num);
            }
            num++;
        }
        StringBuilder sb = new StringBuilder();
        for(int i : deque) {
            sb.append(i+" ");
        }
        System.out.println(sb);
    }
}

 

2798번

 

 

삼중 for문을 사용하여 카드 3장의 나올 수 있는 모든 합들을 list에 넣는다

for문을 돌며 list를 탐색하여 m을 넘지 않으면서 m에 최대한 가까운 합을 구해 출력

 

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

public class Solution {
    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());
        List <Integer> list = new ArrayList<>();
        int [] arr = new int[n];
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i<n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        for(int i = 0; i<arr.length; i++) {
            for(int j = i+1; j< arr.length; j++) {
                for(int k = j+1; k< arr.length; k++) {
                    list.add(arr[i]+arr[j]+arr[k]);
                }
            }
        }
        Collections.sort(list);
        for(int i = list.size()-1; i>=0; i--) {
            if(list.get(i)<=m) {
                System.out.println(list.get(i));
                break;
            }
        }
    }
}

 

삼중 for 문의 이해를 돕기 위한 코드 (4가지 숫자 중 세 개의 숫자를 뽑아 합들을 출력)

 

1929번

 

 

시간 초과 떠서 틀렸다ㅠ

 N 이하의 소수를 모두 구하는 알고리즘 중에 N 보다 작은 자연수들로 모두 나눠보는 풀이의 시간복잡도는 O(N²)  

 

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));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        List <Integer> list = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        for(int i = m; i<=n; i++) {
            int number = i;
            int j;
            for(j = 2; j<=n; j++) {
                if(number%j == 0) {
                    break;
                }
            }
            if(j == number) {
                list.add(j);
            }
        }
        for(int i : list) {
            sb.append(i).append("\n");
        }
        System.out.println(sb);
    }
}

 

다른 방법이 생각나지 않아 찾아보니 아라토스테네스의 체를 사용하는 풀이가 많더라

 

 

2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.

2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)

자기 자신을 제외한 2의 배수를 모두 지운다.

남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)

자기 자신을 제외한 3의 배수를 모두 지운다.

남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)

자기 자신을 제외한 5의 배수를 모두 지운다.

남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)

자기 자신을 제외한 7의 배수를 모두 지운다.

위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다

 

k=2 부터 √n 이하까지 반복하여 자연수들 중 k를 제외한 k의 배수들을 제외시킨다

결론적으로 n의 루트를 씌운 값의 배수까지만 확인

 

잘 이해가 가진 않지만 그렇다고 하자(?)

JAVA [자바] - 소수 구하는 알고리즘 및 구현 (tistory.com)

JAVA [자바] - 소수 구하는 알고리즘 및 구현

 

 

2 이상 √n 이하의 수 중에 나누어 떨어지는 수가 존재한다면 소수가 아님을 이용한 방법도 있다

 

 

만약 𝑝가 증가한다면  𝑞가 감소하고, 반대로 𝑝가 감소한다면 𝑞 가 증가한다

𝑝 와 𝑞 는 n의 약수이기 때문에 결국 n을 임의의 수로 나누게 될 경우 임의의 수가 √n보다 작다면 결국 나머지는 √n 보다 클 수 밖에 없다. 결과적으로 𝑝 와 𝑞 중 하나는 반드시 √n 보다 작거나 같다

 

√n 이하의 자연수 중에 나누어 떨어지는 수가 있다면 이는 1 과 n을 제외한 다른 자연수가 n의 약수라는 의미

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));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        StringBuilder sb = new StringBuilder();
        for(int i = m; i<=n; i++) {
            primeMake(i);
        }
    }

    public static void primeMake (int number) {
        if(number<2) return; // 0 과 1 은 소수가 아니므로 종료

        if(number == 2) { // 굳이 안 넣어도 2가 소수로 출력되긴 하지만 어쨌든....
            System.out.println(number);
            return;
        }

        for(int i =2; i<=Math.sqrt(number); i++) {
            if(number % i == 0) { // 소수가 아닐경우 종료
                return;
            }
        }
        System.out.println(number); //  위에 해당하지 않는 수는 모두 소수
        return;
    }
}