투 포인터스
제로베이스 7월 기업 코테 라이브 특강 / 김태원
투 포인터스 알고리즘
투 포인터스 알고리즘(Two Pointers Algorithm)은 두 개의 포인터를 사용하여 배열이나 문자열과 같은 데이터 구조를 탐색하는 기법입니다. 이 알고리즘은 주로 순차적으로 데이터를 처리하거나 특정 조건을 만족하는 부분 배열이나 부분 문자열을 찾는 데 사용됩니다. 투 포인터스 알고리즘은 특히 정렬된 배열이나 리스트에서 유용합니다.
투 포인터스 알고리즘의 주요 아이디어
- 포인터 초기화: 두 개의 포인터를 배열이나 문자열의 시작과 끝에 배치합니다.
- 포인터 이동: 두 포인터를 특정 조건에 따라 이동시키며 데이터를 처리합니다. 일반적으로 왼쪽 포인터는 오른쪽으로, 오른쪽 포인터는 왼쪽으로 이동합니다.
- 조건 검사: 각 이동 단계에서 포인터가 가리키는 요소를 검사하고 필요한 연산을 수행합니다.
예제: 두 수의 합 (Two Sum)
문제
정렬된 배열에서 두 수의 합이 특정 값이 되는 두 수의 인덱스를 찾으시오.
접근법
- 브루트 포스 접근법
- 모든 가능한 두 수의 조합을 계산하여 합이 특정 값이 되는 경우를 찾습니다. 시간 복잡도는 O(n^2)입니다.
- 투 포인터스 접근법
- 배열이 정렬되어 있으므로, 두 포인터를 사용하여 합이 특정 값이 되는 두 수를 효율적으로 찾습니다. 시간 복잡도는 O(n)입니다.
코드 구현 (Java)
import java.util.*;
class Main {
public int[] solution(int[] nums, int target) {
int[] answer = new int[2];
int left = 0;
int right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) return new int[]{left, right};
else if (sum < target) left++;
else right--;
}
return answer;
}
public static void main(String[] args) {
Main T = new Main();
System.out.println(Arrays.toString(T.solution(new int[]{2, 3, 7, 8, 9, 12, 15}, 12)));
}
}
설명
- 포인터 초기화: 왼쪽 포인터를 배열의 시작에, 오른쪽 포인터를 배열의 끝에 배치합니다.
- 포인터 이동: 두 포인터가 가리키는 요소의 합이
target과 같은지 검사합니다. 합이target보다 작으면 왼쪽 포인터를 오른쪽으로 이동시키고, 합이target보다 크면 오른쪽 포인터를 왼쪽으로 이동시킵니다. - 조건 만족 시 반환: 합이
target과 같으면 해당 인덱스를 반환합니다. - 최종 결과: 조건을 만족하는 두 수의 인덱스를 반환합니다. 만족하는 경우가 없으면 초기화된
answer배열을 반환합니다.
이 알고리즘은 정렬된 배열에서 두 수의 합을 찾는 데 매우 효율적이며, 시간 복잡도는 O(n)입니다.
두 수의 합 다른 코드
import java.util.*;
public class Main {
public int[] solution(int[] nums, int target) {
int[] answer = new int[2];
int n = nums.length;
int y = 0;
HashMap<Integer, Integer> nH = new HashMap<>();
for(int i = 0; i < n; i++){
y = target - nums[i];
if(nH.containsKey(y)) return new int[]{nH.get(y), i};
nH.put(nums[i], i);
}
return answer;
}
public static void main(String[] args) {
Main T = new Main();
System.out.println(Arrays.toString(T.solution(new int[]{3, 7, 2, 12, 9, 15, 8}, 12)));
System.out.println(Arrays.toString(T.solution(new int[]{21, 12, 30, 15, 6, 2, 9, 19, 14}, 24)));
System.out.println(Arrays.toString(T.solution(new int[]{12, 18, 5, 8, 21, 27, 22, 25, 16, 2}, 28)));
}
}
answer: 두 수의 인덱스를 저장할 배열. n: 배열 nums의 길이. y: 현재 수 nums[i]와 합이 target이 되기 위해 필요한 수. nH: 수와 해당 수의 인덱스를 저장할 해시맵.
배열 nums를 순회하며, y = target - nums[i]로 현재 수 nums[i]와 합이 target이 되기 위해 필요한 수 y를 계산합니다. nH에 y가 이미 존재하는지 확인합니다. 존재한다면, y와 현재 수 nums[i]의 합이 target이 되므로 두 수의 인덱스를 반환합니다. nH에 nums[i]와 해당 인덱스를 추가합니다.
두 수의 합이 target이 되는 경우를 찾지 못하면 초기화된 answer 배열을 반환합니다.
연습문제
n번째 작은 학생
import java.util.*;
class Main {
public int solution(int[] a, int[] b){
int answer = 0;
int n = a.length;
int p1 = 0, p2 = 0;
for(int i = 1; i < n; i++){
if(a[p1] < b[p2]){
p1++;
}
else p2++;
}
answer = Math.min(a[p1], b[p2]);
return answer;
}
public static void main(String[] args){
Main T = new Main();
Scanner kb = new Scanner(System.in);
int[] a = new int[]{163, 165, 168, 172, 178, 183, 189};
int[] b = new int[]{164, 170, 171, 178, 180, 188, 190};
System.out.println(T.solution(a, b));
}
}
두 배열의 병합을 이용한 풀이
import java.util.*;
class Main {
public int solution(int[] a, int[] b){
int n = a.length;
int[] answer = new int[n*2];
int p1 = 0, p2 = 0, p3 = 0;
while(p1 < n && p2 < n){
if(a[p1] < b[p2]) answer[p3++] = a[p1++];
else answer[p3++] = b[p2++];
}
while(p1 < n) answer[p3++] = a[p1++];
while(p2 < n) answer[p3++] = b[p2++];
//for(int x : answer) System.out.println(x);
return answer[n-1];
}
public static void main(String[] args){
Main T = new Main();
Scanner kb = new Scanner(System.in);
int[] a = new int[]{163, 165, 168, 172, 178, 183, 189};
int[] b = new int[]{164, 170, 171, 178, 180, 188, 190};
System.out.println(T.solution(a, b));
}
}
회문 문자열
import java.util.*;
class Main {
public String solution(String s){
String answer = "YES";
s = s.toUpperCase();
int left = 0;
int right = s.length()-1;
while(left < right){
if(s.charAt(left) != s.charAt(right)) return "NO";
else{
left++;
right--;
}
}
return answer;
}
public static void main(String[] args){
Main T = new Main();
System.out.println(T.solution("AbceCBa"));
System.out.println(T.solution("BtoMnoTb"));
}
}
import java.util.*;
class Main {
public String solution(String s){
String answer="NO";
String tmp=new StringBuilder(s).reverse().toString();
if(s.equalsIgnoreCase(tmp)) answer="YES";
return answer;
}
public static void main(String[] args){
Main T = new Main();
System.out.println(T.solution("gooG"));
System.out.println(T.solution("Moon"));
}
}
import java.util.*;
class Main {
public boolean isPalindrome(String s){
int left = 0;
int right = s.length() - 1;
while(left < right){
if(s.charAt(left) != s.charAt(right)) return false;
else{
left++;
right--;
}
}
return true;
}
public String solution(String s){
String answer = "YES";
int left = 0;
int right = s.length()-1;
while(left < right){
if(s.charAt(left) != s.charAt(right)){
String s1 = s.substring(left, right);
String s2 = s.substring(left+1, right+1);
if(!isPalindrome(s1) && !isPalindrome(s2)) return "NO";
else break; //return "YES";
}
else{
left++;
right--;
}
}
return answer;
}
public static void main(String[] args){
Main T = new Main();
System.out.println(T.solution("abcbdcba"));
System.out.println(T.solution("abcabbakcba"));
System.out.println(T.solution("abcacbakcba"));
}
}
Leave a comment