전체 글89 백준 1929: 소수 구하기(JAVA) / 에라토스테네스의 체 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 소수를 판별하는 알고리즘은 여러가지가 있다. 숫자 하나에 대하여 소수인지 판단할 때는 해당 숫자의 제곱근까지만 약수인지 아닌지 반복문을 돌리면 O(N^1/2)의 시간 복잡도로 빠르게 구할 수 있다. 특정 수를 나눴을 때 몫은 항상 그 수의 제곱근 이하이기 때문이다. 하지만 여러 개의 소수를 한꺼번에 판별해야할 경우는 에라토스테네스의 체를 이용한다. *에라스토스테네스의 체 소수를 판별할 범위만큼 배열을 할당하고 소수가 아니면 하나.. 2022. 8. 9. 백준 10816: 숫자 카드 2(JAVA) https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 전에 풀었던 숫자 카드는 해당 숫자의 카드가 있는지만 판별하면 되는거라서 HashSet의 contains로 쉽게 풀 수 있었다. 이번 숫자 카드 2 문제는 해당 숫자의 카드가 몇 개 있는지까지 저장해야해서 위와 같은 방법으로는 풀 수 없다. 그래서 떠올린 방법이 map을 이용하는 것이다. 물론 더 좋은 방법이 있을 것 같지만...일단 도전 key 값으로 카드의 숫.. 2022. 7. 19. 백준 1181: 단어 정렬 https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net Arrays.sort()를 이용하여 정렬하였다. 첫번째는 String 객체에 기본적으로 구현되어있는 Comparator에 의해 알파벳 순서로 정렬이 된다. 그 후 새롭게 문자열을 비교해서 반환하는 Comparator를 구현하면 길이가 짧은 순서로 정렬된다. 최종적으로는 길이 순으로, 그 중에서도 알파벳 순으로 정렬이 된다. 중복은 출력문에서 처리하였다. 앞에 위치한 문자열과 같다면 출력.. 2022. 7. 17. 백준 10815: 숫자 카드(JAVA) ArrayList의 contains는 타임아웃 발생 *ArrayList의 contians는 시간복잡도: O(n) 대신 HashSet을 사용하였다. *HashSet의 contains는 시간복잡도: O(1) 시간을 단축시키기 위해 StringBuilder를 이용하여 출력하였다. import java.util.*; public class Main { public static void main(String[] args) { int N, M; Scanner sc = new Scanner(System.in); N = sc.nextInt(); HashSet arr = new HashSet(); StringBuilder sb = new StringBuilder(); for(int i=0; i 2022. 7. 17. 백준 10989번: 수 정렬하기 3(JAVA) / 계수 정렬(counting sort) https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 시간을 단축하기 위해 Scanner 대신 BufferedReader 사용하였고 출력도 StringBuilder를 사용하였다. 정렬로 계수정렬(counting sort)를 사용하였다 *Counting sort 시간복잡도: O(n) ->10000보다 작거나 같은 자연수라고 했기 때문에 계수정렬을 사용할 수 있다. 수를 입력받을 때마다 해당 숫자의 cnt값 1 증가시키면 1부터 10000까지 중복을 포함한 정렬을 할 수 .. 2022. 7. 16. 이전 1 ··· 12 13 14 15 다음