투포인터

📖 문제 https://www.acmicpc.net/problem/2531   💡  풀이 방식• 투 포인터1. 입력된 정보를 저장한다.  - int[N] sushi : 초밥 종류 저장 배열  - int[d+1] chk  :  초밥 각 종류가 몇 개 존재하는지 나타내는 배열 2. 투 포인터를 이용해 먹을 수 있는 최대 가짓수를 구한다.  1) 회전하지 않았을 때 초밥을 먹는다.  2)  N-1번 회전하며 탐색을 진행한다.      → [규칙] 처음 먹은 초밥은 제거하고, 마지막+1 번째 초밥은 추가한다.  🔺 코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152import java..

📖 문제 https://www.acmicpc.net/problem/20437   💡  풀이 방식• 슬라이딩 윈도우1. 입력받는 문자열 w의 알파벳 갯수를 센다.int[] alpha = new int[26];for(int i = 0 ; i  2. 입력받은 문자열을 돌면서 해당 문자의 갯수가 k개 이하라면 탐색을 종료한다.if(alpha[w.charAt(i) - 'a']  k개 이상이라면, 뒷 문자와 비교하며 같은 문자의 갯수를 센다.if(w.charAt(i) == w.charAt(j)) cnt++; 그리고 같은 문자가 k개가 되는 순간, 문제에서 요구하는 조건만큼의 문자를 포함하는 길이가 되었으므로min, max 값을 갱신한다.   🔺 코드1234567891011121314151617181920..

📖 문제 https://www.acmicpc.net/problem/2118   💡  풀이 방식• 누적합, 투 포인터 N가지 지점 中 2가지를 뽑는 경우의 수는 N * (N-1)/2이고, 이러면 약 12억 5천만을 넘으므로 시간 초과가 발생한다.그러므로 투 포인터로 두 지점을 뽑는다. 그리고 나서 정방향 / 역방향으로 진행하며 최대 거리를 구한다.   🔺 코드12345678910111213141516171819202122232425262728293031323334353637383940414243import java.util.*;import java.io.*; public class Main {    public static void main(String[] args) throws IOException..

🔺 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 import java.util.*; class Solution { public int[] solution(int[] sequence, int k) { int[] answer = new int[] {0, sequence.length - 1}; int left = 0; int right = 1; int sum = s..

🔺 문제 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { Buff..

🔺 문제 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 🔺 코드 1) 누적 합 풀이 - 시간 복잡도 : O(N) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { Bu..

🔺 문제 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException..

🔺 문제 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOExceptio..

🔺 문제 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { Buff..