java
[백준] 1181번 : 단어 정렬 - JAVA [자바]
[백준] 1181번 : 단어 정렬 - JAVA [자바]
2020.06.19www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1≤N≤20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 문제 이전 좌표정렬하기 문제를 풀어보았다면 이 문제 또한 매우 간단한 문제다! ※ 주의할 점 단어 길이순으로 정렬한 뒤, 길이가 같을 경우 사전순으로 정렬해야한다. 중복되는 단어가 있을경우 한 번만 출력한다. 알고리즘 [접근 방법] 이전 포스팅에서도 말했지만 배열을 특정한 규칙에 의해 정렬하고 싶은 경우 Arrays.sort 메소드에 Comparator 을 구현하면 된다고 했다. (만약 보지 못한 분들을 위..
[백준] 11651번 : 좌표 정렬하기 2 - JAVA [자바]
[백준] 11651번 : 좌표 정렬하기 2 - JAVA [자바]
2020.06.17www.acmicpc.net/problem/11651 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 문제 좌표 정렬하기 (11650번) 문제를 풀었다면 매우 쉬운 문제다. 알고리즘은 따로 설명 안할테니 아래 링크를 참고해주시면 된다. st-lab.tistory.com/110#알고리즘 [백준] 11650번 : 좌표 정렬하기 - JAVA [자바] www.acmicpc.net/problem/11650 1546번: 평균 첫째 줄에 시험 본 과목의 개수 N이 주..
[백준] 11650번 : 좌표 정렬하기 - JAVA [자바]
[백준] 11650번 : 좌표 정렬하기 - JAVA [자바]
2020.06.10www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 문제 이번 문제는 람다식(lambda)만 쓸 줄 알면 그리 어렵지 않게 풀 수 있다. (오랜만입니다..) 알고리즘 [접근 방법] 보통 문제를 보면 가장 먼저 생각하는 것이, 아! 2차원 배열을 사용해야겠다! 일 것이다. 아쉽게도 Arrays.sort() 자체는 2차원 배열의 정렬을 할 수가 없다. 그렇기 때문에 람다식을 사용하여 Arrays.sort() 확장..
[백준] 1427번 : 소트인사이드 - JAVA [자바]
[백준] 1427번 : 소트인사이드 - JAVA [자바]
2020.06.03www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하고자하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 오랜만에 매우 쉬운 문제가 나왔다. 알고리즘 [접근 방법] 이 문제의 경우 접근 방법이 정말 무궁무진하다. 먼저 정렬 알고리즘으로 배열을 이용하여 Arrays.sort 를 사용하는 방법부터 카운팅정렬을 사용하는 방법, 이렇게 크게 두 가지가 있을 것이다. 또한 각 자릿수의 값을 정렬하는 것이다보니 입력방법도 다양하게 할 수 있다. Scanner 을 사용하여 입력받는 방법, BufferedReader 로 입력받는 방법, InputStream 으로 입력받는 방법 등 매우 많다. 각 자릿수를 값으로..
[백준] 2108번 : 통계학 - JAVA [자바]
[백준] 2108번 : 통계학 - JAVA [자바]
2020.06.01www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 문제 그리 어렵지 않은 문제지만 약간의 함정이 있으니 주의해야한다. ※ 주의할 점 동일한 최빈값이 있을경우 '두 번째로 작은 값'을 출력해야 한다. 알고리즘 [접근 방법] 기본적으로 이 문제를 풀기 위해서는 Counting Sort(카운팅 정렬)을 사용할 것이다. 물론 정렬을 쉽게 하기 위해 Arrays.sort 로 풀 수도 있지만 최빈값을 구하는 과정에 있어 '두 번째로 작은 값'을 출력해야하다보니 조금 복잡해진다. (사실상 중앙값 때문에 정렬..
[백준] 10989번 : 수 정렬하기 3 - JAVA [자바]
[백준] 10989번 : 수 정렬하기 3 - JAVA [자바]
2020.05.31www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 드디어 그동안의 기본정렬을 끝맺는 끝판왕 문제다! ※ 주의할 점 Java 의 시간 제한은 3초다. (원래 자바의 경우 언어 보너스가 있어 주어진 시간의 ×2 + 1 초가 주어지지만 이번에는 3초를 넘길 수 없다) (2021. 01. 10 기준 Java → Java8로 명칭이 바뀌었다.) Java 의 메모리 제한은 512MB 이다. 알고리즘 [접근 방법] 이전의 수 정렬하기 문제 포스팅을 보셨다면 이 문제는 쉽게 풀 수 있을..
[백준] 2751번 : 수 정렬하기 2 - JAVA [자바]
[백준] 2751번 : 수 정렬하기 2 - JAVA [자바]
2020.05.30www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 문제 수 정렬하기에 이은 두 번째 문제다. 차이점이라면 데이터도 이전 문제에 비해 1000배 많아졌고, 수의 범위도 1000배 넓다. ※ 주의할 점 Java기준 Arrays.sort 로 쓰면 시간초과가 날 가능성이 높다. (2021.01.11 Java → Java8 명칭이 변경됨) 알고리즘 [접근 방법] 이 문제를 풀기 전에 참고했으면 하는 글 두 개를 넣겠다. 문제를 푸는데 있어 매우 도움이 될 ..
[백준] 2750번 : 수 정렬하기 - JAVA [자바]
[백준] 2750번 : 수 정렬하기 - JAVA [자바]
2020.05.29www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 문제 정렬의 가장 기초적인 문제다! 9가지 방법을 이용하여 풀이한다. 먼저 정렬 방법은 여러가지가 있지만 가장 쉽게 쓸 수 있는 방법은 크게 3가지가 있다. 먼저, 선택정렬이다. 첫 번째 인덱스부터 시작하여 뒤의 인덱스들의 값들과 비교하여 최솟값들을 차곡차곡 쌓아나가는 방법이다. 가장 구현하기 쉽다는 장점이 있으나 시간복잡도가 O(n2) 으로 그리 좋은 성능의 알고리즘은 아니다. 아마 정렬을 구현해보거나 접해본 분들..
자바 [JAVA] - 카운팅 정렬 (Counting Sort / 계수 정렬)
자바 [JAVA] - 카운팅 정렬 (Counting Sort / 계수 정렬)
2020.05.29[정렬 알고리즘 모음] 더보기 1. 계수 정렬 (Counting Sort) - [현재 페이지] 2. 선택 정렬 (Selection Sort) 3. 삽입 정렬 (Insertion Sort) 4. 거품 정렬 (Bubble Sort) 5. 셸 정렬 (Shell Sort) 6. 힙 정렬 (Heap Sort) 7. 합병(병합) 정렬 (Merge Sort) 8. 퀵 정렬 (Quick Sort) 9. 이진 삽입 정렬 (Binary Insertion Sort) 10. 팀 정렬 (Tim Sort) Counting Sort [계수 정렬 / 카운팅 정렬] Counting Sort... 계수 정렬, 카운팅 정렬 등으로 많이 불리지만, 가장 와닿는 단어는 카운팅 정렬이므로 이 포스팅에서는 카운팅 정렬로 통일하여 쓰겠다. 카운팅..
[백준] 1436번 : 영화감독 숌 - JAVA [자바]
[백준] 1436번 : 영화감독 숌 - JAVA [자바]
2020.05.27www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 문제 매우 간단한 문제지만 예외의 상황을 잘 고려해야 하는 문제다. 알고리즘 [접근 방법] 이 문제의 경우 브루트포스를 사용할 수도, 사용하지 않을 수도 있는 문제다. 두 가지 접근법을 살펴보도록 하자. [방법 1] 일단 N 번째 ( 1 ≤ N ≤ 10000 ) 로 큰 "666" 이 들어가는 수를 찾아야 한다. 가장 간단하게 브루트포스를 사용하는 방법은 N 의 최솟값은 1 이니 결국 666부터 시작하여, 1 ..