99클럽 코테 스터디 1일자 TIL [03/31]

참여 난이도

자바/미들러

오늘의 문제

백준 1929 소수 구하기

 

예전에 많이 풀었던 문제라 쉽게 풀 수 있을 거라고 생각했지만, 금방 풀지는 못했습니다. ㅠㅠ

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String[] str = sc.nextLine().split(" ");

        int M = Integer.parseInt(str[0]);
        int N = Integer.parseInt(str[1]);

        boolean[] isPrime = new boolean[N + 1];
        primeEratosthenes(N, isPrime);

        for (int i = M; i <= N; i++) {
            if (isPrime[i]) System.out.println(i);
        }
    }

    public static void primeEratosthenes(int n, boolean[] isPrime) {
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;

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

풀이 방법

• 에라토스테네스의 체 (Sieve of Eratosthenes) 사용
  • 소수를 빠르게 구하는 대표적인 방법
  • N까지의 수에서 소수의 배수들을 지워가며 소수만 남기는 방식
  • 시간복잡도: O(N log log N) → 매우 빠름
• 시간 복잡도 계산 (1) 바깥 for 문

for (int i = 2; i * i <= n; i++)

 

-> 이 반복문은 루트 n번 반복합니다.

-> 조건이 i * i < n 을 보면 알 수 있습니다.

 

• 시간 복잡도 계산 (2) 안쪽 for 문

for (int j = i * i; j <= n; j += i)

 

 

i가 2일 때: n / 2번

i가 3일 때: n / 3번

i가 5일 때: n / 5번

 

i가 2이며, n이 20이라면
4, 6, 8, 10, 12, 14, 16, 18, 20 → 2의 배수 중, 2를 제외한 값들이 지워집니다. 
대략적으로 n/2에 비례하는 횟수라고 볼 수 있습니다.

정리

• 입력: M N
• 출력: M 이상 N 이하의 소수
• 알고리즘: 에라토스테네스의 체
• 시간복잡도: O(N log log N)
• 주의할 점: 체의 시작은 항상 2부터

 

추가 문제 정리

347. Top K Frequent Elements

https://leetcode.com/problems/top-k-frequent-elements/description/

import java.util.*;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        List<Integer> keys = new ArrayList<>(map.keySet());
        keys.sort((a, b) -> map.get(b).compareTo(map.get(a)));
        int[] answer = new int[k];
        for (int i = 0; i < k; i++) {
            answer[i] = keys.get(i);
        }
        return answer;
    }
}

• map으로 (num, 중복횟수) 수집하고
• key값을 가져와, 정렬을 하는데 조건을 map에 있는 value값 내림차순 
• 오름차순이였으면 간단한 람다식으로 처리할 수 있으나 문제에서는 내림차순으로 정렬을 해야 원하는 값을 구할 수 있었습니다.

 

회사 업무 TIL

InputStreamDataSource, ByteArrayDataSource 차이

• eml파일을 파싱해서, 첨부파일을 읽어 추출해야하는 파싱을 진행해야 했습니다.
• 첨부파일의 데이터를 읽을 때 다음과 같은 이슈가 있었습니다.
• ByteArrayDataSource 방식으로 첨부파일의 InputStream에서 전체 데이터를 읽어와서 바이트 배열로 보관하는 방법
• InputStreamDataSource 방식으로 첨부파일의 InputStream을 그대로 저장해서 실제로 데이터가 필요할 때(getInputStream 호출 시) 스트림을 통해 파일의 데이터를 읽어오는 방법
• 전자의 경우 여러 개발자들이 바이트 배열을 메모리에 올려 저장한 후, 필요할 때 데이터를 배열에서 제공하기 때문에 out of memory가 날 수 있습니다.
• 후자의 경우 파일의 전체 데이터를 미리 메모리에 로드하지 않으므로 대용량 파일 처리 시 메모리 부담이 적어질 수 있습니다.
• 저의 경우에는 대량의 첨부파일이 업로드 될 가능성이 있기 때문에 InputStreamDataSource 방식으로 파싱을 진행했습니다.
• 참고 글
  • https://velog.io/@dongvelop/Spring-Boot-Out-of-Memory-when-Using-JDK21

[Spring Boot] Out of Memory when Using JDK21

import javax.activation.DataSource;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;

public class InputStreamDataSource implements DataSource {
    private final InputStream inputStream;
    private final String contentType;
    private final String name;

    public InputStreamDataSource(InputStream inputStream, String contentType, String name) {
        this.inputStream = inputStream;
        this.contentType = contentType;
        this.name = name;
    }

    @Override
    public InputStream getInputStream() throws IOException {
        return inputStream;
    }

    @Override
    public OutputStream getOutputStream() throws IOException {
        throw new IOException("OutputStream not supported.");
    }

    @Override
    public String getContentType() {
        return contentType;
    }

    @Override
    public String getName() {
        return name;
    }
}