투 포인터
배열에서 두개의 포인터를 사용하여 원하는 결과를 얻는 방법
두개의 포인터의 배치 방법
같은 방향에서 시작: 첫번째 원소에 둘다 배치서로 다른 방향에서 시작: 첫번재 원소와 마지막 원소에 배치
다중 for 문의 복잡도를 좀 더 선형적으로 풀수 있음
예를 들어 아래 배열에서 부분합이 9가 되는 구간을 찾는 방법
위 경우 worst case에서 알고리즘 복잡도 n^2
포인터를 맨 앞에 두개 배치
처음 p1포인터를 옮기면서 부분합을 계산하다가 11인 경우 9보다 크기 때문에 이때 p2를 한칸 앞으로 옮김
이후 p2포인터를 옮기면서 넘어온 값 11로 숫자들을 빼봄
-> 8이 되는 순간 부분합보다 작아지기에 다시 P1을 옮김
worst case여도 복잡도가 2N이 됨
구현 예시
import java.util.Arrays;
public class Main {
public static int[] forLoop(int[] arr, int target){
int[] result = {-1, -1};
for (int i = 0; i < arr.length; i++) {
int sum = arr[i];
for (int j = i+1; j < arr.length; j++) {
if(sum == target){
result[0] = i;
result[1] = j-1;
break;
}
sum += arr[j];
}
if(sum == target){
break;
}
}
return result;
}
public static int[] twoPointers(int[] arr, int target){
int p1 = 0;
int p2 = 0;
int sum = 0;
int[] result = {-1,-1};
while(true){
if(sum > target){
sum -= arr[p2++];
}else if(p1 == arr.length){
break;
}else{
sum += arr[p1++];
}
if(sum == target){
result[0] = p2;
result[1] = p1 - 1;
break;
}
}
return result;
}
public static void main(String[] args) {
int[] arr = {1,2,5,3,7,2,4,3,2};
System.out.println(Arrays.toString(forLoop(arr, 9)));
System.out.println(Arrays.toString(forLoop(arr, 14)));
System.out.println();
System.out.println(Arrays.toString(twoPointers(arr, 9)));
System.out.println(Arrays.toString(twoPointers(arr,14)));
}
}연습 문제
문제1
// Practice
// a, b, c, d 로 이루어진 알파벳 문자열에 대해서
// 다음과 같은 규칙으로 문자열을 정리한 후 남은 문자열을 반환하는 프로그램을 작성하세요.
// 양쪽의 문자를 비교한 후 같으면 삭제하는데, 연속해서 같은 문자가 등장하면 함께 삭제한다.
// 최종적으로 남은 문자열을 반환하세요.
// 입출력 예시
// 입력 s: "ab"
// 출력: "ab"
// 입력 s: "aaabbaa"
// 출력: (없음)
public class Practice1 {
public static String solution(String s) {
if(s == null || s.length() == 0){
return null;
}
int p1 = 0;
int p2 = s.length()-1;
while(p1 < p2 && s.charAt(p1) == s.charAt(p2)){
char c = s.charAt(p2);
while(p1 <= p2 && s.charAt(p1) == c){
p1++;
}
while(p1 <= p2 && s.charAt(p2) == c){
p2--;
}
}
return s.substring(p1, p2 + 1);
}
public static void main(String[] args) {
// Test code
System.out.println(solution("ab")); // ab
System.out.println(solution("aaabbaa")); //
System.out.println(solution("aabcddba")); // cdd
}
}문제2
// Practice
// nums1 과 nums2 두 배열이 주어졌을 때
// 두 배열의 공통 원소를 배열로 반환하는 프로그램을 작성하세요.
// 결과 배열의 원소에는 중복 값이 없도록 하며 순서는 상관 없다.
// 입출력 예시
// nums1: 1, 2, 2, 1
// nums2: 2, 2
// 출력: 2
// nums1: 4, 9, 5
// nums2: 9, 4, 9, 8, 4
// 출력: 4, 9 (or 9, 4)
import java.util.Arrays;
import java.util.HashSet;
public class Practice2 {
public static int[] solution(int[] nums1, int[] nums2) {
HashSet<Integer> set = new HashSet<>();
Arrays.sort(nums1); Arrays.sort(nums2);
int p1 = 0; int p2 = 0;
while(p1 < nums1.length && p2 < nums2.length){
if(nums1[p1] < nums2[p2]){
p1++;
}else if(nums1[p1] > nums2[p2]){
p2++;
}else{
set.add(nums1[p1]);
p1++;
p2++;
}
}
int[] result = new int[set.size()];
int idx = 0;
for(Integer n : set){
result[idx++] = n;
}
return result;
}
public static void main(String[] args) {
// Test code
int[] nums1 = {1, 2, 2, 1};
int[] nums2 = {2, 2};
System.out.println(Arrays.toString(solution(nums1, nums2)));
nums1 = new int[]{4, 9, 5};
nums2 = new int[]{9, 4, 9, 8, 4};
System.out.println(Arrays.toString(solution(nums1, nums2)));
nums1 = new int[]{1, 7, 4, 9};
nums2 = new int[]{7, 9};
System.out.println(Arrays.toString(solution(nums1, nums2)));
}
}문제 3
// Practice
// 문자열 s 를 거꾸로 출력하는 프로그램을 작성하세요.
// 단, 각 단어의 알파벳 순서는 그대로 출력합니다.
// 문장에 공백이 여러개일 시, 단어와 단어 사이 하나의 공백을 제외한 나머지 공백은 제거하세요.
// 입출력 예시
// 문자열 s: "the sky is blue"
// 출력: "blue is sky the"
// 문자열 s: " hello java "
// 출력: "java hello"
public class Practice3 {
public static String solution(String s) {
if(s == null){
return null;
}
if(s.length() < 2){
return s;
}
s = removeSpaces(s);
char[] cArr = s.toCharArray();
reverseString(cArr, 0, s.length() - 1);
reverseWords(cArr, s.length());
return new String(cArr);
}
public static String removeSpaces(String s) {
int p1 = 0;
int p2 = 0;
char[] cArr = s.toCharArray();
int length = s.length();
while (p2 < length) {
// 단어 앞 쪽 공백 skip
while (p2 < length && cArr[p2] == ' ') {
p2++;
}
// 공백 아닌 경우 해당 문자로 채워넣기
while (p2 < length && cArr[p2] != ' ') {
cArr[p1++] = cArr[p2++];
}
// 단어 뒤쪽 공백 skip
while (p2 < length && cArr[p2] == ' ') {
p2++;
}
// 단어와 단어 사이 공백 하나는 추가
if (p2 < length) {
cArr[p1++] = ' ';
}
}
// 공백 정리해서 앞쪽부터 채워넣은 부분 문자열 반환
return new String(cArr).substring(0, p1);
}
public static void reverseString(char[] cArr, int i, int j) {
while (i < j) {
char tmp = cArr[i];
cArr[i++] = cArr[j];
cArr[j--] = tmp;
}
}
public static void reverseWords(char[] cArr, int length) {
int p1 = 0;
int p2 = 0;
while (p1 < length) {
// p1, p2 로 공백 제외 단어 부분 시작, 끝 설정
while (p1 < p2 || p1 < length && cArr[p1] == ' ') {
p1++;
}
while (p2 < p1 || p2 < length && cArr[p2] != ' ') {
p2++;
}
reverseString(cArr, p1, p2 - 1);
}
}
public static void main(String[] args) {
// Test code
System.out.println(solution("the sky is blue"));
System.out.println(solution(" hello java "));
}
}문제 4
// Practice
// 주어진 nums 배열에서 3 개의 합이 0이 되는 모든 숫자들을 출력하세요.
// 중복된 숫자 셋은 제외하고 출력하세요.
// 입출력 예시
// nums: {-1, 0, 1, 2, -1, -4};
// 출력: [[-1, -1, 2], [-1, 0, 1]]
// nums: {1, -7, 6, 3, 5, 2}
// 출력: [[-7, 1, 6], [-7, 2, 5]]
import java.util.ArrayList;
import java.util.Arrays;
public class Practice4 {
public static ArrayList<ArrayList<Integer>> solution(int[] nums) {
Arrays.sort(nums);
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
for(int i = 0; i < nums.length - 2; i++){
if(i == 0 || i > 0 && nums[i] != nums[i-1]){
int p1 = i + 1;
int p2 = nums.length - 1;
int sum = 0 - nums[i];
while(p1 < p2){
if(nums[p1] + nums[p2] == sum){
result.add(new ArrayList<>(Arrays.asList(nums[i], nums[p1], nums[p2])));
while(p1 < p2 && nums[p1] == nums[p1+1]){
p1++;
}
while(p1 < p2 && nums[p2] == nums[p2-1]){
p2--;
}
p1++;
p2--;
}else if(nums[p1] + nums[p2] < sum){
p1++;
}else{
p2--;
}
}
}
}
return result;
}
public static void main(String[] args) {
// Test code
int[] nums = {-1, 0, 1, 2, -1, -4}; // [[-1, -1, 2], [-1, 0, 1]]
System.out.println(solution(nums));
nums = new int[] {1, -7, 6, 3, 5, 2}; // [[-7, 1, 6], [-7, 2, 5]]
System.out.println(solution(nums));
}
}
Journey for Backend Developer