은비블로그

[백준] 2230 : 수 고르기 (JAVA)

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짜리 수열..