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..
Problem Solving/투포인터
이진탐색, 투 포인터로 다시 풀어보기 이진탐색 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..
https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net import java.util.*; import java.io.*; public class Main { public static int search(int[] numbers, int m){ int right = 0; int min_diff = 2_000_000_000; for(int left=0; left
https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net import java.util.*; import java.io.*; public class Main { public static int search(int[] acc, int s){ int right = 0; int sum_length=acc.length+1; for(int left=1; left
투 포인터 (주로) 선형 데이터 구조에서 두 개의 인덱스를 관리하여 특정 조건을 만족하는 부분집합이나 특정 값을 찾는 알고리즘 1. 두 포인터(인덱스)를 시작점(left=0, right=0 또는 left=0, right=마지막인덱스 또는 서로다른 배열 등)으로 초기화한다. 2. 규칙에 따라 포인터를 이동시킨다. - 같은 배열에서 동일한 방향으로 이동하는 투 포인터 - 같은 배열에서 마주보는 방향으로 좁혀가는 투 포인터 - 서로 다른 배열에서 이동하는 투 포인터 - 여러 형태에서 효율적인 시간 복잡도를 가진다. 3. 두 포인터 중 하나 혹은 둘 모두가 끝에 도달할 때까지 반복한다. * 인덱스가 아니더라도 오른쪽(시계방향), 왼쪽(반시계) 거리를 right, left로 둘 수 도 있다. https://yun..
소요시간: 40분 나의 정답코드 import collections def solution(gems): gemNum=len(set(gems)) lt=0 rt=0 selected = collections.defaultdict(int) answer=[0,1e9] selected[gems[lt]]+=1 while True: if len(selected)
