728x90 반응형 투포인터3 [백준/java] 1644번: 소수의 연속합 - 투 포인터 + 에라스토테네스의 체 에라스토테네스의 체를 이용하여 소수를 먼저 구하고, 투 포인터로 소수의 합이 N과 일치할 때 정답의 개수를 구하는 문제이다. 예외처리를 잘해주지 않으면 틀리는 문제이다. 단순히 투포인터 문제라 두개의 점으로 시작하는 방식으로 구현했었다. 소수가 2, 3, 5, 7... 소수를 두개로 시작하면 2, 3부터이니 solution 메서드의 두번째 for문의 rt를 1부터 순회하였다. 그렇게되면 N이 2일 때, for문은 answer를 증가하지 않는다. 그리고 N이 1이면 0을 리턴해줘야하는데, int lt = 0, sum = list.get(lt);를 하게 되면 소수가 2부터 시작하므로 1 이하로 존재하는 소수가 없다. 그러므로 n = 1일때, lt = list.get(lt); 를 하게 되면 IndexOutOf.. 2021. 9. 24. [백준/java] 2470번: 두 용액 - 투 포인터 값을 입력받을 때, 처음에 Scanner를 이용했었다가 시간초과가 4번정도 떴었다. BufferedReader로 바꾼 후에도 시간초과가 뜨길래 정렬 방식에서 문제가 있나 싶었다. 입력되는 값이 너무 크다보니 범위가 커져서 Arrays.sort()의 경우 최악의 경우는 O(N^2)까지 가는 경우도 있으니 ArrayList로 입력을 받아서 Collections.sort()로 정렬하면 수행시간이 O(N log N)이 보장되기 때문에 리스트로 입력받는 방법을 선택했다. 그리고 두 포인터 인덱스의 값의 합이 0일 때는 해당 인덱스들을 출력해야하기 때문에 두 포인터를 좁혀나가는 로직에서 break를 걸어주어야 한다. package twoPointer; import java.io.BufferedReader; impo.. 2021. 9. 24. [백준/java] 1806번: 부분합 - 투 포인터 활용 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 코딩테스트 강의를 들으며 투 포인터를 익혔다. 강의에서도 부분수열의 합에 대해서 다뤘었는데 확실히 개념을 익히고 나니까 이번 문제를 풀 수있었다. https://www.inflearn.com/course/%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%9.. 2021. 9. 10. 이전 1 다음 728x90 반응형
