📙[Algo] 24.01.22 알고리즘 / SQL

알고리즘 문제) BOJ 1644. 소수의 연속합

1644번: 소수의 연속합

문제 요약

• 자연수가 연속된 소수의 합으로 나타낼 수 있는 경우의 수 구하기

시간 제한

• 2초

입력

• 자연수 N (1 ≤ N ≤ 400만)

출력

• 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수 출력

접근법

1. 완전 탐색으로 접근하기
   1 3 5 7 9 11 13 17 19 23 29 31 37 …
   
   • 에라토스트 테네스 체에서 소수 목록 만들고,
   • 소수인 숫자만 뽑아서 배열 리스트에 담기
   • 해당 리스트 앞에서부터 연속합을 구하고, 자연수 N이 나오는 구간 찾기
2. 최적화 하기
   • 에라토스트 테네스 체에서 400만*log400만 = 2400만 시간 걸림
   • 리스트 담을 때도 넉넉히 400만 시간 걸린다 생각
   • 연속합을 구할 때 최적화 필요
     • N = 20
       1 3 5 7 11 13 17 19 23…
       s
       e
       
       • s → 1, e → 1
         • sum = 1 < 20
         • e += 1
       • s → 1, e → 3
         • sum = 4 < 20
         • e += 1
       • s → 1, e → 5
         • sum = 9 < 20
         • e += 1
       • s → 1, e → 7
         • sum = 16 < 20
         • e += 1
       • s → 1, e → 11
         • sum = 27 > 20
         • s += 1
       • s → 3, e → 11
         • sum = 26 > 20
         • s += 1
       • s → 5, e → 11
         • sum = 23 > 20
         • s += 1
       • s → 7, e → 11
         • sum = 18 < 20
         • e += 1
       • s → 7, e → 13
         • sum = 31 > 20
         • s += 1
       • s → 11, e → 13
         • sum = 24 > 20
         • s += 1
       • s → 13, e → 13
         • sum = 13 < 20
         • e += 1
       • s → 13, e → 17
         • sum = 30 > 20
         • s += 1
       • s → 17, e → 17
         • sum = 17 < 20
         • e += 1
       • s → 17, e → 19
         • sum = 36 > 20
         • s += 1
       • s → 19, e → 19
         • sum = 19 < 20
         • e += 1
       • s → 19, e → 23
         • sum = 42 > 20
         • s += 1
       • s → 23, e→ 23
         • sum = 23 > 20
         • s =+ 1
         • s > e되므로 종료

코드

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

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());

        boolean[] isPrime = new boolean[4000010];
        Arrays.fill(isPrime, true);
        isPrime[1] = false;
        for (int i = 2; i <= 4000000 ; i++) {
            if(!isPrime[i]) continue;

            if ((long)i * i <= 4000000) {
                for (int j = i * i; j <= 4000000; j += i) {
                    isPrime[j] = false;
                }
            }

        }

        ArrayList<Integer> primes = new ArrayList<>();
        for (int i = 1; i <= 4000000; i++) {
            if(isPrime[i]) primes.add(i);
        }

        int s = 0, e = 0, cnt = 0, sum = primes.get(0);
        while (s <= e) {

            if (sum < N) {
                e++;
                if(e == primes.size()) break;
                sum += primes.get(e);
            } else if (sum >= N) {
                if(sum == N) cnt++;
                sum -= primes.get(s);
                s++;
            }

        }

        bw.write(String.valueOf(cnt));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

SQL ) Lv1. 흉부외과 또는 일반외과 의사 목록 출력하기  

문제 요약

• 조인 문제인 줄 알았는 데 UNION 문제
• 오프라인 판매 데이터랑 온라인 판매 데이터 둘 다 표현
• 오프라인 판매 데이터의 USER_ID는 NULL로 표현

알게 된 점

null as

• 오프라인 테이블에는 user_id 칼럼이 없어서 null as 처리

UNION

• 쿼리 결과를 합치며 중복된 row 제거

UNION ALL

• 쿼리 결과를 합치며 중복된 row 제거 안 함

(SELECT DATE_FORMAT(SALES_DATE, "%Y-%m-%d") AS DATE_FORMAT, PRODUCT_ID, USER_ID, SALES_AMOUNT
FROM ONLINE_SALE 
WHERE SALES_DATE LIKE '2022_03%')
UNION
(SELECT DATE_FORMAT(SALES_DATE, "%Y-%m-%d") AS DATE_FORMAT, PRODUCT_ID, NULL AS USER_ID, SALES_AMOUNT
FROM OFFLINE_SALE 
WHERE SALES_DATE LIKE '2022_03%')
ORDER BY 1,2,3;