은비블로그

https://www.acmicpc.net/problem/2467 [풀이과정]투포인터로 풀었다.0과 가까운 값을 갱신하는 것과 포인터 위치를 변경하는 것의 조건을 각기 다르게 둬야 했는데, 한 번에 처리해서 틀렸다. [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;/*산성 용액 특성값 1 ~ 10억알칼리성 용액 특성값 -10억 ~ -1두 용액을 혼합하여 0에 가장 가까운 용액 만들기 */public class Main { static BufferedReader br = new Bu..

https://www.acmicpc.net/problem/14921 [풀이과정]완탐으로 하기엔 N이 10만이어서 불가능했다.O(N)의 투포인터로 구현했음.일단 오름차순으로 나열한 후 양끝의 값들을 비교하며 0과의 차이가 가장 적은 걸 찾아줬다.이때 더한 값이 음수라면 오른쪽 포인터를 이동시켜줬고, 양수라면 왼쪽 포인터를 이동시켜줬다.0과의 차이는 절댓값으로 비교해줘야 했지만 실제 출력되는 것은 음수인지 양수인지도 표기해야 했으므로 비교만 절댓값으로 해줬다. [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.Strin..

https://www.acmicpc.net/problem/2230 [풀이과정]처음 코드는 완전탐색으로 O(N^2)여서 시간초과가 났다.투포인터를 사용해서 풀었는데, 먼저 배열을 정렬한 후 계산을 하는 방식이다.정렬된 상태에서 두 수의 차이를 구하면 이후의 차이가 현재 차이보다 크단 걸 알 수 있으니 넘겨서 더 큰 수끼리 비교하면 된다.배열 정렬 O(N logN) + 투포인터 탐색 O(N)으로 전체 시간복잡도는 O(N logN)임. 이분탐색으로도 풀 수 있고 이분탐색 풀이도 O(N logN)이다. [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;..

https://www.acmicpc.net/problem/1806 [문제풀이]처음엔 왼쪽 포인터와 오른쪽 포인터가 가리키는 두 수 중 더 작은 수를 빼주며 최소길이를 구하려고 했다.하지만 S 이상의 부분합을 전부 볼 수 없다는 문제점이 있었다.그래서 왼쪽과 오른쪽 포인터를 0에서 시작하여 오른쪽만 움직이다가 부분합이 S 이상이 되면 왼쪽 포인터가 가리키는 값을 빼준 왼쪽 포인터를 오른쪽으로 한 칸 옮기는 방식을 구현하였다. [정답]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;/*10,000 이하의 자연수로 이루어진 길이 N짜리 수열..