슬라이딩 윈도우란 투포인터 알고리즘의 일종으로 볼 수 있다. 배열의 구간을 훑지만 일정 구간씩 보는 것이다. 0000000000000000 배열이 있을 때 XXX0000000000000 0XXX000000000000 00XXX00000000000 000XXX0000000000 위와 같은 방식으로 일정 구간씩 훌는 것이다. 갯수 세기에 주로 쓰인다. https://www.acmicpc.net/problem/14465 14465번: 소가 길을 건너간 이유 5 첫 줄에 N, K, B (1 ≤ B,K ≤ N)가 주어진다. 그 다음 B줄에는 고장난 신호등의 번호가 하나씩 주어진다. www.acmicpc.net 슬라이딩 윈도우 방식 import java.util.*; import java.io.*; public c..
Problem Solving
https://www.acmicpc.net/problem/14465 14465번: 소가 길을 건너간 이유 5 첫 줄에 N, K, B (1 ≤ B,K ≤ N)가 주어진다. 그 다음 B줄에는 고장난 신호등의 번호가 하나씩 주어진다. www.acmicpc.net 이문제는 투포인터( 슬라이딩 윈도우) 또는 누적합을 이용하여 풀 수 있다. 슬라이딩 윈도우 방식 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] ..
https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine..
https://www.acmicpc.net/problem/15831 15831번: 준표의 조약돌 첫 줄에 조약돌의 총 개수 N, 준표가 원하는 검은 조약돌의 최대개수 B와 하얀 조약돌의 최소개수 W가 주어진다. 둘째 줄에는 N개의 조약돌의 정보가 한 줄로 주어진다. i번째 문자가 B라면 i번 조 www.acmicpc.net import java.util.*; import java.io.*; public class Main { public static int solution(String word, int n , int w , int b){ int right=0; int b_count=0; int w_count=0; int ans=0; for(int left=0; left
https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net import java.util.*; import java.io.*; public class Main { public static boolean isPalindrome(String word, int left, int right,boolean is_remove){ while(left
https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWri..
이진탐색, 투 포인터로 다시 풀어보기 이진탐색 NlogN 투 포인터 N 누적합 N^2 https://www.acmicpc.net/problem/2118 2118번: 두 개의 탑 첫째 줄에 지점의 개수 N(2 ≤ N ≤ 50,000)이 주어진다. 다음 N개의 줄에는 차례로 두 지점 사이의 거리가 양의 정수로 주어진다. 전체 거리의 총 합은 1,000,000,000을 넘지 않는다. www.acmicpc.net 환형구조에서 반대쪽으로의 거리를 구할려면 전체 거리 - 순방향 거리를 하면 된다. 투포인터 문제이지만 나는 N2 복잡도인 누적합으로 해결하였다. 환형구조의 경우 선형자료형에 저장하기 위해 모듈러(%)를 사용하여 인덱스를 관리해 주어야 한다. 상황에 따라 그냥 배열을 두배로 늘리고 모듈러를 사용하지 않는..
https://www.acmicpc.net/problem/12891 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 해쉬맵을 쓰거나 문자열을 인덱스로 변환해주는 메소드를 만들어서 사용하면 된다. left와 right사이의 거리가 일정한 문제이다. import java.util.*; import java.io.*; public class Main { public static HashMap std = new HashMap(); public static int s; public static i..
