문제 링크 https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 풀이 - 시간복잡도 O(NlogN) = 정렬 O(NlogN) 후 투 포인터 O(N) 수행 - Integer 범위 내이긴 하지만, 초기화시 일부 long 선언 처리 - M 만큼의 차이가 날 때까지 R을 먼저 탐색, A[R] - A[L] > M 조건 성립시 결과값 갱신 (최소값) 제출 코드 import java.util.*; import java.io.*; public ..

문제 링크 https://www.acmicpc.net/problem/15565 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 풀이 - 시간복잡도 O(N) - 1 (라이언 인형) 인 경우에만 카운팅 처리를 해주고, K개이상이 되는 연속된 인형의 집합의 길이는 L, R범위로 측정 제출 코드 import java.util.*; import java.io.*; public class Main { static int N, K; static int[] A; static void input() throws Excep..

문제 링크 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 풀이 - 정렬 후 투 포인터 로직 수행 - 시간 복잡도 : O(NlogN) - 배열 순차적으로 순회하여 기준 값과 나머지 영역에서 투 포인터로 두 값을 정하고 다 더했을 때 0에 가까운 최대 값을 구하면 됨 참고 [BOJ 2470] 두용액 (Java, 투 포인터) [BOJ 1253] 좋다 (Java, 투 포인터) 제출 코드 - 입력 배열 A 의 데이터 타입을 lon..

문제 링크 https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 풀이 - 알파벳(26자) 카운팅 배열을 활용하여 투포인터 문제 풀이 - 시간복잡도는 O(N) *알파벳 인덱스 구하기 int index = TEXT.char(i) - 'a'; 제출 코드 import java.util.*; import java.io.*; public class Main { static int N, CNT; static String TEXT; static int[] ALPHABET ..

문제 링크 https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 풀이 - 두 용액 문제 풀이 방법을 응용하여 풀이 - 시간 복잡도 O(NlogN) - 순차 조회하면서 해당 값을 다른 두 수의 합으로 만들 수 있는지 확인 (이때 탐색과정에서 자기자신의 경우 제외, targetIdx) 제출 코드 import java.util.*; import java.io.*; public class Main { static int N; static int[] A; static void input..

문제 링크 https://www.acmicpc.net/problem/13144 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net 풀이 - 투 포인트 기법과 카운팅 배열을 활용하여 1 ~ N 까지의 모든 경우의 수 합을 더하면 됨 - 시간복잡도 O(N) 이때 최대값의 경우 1 2 3 ... 100,000 1 2 3 ... 100,000 1 ~ 100,000까지의 합을 나타내기 때문에 100000(99999) / 2 = 대략 50억이기 때문에 long으로 풀이 해야 함 L = 1인 경우 100,000 L = 2인 경우 99..

문제 링크 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 - 투 포인터 문제 - 시간 복잡도 O(N) - 정답의 최대 길이는 100,000 , 구하려는 S의 최대는 10^9 이므로 Integer로 풀이 가능 제출 코드 import java.util.*; import java.io.*; public class Main { static int N, S; static int[] NUMBERS; static void input()..

문제 링크 https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 풀이 - 투 포인터로 문제 풀이 (이진탐색으로 풀이 가능하나 개념적으로 조금 어려움) - 두 용액을 더 했을 때 0에 가까운 두 수를 구하는 문제 - 양 끝에서 투 포인터를 시작해서 서로를 향해 이동 - sum 의 값이 양수인 경우 R을 감소, 음수인 경우 L을 증가 0 1 2 3 4 -99 -2 -1 4 98 -99, 98 = -1 이므로 L증가 -2..