정렬24 [백준]3151: 합이 0 - JAVA https://www.acmicpc.net/problem/3151 풀이N개의 숫자들 중 3개를 선택하여 그들의 합을 0으로 만드는 경우의 수를 찾는 문제이다. 배열에 숫자들을 저장하여 정렬한다. 첫 번째 숫자를 선택하고, 그 다음 숫자를 left, 배열의 끝 숫자를 right로 놓고 left와 right를 조정하여 합이 0이 되는 수를 찾는다. 선택한 숫자를 node라고 할 때, `node + arr[left] + arr[right]` 가 0이 되는 경우를 찾아 정답을 증가시킨다. `arr[left]` 와 `arr[right]`가 같은 경우에는 left부터 right까지의 수가 n개라고 할 때 nC2의 조합을 구하는 것과 같다. 처음 선택한 수를 0부터 시작하여 증가시키면서 값이 0보다 커질 때까지 실행.. 2024. 9. 3. [백준] 30960: 조별 과제 - JAVA https://www.acmicpc.net/problem/30960 풀이N명의 학생들의 조를 편성해야한다. 1개의 조만 3명으로 편성되고 다른 조들은 2명으로 편성된다. 학생에게 숫자가 부여되는데 각 조 안에서 (최댓값 - 최솟값)이 해당 조의 어색함이 된다. 어색함의 합의 최소가 되도록해야한다. 먼저 입력받은 배열을 정렬했다. 정렬 후 2개의 배열을 만들어서 하나는 앞에서부터 시작, 하나는 뒤에서부터 시작하여 누적합을 담았다. 누적합은 어색함들의 합을 더해줬다. `left[i] += (arr[i] - arr[i-2])` 이런식으로 어색함을 더해줬고, i는 2찍 증가시키면서 진행했다. 누적합 배열 2개를 만든 후, 어느 지점에서 3명인 조를 시작해야 어색함이 최소가될지 구해줬다. 메모리: 84096K.. 2024. 6. 25. [백준] 23889: 돌 굴러가유 - JAVA https://www.acmicpc.net/problem/23889 풀이마을들이 일자로 배치되어있고 돌은 벽을 만날때까지 왼쪽에서 오른쪽으로 굴러간다. 마을에는 모래성이 있어서 돌이 굴러가면 모래성이 다 부서진다. 벽을 세워 돌을 막을 수 있는데 모래성이 가장 적게 부서지게 세워야 한다. 돌의 위치와 몇개의 모래성을 부수는지 이차원배열에 담았다. 먼저 돌이 굴러가기 시작하는 위치를 배열에 넣고, 돌의 위치를 기준으로 다음 돌까지 모래성의 개수를 합하여 배열에 넣었다. 부수는 모래성의 개수를 기준으로 내림차순 정렬하고, 가장 많은 모래성을 지킬 수 있는 경우가 두 가지 이상 존재할 경우, 사전순으로 가장 빠른 답을 출력해야 하므로 모래성의 개수가 같을 경우 돌의 위치를 기준으로 오름차순 정렬하였다. 벽의 .. 2024. 6. 20. [백준] 28449: 누가 이길까 - JAVA https://www.acmicpc.net/problem/28449 풀이HI 팀과 ARC 팀의 모든 사람들끼리 한번씩 대결하여 N X M회의 대결이 성사된다. HI팀이 이기는 횟수, ARC팀이 이기는 횟수, 무승부하는 횟수를 구해야 한다. 각 팀의 점수를 입력받아 각각 정렬했다. HI팀을 순회하면서 HI팀원의 점수를 타겟으로 하여 ARC팀에서 해당 점수와 같은 점수가 있는지 찾았다. 이때, 이분탐색을 이용하여 같은 점수가 시작되는 지점(drawStart), 같은 점수가 끝나는 지점(drawEnd)를 각각 찾았다. drawStart보다 작은 값들은 HI팀이 이기게 되고, drawEnd보다 큰 값들은 ARC팀이 이기게 된다. 메모리: 41148KB시간: 700ms언어: Java 11import java.i.. 2024. 6. 18. [백준] 14527: Paired Up - JAVA https://www.acmicpc.net/problem/14527 풀이소들의 수와 milk output이 주어진다. milk output을 기준으로 정렬했다. 투포인터를 이용하여 양쪽에서 가운데를 향해 가면서 소의 수를 감소시키고, 0이되면 다음으로 넘어간다. 이때 milk output의 합을 정답에 갱신하면 되는 문제였다. 메모리: 46184KB시간: 3044ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStream.. 2024. 6. 10. [백준] 1263: 시간 관리 - JAVA https://www.acmicpc.net/problem/1263 풀이해야 할 일들 n개가 일을 처리하는데 걸리는 시간(s), 마감시간(t)이 주어진다. 이차원배열에 s와 t를 넣고 정렬하는데, 이때 정렬기준은 마감시간을 내림차순으로 정렬했다. 마감시간이 마지막인 것 부터 걸리는 시간을 빼주면 일을 언제 시작해야 하는지 구할 수 있다. 일을 시작해야할 시간을 갱신하면서 이 시간이 바라보고있는 일의 마감시간보다 작다면 하던대로 빼주고, 크다면 시작해야 할 시간을 현재 마감시간에서 걸리는 시간을 빼준 값으로 갱신한다. 메모리: 14576KB시간: 148ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static v.. 2024. 5. 31. [백준] 23843: 콘센트 - JAVA https://www.acmicpc.net/problem/23843 풀이충전기 m개로 n개의 전자기기를 충전해야한다. 전자기기마다 충전이 완료되는데 필요한 시간이 달라서 충전기에 전자기기를 적절하게 배치해야한다. 충전기가 비어있다면 충전에 걸리는 시간이 가장 긴 기기를 배치하는 게 적절했다. 따라서 우선순위큐를 이용해 시간이 오래걸리는 순으로 뽑아서 충전기에 넣었다. 충전기에 넣으면서 걸리는 시간을 정답에 갱신하면된다. 메모리: 15476KB시간: 180ms언어: Java 11import java.io.*;import java.util.*;public class Main { static class Charger { PriorityQueue chargers; Priority.. 2024. 5. 22. [백준] 2230: 수 고르기 - JAVA https://www.acmicpc.net/problem/2230 풀이n개의 정수가 주어지고, 두 수를 골랐을 때 차이가 m 이상인 경우 중 제일 작은 경우를 골라야 한다. 정렬을 해놓고 슬라이딩윈도우를 통해 두 수를 골라 차이를 비교했다. start, end 이렇게 두 포인터를 두고 두 수의 차이가 m보다 작은 경우 end를 1 늘린다. 두 수의 차이가 큰 경우 정답을 갱신하고 start를 1늘린다. 메모리: 28584KB시간: 396ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedRead.. 2024. 5. 19. [백준] 1744: 수 묶기 - JAVA https://www.acmicpc.net/problem/1744 풀이길이 n의 수열이 주어지고, 이 수열의 합을 구하는 문제이다. 수열내의 두 수를 묶어 그 수들을 곱하는 것으로 계산 할 수 있다. `{-1, 2, 1, 3}` 과 같은 수열이 있다면, 2와 3을 묶어 6으로 만들고, `-1 + 1 + 6 = 6` 으로 6이 최대값이 된다. 음수는 같은 음수끼리 곱하거나, 0과 곱할 때 합에서 이득을 볼 수 있으므로 0이하인 것들은 minus 리스트에 담고, 0보다 큰 수들은 plus 리스트에 담았다. 두 리스트를 정렬해서 minus에 있는 것들은 작은 순으로 2개씩 묶고, plus에 있는 수들은 큰 순으로 2개씩 묶었다. 다만, 1의 경우는 `{1, 1}` 의 수열에서 볼 때, `1 + 1` 이 `1 .. 2024. 5. 19. [백준] 8983: 사냥꾼 - JAVA https://www.acmicpc.net/problem/8983 풀이x축에 사냥꾼들의 위치가 주어지고, 동물의 좌표가 x, y 좌표로 주어진다. 사냥꾼의 총의 사정거리가 주어지고, 동물을 몇 마리 잡을 수 있는지 구하는 문제이다. 동물을 기준으로 자신을 잡을 수 있는 사냥꾼이 있는지 판별했다. 동물의 위치로부터 사정거리 내에 있는 x축 위 점의 최소, 최대를 구한다. 이를 left, right로 하고 이분탐색을 통해 사냥꾼의 위치가 이 범위 안에 있는지 확인한다. 메모리: 55416KB시간: 700ms언어: Java 11import java.io.*;import java.util.*;public class Main { static class Animal { int x; .. 2024. 5. 19. 이전 1 2 3 다음