두 포인터7 [백준]3151: 합이 0 - JAVA https://www.acmicpc.net/problem/3151 풀이N개의 숫자들 중 3개를 선택하여 그들의 합을 0으로 만드는 경우의 수를 찾는 문제이다. 배열에 숫자들을 저장하여 정렬한다. 첫 번째 숫자를 선택하고, 그 다음 숫자를 left, 배열의 끝 숫자를 right로 놓고 left와 right를 조정하여 합이 0이 되는 수를 찾는다. 선택한 숫자를 node라고 할 때, `node + arr[left] + arr[right]` 가 0이 되는 경우를 찾아 정답을 증가시킨다. `arr[left]` 와 `arr[right]`가 같은 경우에는 left부터 right까지의 수가 n개라고 할 때 nC2의 조합을 구하는 것과 같다. 처음 선택한 수를 0부터 시작하여 증가시키면서 값이 0보다 커질 때까지 실행.. 2024. 9. 3. [백준] 14527: Paired Up - JAVA https://www.acmicpc.net/problem/14527 풀이소들의 수와 milk output이 주어진다. milk output을 기준으로 정렬했다. 투포인터를 이용하여 양쪽에서 가운데를 향해 가면서 소의 수를 감소시키고, 0이되면 다음으로 넘어간다. 이때 milk output의 합을 정답에 갱신하면 되는 문제였다. 메모리: 46184KB시간: 3044ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStream.. 2024. 6. 10. [백준] 16472: 고냥이 - JAVA https://www.acmicpc.net/problem/16472 풀이문자열을 최대 N개 종류의 알파벳을 가진 문자열로 잘라야한다. abbcaccba 라는 문자열을 최대 2개 종류의 알파벳을 가진 문자열로 자르면 cacc 일때 길이가 4로 최대가 된다. 알파벳의 개수를 int 배열을 통해 저장하고, 새로운 알파벳이 나올 때마다 cnt를 늘려가면서 탐색한다. 이때 탐색은 투포인터 알고리즘으로 한다. cnt가 n보다 크면 left를 1늘려서 문자열의 길이를 줄이고, cnt가 n보다 작거나 같다면 right를 1늘려서 문자열의 길이를 늘린다. 메모리: 15492KB시간: 160ms언어: Java 11import java.io.*;public class Main { public static void m.. 2024. 5. 29. [백준] 2230: 수 고르기 - JAVA https://www.acmicpc.net/problem/2230 풀이n개의 정수가 주어지고, 두 수를 골랐을 때 차이가 m 이상인 경우 중 제일 작은 경우를 골라야 한다. 정렬을 해놓고 슬라이딩윈도우를 통해 두 수를 골라 차이를 비교했다. start, end 이렇게 두 포인터를 두고 두 수의 차이가 m보다 작은 경우 end를 1 늘린다. 두 수의 차이가 큰 경우 정답을 갱신하고 start를 1늘린다. 메모리: 28584KB시간: 396ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedRead.. 2024. 5. 19. [백준] 13144: List of Unique Numbers - JAVA https://www.acmicpc.net/problem/13144 풀이길이 N의 수열에서 연속한 1개 이상의 수을 뽑았을 때 같은 수가 여러번 등장하지 않는 경우의 수를 구해야 한다. 처음에는 첫번째 원소부터 시작하여 dfs탐색을 통해 구하려고 했었다. 방문체크는 비트마스킹을 이용할 계획이었다. 하지만 N의 범위와 숫자들의 범위가 커서 안되는 것을 깨달았다. 따라서 투포인터 알고리즘을 떠올렸다. start, end를 0에서 부터 시작하여 방문처리를 하면서 end값을 증가시킨다. 이전에 나온 숫자가 나올때까지 end값을 증가시키고 ans에 end - start를 더해준다. 현재 start값에 대한 경우의 수를 구했으므로 현재 start값의 방문처리를 지우고 start값을 1늘려 다시 판단한다. 메모리:.. 2024. 5. 17. [백준] 20922: 겹치는 건 싫어 - JAVA https://www.acmicpc.net/problem/20922 풀이같은 원소가 K개 이하로 들어있는 최장 연속 부분 수열의 길이를 구해야한다. 원소의 개수를 세줄 배열을 만들어놓고 0부터 시작하여 원소의 개수를 세준다. i번째 원소의 개수가 K개보다 크다면 start부터 시작하여 i번쨰 원소와 같은 원소가 나올때까지 count 배열에서 하나씩 빼준다. `(i - start + 1)` 이 조건을 만족하는 부분 수열의 길이이다. 최댓값과 비교하여 갱신해준다. 메모리: 32740KB시간: 360ms언어: Java 11import java.util.*;import java.io.*;public class Main { public static void main(String[] args) throws .. 2024. 5. 17. [백준] 15961: 회전 초밥 - JAVA https://www.acmicpc.net/problem/15961 풀이슬라이딩 윈도우를 사용해서 카운트하는 문제였다. 회전 초밥을 연속에서 k개 먹어야하는데 최대한 다양한 종류를 먹으려고 한다. 쿠폰이 하나 주어지고 쿠폰에 적혀진 종류의 초밥을 먹지 않았으면 하나 제공해 준다. 즉, 가장 다양하게 먹으려면 연속된 k개에서 다 다른 초밥을 먹고 쿠폰에 있는 초밥을 제공받아 먹어야 한다. int로 먹은 것을 체크하는 배열을 만들었다. left는 0, right는 k-1부터 시작하여 1씩 늘리면서 체크해준다. 체크 배열에 쿠폰에 있는 초밥이 없으면 bonus를 1로 해주고 cnt + bonus의 최댓값이 정답이 된다. 메모리: 170972KB시간: 548ms언어: Java 11import java.io.*.. 2024. 5. 13. 이전 1 다음