Algorithm/정렬(Sort)
-
[백준 1037번] 약수 (Java 풀이)Algorithm/정렬(Sort) 2022. 5. 29. 11:16
백준알고리즘 1037번 : 약수 (Solved.ac 난이도 Silver5) https://www.acmicpc.net/problem/1037 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되 www.acmicpc.net 문제를 꼼꼼히 읽어야한다는 것을 다시한번 상기하게되었다. 얼핏 보고 나열된 숫자들의 최소공배수를 구하는 문제인 줄 알았는데, 나열된 약수들을 갖고 있는 숫자를 맞추는 문제였다. 양수 A가 정답이라면, A와 1은 약수로 치지않는다. 약수들의 목록을 오름차순으로 정렬하고, 최소 값과 최댓 값의 곱을 구해주면 간단하게 해..
-
[백준 2473번] 세 용액 (Java 풀이)Algorithm/정렬(Sort) 2022. 5. 6. 20:27
백준알고리즘 2473번 : 세 용액 (Solved.ac 난이도 Gold4) https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 숫자 3개를 선택하여 가장 절대값이 가장 작은 숫자를 만드는 조합을 출력하는 문제이다. 두개라면 two pointer를 사용하여 풀 수 있을꺼라 생각하였는데, 고민하다가 하나를 고정하는 대신 나머지 2개를 투 포인터로 fix하는 방법은 어떨까 생각해보았다. 물론 내가 작성한 logic은 중복으로 탐색하..
-
[백준 7453번] 합이 0인 네 정수 (Java 풀이)Algorithm/정렬(Sort) 2022. 4. 29. 13:07
백준알고리즘 7453번 : 합이 0인 네 정수 (Solved.ac 난이도 Gold2) https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 첫번째로 간과한 부분은 12초가 꽤 러프하다고 생각하여 단순 계산으로 시도해본 것이고, 두번째로 간과한 부분은 속도를 높이기 위해 투 포인터 방식을 사용했으나 동일한 연산에 대하여 곱셈이 아니라 덧셈으로 count를 해준 것이다. 예를들어 AxB 배열에 13이 3개, CxD 배열에 -13이 3개..
-
[백준 1082번] 배 (Java 풀이)Algorithm/정렬(Sort) 2022. 4. 15. 19:36
백준알고리즘 1082번 : 배 (Solved.ac 난이도 Gold5) 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 문제이다. 이 문제에서 크레인의 무게제한을 비중있게 생각할 필요는 없다. 무게가 많이 나가는 박스부터 옮기되 들수 있는 무게가 적은 크레인이라도 어느 하나의 박스라도 옮길 수 있도록 체크해주면 된다. 따라서 크레인과 박스를 내림차순으로 정렬하고 크레인 배열이 박스 배열을 돌면서 옮겨주면 된다. 옮긴 박스는 체크하고, 크레인 배열이 한 번 돌때마다 시간을 1씩 늘린다. https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000..
-
[백준 8979번] 올림픽 (Java 풀이)Algorithm/정렬(Sort) 2022. 4. 13. 21:19
백준알고리즘 8979번 : 올림픽 (Solved.ac 난이도 Silver5) 특정 국가의 올림픽 순위를 출력하는 문제이다. 금메달, 은메달, 동메달 총 3개의 값을 비교하여 적절한 순위를 출력한다. https://www.acmicpc.net/problem/8979 8979번: 올림픽 입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 www.acmicpc.net Comparator를 이용하여 2차원 배열의 3개 값을 비교하는 것 까지는 어렵지 않았으나, 동점일 경우에 순위를 확정지을수 있는 방법에 대한 고민이 필요했다. 결과적으로는 2차원..
-
[백준 3273번] 두 수의 합 (Java 풀이)Algorithm/정렬(Sort) 2022. 4. 12. 19:10
백준알고리즘 3273번 : 두 수의 합 (Solved.ac 난이도 Silver3) 더해서 자연수 x를 만족하는 쌍이 몇개 있는지 확인하는 문제이다. https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 처음에는 100만까지 숫자가 주어진다는 것을 확인하여 Int 배열의 크기를 100만으로 만들고, 받아온 숫자값에 1을 넣어서 숫자가 1이면 count한다, 라는 식으로 풀어보았다. 예제를 반영하자..
-
[백준 5052번] 전화번호 목록 (Java 풀이)Algorithm/정렬(Sort) 2022. 4. 11. 19:22
백준알고리즘 5052번 : 전화번호 목록 (Solved.ac 난이도 Gold4) 한 전화번호가 다른 전화번호의 접두어인 경우를 찾는 문제이다. String Type의 실수를 정렬하는 Case를 고민하여 풀 수 있다. ↑클릭시 문제 link로 이동합니다.😊 이 문제를 풀면서 발생한 애로사항 첫번째는 문제의 몰이해다. 문제에서 제시한 제한 조건은 하나의 전화번호가 다른 번호의 '접두어'만 아니여야한다는 것이다. 예를들어 번호 목록이 911과 911123이면 911이 911123의 접두어이므로 NO를 출력해야하는게 당연하나 나는 포함관계가 아니여야한다고 착각하여 911과 11911의 case에도 NO를 출력해야 한다고 판단하고 문제를 풀었다. (시간 초과가 계속 발생하여 틀린줄도 몰랐다..) 역시 소스를 짜기..
-
[백준 2470번] 두 용액 (Java 풀이)Algorithm/정렬(Sort) 2022. 4. 10. 19:25
백준알고리즘 2470번 : 두 용액 (Solved.ac 난이도 Gold5) 여러 용액 중 그 합의 절댓값이 가장 작은 두 용액을 찾아내는 문제이다. 2차원 배열로 값을 담아 for문을 한 번 돌면서 그 합이 가장 낮은 숫자 들을 찾는다. ↑클릭시 문제 link로 이동합니다.😊 시간 제한이 1초라서 이중 for문으로 돌리면 무조건 시간초과가 날 것 같았다. 그래서 떠올린 방법이 2차원 배열로 값을 담되, 값을 담으면서 음수는 미리 check해두는 것이다. 절댓값으로 정렬하고 난 뒤에 for문을 한번만 돌면서 i번째와 i+1번째 값을 비교한다. 이 두 숫자의 합이 가장 작은 경우를 찾는다. (절대값으로 처리된 숫자로는 정확한 합을 구할 수 없기 때문에 양/음수를 check해둔 값을 불러와서 실제 숫자를 호출..