정렬41 [백준] 1946번 - 신입 사원 [Java] https://www.acmicpc.net/problem/1946 1. 아이디어 두 성적 모두 다른 지원자 보다 떨어지는 자는 선발하지 않으므로 한 성적을 기준으로 정렬한 후 순회하며 정렬 기준이 아닌 다른 성적에 대해 이전 모든 지원자 보다 떨어지면 선발하지 않으면 된다.2. 문제풀이 성적은 1부터 N 중 중복되지 않는 수 이므로 1차원 배열을 활용해 한 성적을 인덱스, 한 성적은 값으로 하면 인덱스로 한 성적을 기준으로 정렬이 된 것으로 볼 수 있다. 배열을 순회하며 값의 최솟값을 갱신하며 저장하고 이 값을 현재 배열의 값과 비교하면 된다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(S.. 2025. 3. 18. [백준] 2170번 - 선 긋기 [Java] https://www.acmicpc.net/problem/2170 1. 아이디어 그리디 알고리즘과 스위핑 알고리즘으로 해결할 수 있었다.2. 문제풀이 일반적인 그리디 알고리즘이랑 스위핑 두 가지 방식으로 접근했다.그리디 알고리즘은 선의 x 좌표를 기준으로 오름차순 정렬한 우선순위 큐(items)와 y 좌표를 기준으로 내림차순 정렬한 우선순위 큐(pq) 두 개를 사용했다. items에서 원소(item)를 하나씩 꺼내서 pq의 원소(cur)와 비교하며 item과 cur이 겹치는 부분이 있으면 두 선을 합친 선을 pq에 다시 삽입하고 겹치는 부분이 없으면 각각 삽입하는 방식으로 구현했다. 이후 pq의 모든 선을 꺼내서 길이를 합하면 된다.스위핑은 x 좌표를 기준으로 오름차순, x 좌표가 같으면 y 좌표를 기.. 2025. 3. 7. [백준] 11000번 - 강의실 배정 [Java] https://www.acmicpc.net/problem/11000 1. 아이디어 그리디 알고리즘으로 해결할 수 있었다.시작 시간에 대한 오름차순 정렬 우선순위 큐와 종료 시간에 대한 오름차순 우선순위 큐 두 개를 활용해서 해결할 수 있다.2. 문제풀이 시작 시간에 대한 오름차순 우선순위 큐를 items, 종료 시간에 대한 오름차순 우선순위 큐를 pq로 선언했다.pq에 items의 첫번째 원소를 삽입한채로 시작하며 pq의 peek의 종료 시간보다 items의 peek의 시작 시간이 늦으면 pq의 해당 강의 뒤에 items의 강의를 붙이는 개념으로 생각할 수 있어서 pq의 해당 원소를 제거했다.pq에서 제거했으면 뒤에 붙이는 거니 pq에 삽입해야하고 pq에서 제거하지 않았어도 새로운 강의실이 필요한 것이.. 2025. 3. 6. [백준] 2457번 - 공주님의 정원 [Java] https://www.acmicpc.net/problem/2457 1. 아이디어 그리디 알고리즘으로 해결할 수 있었다.시작일에 대한 오름차순 정렬 우선순위 큐와 종료일에 대한 내림차순 우선순위 큐 두 개를 활용해서 3월 1일부터 피어있는 꽃 중 가장 지는 날이 늦을 꽃을 선택하고 현재 날짜를 갱신 후 다시 현재 날짜에 피어 있는 꽃 중 가장 지는 날이 늦은 꽃을 선택하는 과정을 반복했다.2. 문제풀이 최초 모든 꽃은 시작일에 대한 오름차순 우선순위 큐에 담았다.이후 현재 날짜를 3월 1일로 세팅해서 3월 1일에 피어져 있는 꽃들을 임시 우선순위 큐에 담고 이 중 가장 지는 날이 늦은 꽃 하나만 선택했다. 이후 현재 날짜를 다시 갱신하고 현재 날짜 기준 피어져 있는 꽃들을 다시 임시 우선순위 큐에 담는 .. 2025. 3. 5. [백준] 1744번 - 수 묶기 [Java] https://www.acmicpc.net/problem/1744 1. 아이디어 그리디 알고리즘으로 해결할 수 있다.1 보다 큰 정수는 값이 큰 정수부터 2개씩 묶을수록 최대가 되고, 1은 그냥 더할 때 최대가 된다.0 이하인 정수는 절댓값이 큰 정수부터 2개씩 묶을수록 최대가 된다.2. 문제풀이 1 보다 큰 정수를 담은 우선순위 큐와 0 이하인 정수를 담은 우선순위 큐 두 개를 활용했다.1은 따로 담지 않고 바로 더해줬다.1 보다 큰 정수를 담은 우선순위 큐는 절댓값이 큰 수부터 묶어야하므로 우선순위 큐의 길이가 홀수면 앞의 수 하나는 빼서 그냥 더하고 나머지는 묶는 식으로 구현했고,0 이하인 정수를 담은 우선순위 큐도 절댓값이 큰 수부터 묶어야하므로 하나밖에 안남아서 묶을 수 없으면 그냥 더하는 조.. 2025. 3. 4. [백준] 20920번 - 영단어 암기는 괴로워 [Java] https://www.acmicpc.net/problem/20920 1. 아이디어 Comparable을 이용한 정렬로 우선순위를 정하는 방식으로 해결할 수 있다.2. 문제풀이 정렬에 단어의 빈도수가 필요하므로 Map으로 입력을 받아서 단어와 개수를 세줬다. 이후 각 Entry를 활용해 노드 클래스를 만들고 이를 우선순위에 맞게 정렬하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { private static class Node implements Comparable { String word; int cnt; public Node(String word, int cnt) { .. 2025. 2. 20. [백준] 2108번 - 통계학 [Java] https://www.acmicpc.net/problem/2108 1. 아이디어 산술평균은 Math.round 메서드로 반올림을 하는 방식으로, 중앙값은 정렬을 활용해서, 최빈값은 카운팅 배열로, 범위는 정렬을 활용해서 구할 수 있다.2. 문제풀이 입력 단계에서 수들을 배열로 입력받으면서 합과 카운팅 배열을 작성했다. 이후 배열을 정렬해서 중앙값과 범위를 구하고 합으로 산술평균을 구하고, 카운팅 배열로 최빈값을 찾는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { private static final int MAX = 4000; public static void main(String[] args) throws I.. 2025. 2. 19. [백준] 8979번 - 올림픽 [Java] https://www.acmicpc.net/problem/8979 1. 아이디어 람다식을 활용한 객체 정렬로 해결할 수 있었다.2. 문제풀이 각 국가를 클래스로 만들고 국가 번호, 국가 순위, 금메달 수, 은메달 수, 동메달 수를 필드로 뒀다. 입력을 받은 후 금은동에 맞춰 정렬을 하고 순회를 하며 인덱스로 순위를 부여했다. 이후 국가 번호 순으로 정렬해서 K 국가의 순위를 출력하면 됐다.3. 코드 import java.io.*;import java.util.*;public class Main { private static class Node { int num; int order; int gold; int silver; int bron.. 2025. 2. 18. [백준] 18110번 - solved.ac [Java] https://www.acmicpc.net/problem/18110 1. 아이디어 Math.round 메서드로 반올림을 수행하는 걸 활용하면 간단하게 해결할 수 있다.2. 문제풀이 주어진 점수들을 정렬한 후 절사평균을 위한 15%에 해당하는 인원수를 계산 후 인덱스를 활용해 70% 인원의 점수만 더했다. 이후 절사평균만 출력하면 된다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); .. 2025. 2. 15. [SWEA] 1966번 - 숫자를 정렬하자 [Java] https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PrmyKAWEDFAUq 1. 아이디어 배열의 정렬은 Arrays.sort 메서드로 정렬할 수 있다.2. 문제풀이 주어진 입력을 배열로 받아 정렬 후 StringBuilder로 포맷팅해서 출력하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Solution { public static void main(String[] args) throws IOException {// BufferedReader br = new BufferedReader(new InputStreamRea.. 2025. 2. 13. [SWEA] 14229번 - 백만 개의 정수 정렬 [Java] https://swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AX_Y-4T6-yoDFAVy 1. 아이디어 Arrays.sort 메서드로 정렬을 수행하면 간단하게 해결할 수 있다.2. 문제풀이 정렬 후 해당 인덱스의 값을 출력했다.3. 코드 import java.io.*;import java.util.*;public class Solution { private static final int MAX = 1_000_000; public static void main(String[] args) throws IOException {// BufferedReader br = new BufferedRe.. 2025. 2. 12. [백준] 2696번 - 중앙값 구하기 [Java] https://www.acmicpc.net/problem/2696 1. 아이디어 중앙값보다 작은 수들을 모은 우선순위 큐와 중앙값보다 큰 수들을 모은 우선순위 큐를 활용하면 해결할 수 있다.2. 문제풀이 중앙값보다 작은 수들을 모은 우선순위 큐는 내림차순 정렬, 중앙값보다 큰 수들을 모은 우선순위 큐는 오름차순 정렬을 해서 두 우선순위 큐의 peek 값이 중앙값 바로 전후가 되도록 했다. 이후 두 우선순위 큐의 크기를 동일하게 유지만 하면 간단하게 중앙값을 구할 수 있다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { .. 2025. 2. 12. 이전 1 2 3 4 다음
