[Java 기본 알고리즘] (4) 투 포인터

package TwoPointerBasic;

import java.util.HashMap;
import java.util.Map;

public class TwoPointer2 {
	public static void main(String[] args) {
		String s= "ccaabbb";
		System.out.println(solve_map(s));
	}
	
	//최대 2개의 고유 문자가 있는 가장 긴 부분 문자열
	//문제 해결
	

	public static int solve_map(String s) {
		//1. ds
		Map<Character, Integer> map = new HashMap<>();
		int l=0, r=0, counter=0, max=0;
		
		//2. for, while -> 이중 while문이 아니라, 2행 while문 -> O(n)
		while(r<s.length()) {	//문자열의 길이만큼 오른쪽길이가 증가
			char c=	s.charAt(r);	//cccaabb
			//Key, Value구조로 만들어서 counter=3일 떄를 기준으로 
			map.put(c,map.getOrDefault(c, 0)+1);	//기존의 map에 문자가 있으면 추가, 없으면 새로 만들기
			//c=2, a=2, b=1
			
			//카운터의 개수 구하기
			if(map.get(c)==1)
				counter++;	//3
			r++;
			
			//ccaa에서 b를 만났을 때 -> 카운터 설정 [고유 문자가 2개여야하므로]
			//즉, r이 1~4까지 동일하지만, r이 5인 순간부터
			
			while(counter>2) {
				//counter가 3일떄 c를 없애준다. -> counter를 2로 만들기
				char c2= s.charAt(l);		//left의 문자
				map.put(c2, map.get(c2)-1);	//c2의 value 두개중에 하나를 빼주도록
				if(map.get(c2)==0) {		//c가 두개이기 때문에 두번 돌아서 0이되는 순간에 counter를 감소시킨다.
					counter--;				//c가 없어졌기 떄문에 counter를 감소시킨다. counter=2
				}
				l++;						//left는 a로 보낸다.
			}
			max=Math.max(max, r-l);	//max와 r-l중 큰 값을 max에 저장
			System.out.println("r: "+r+" l:"+l+" "+(r-l));
		}
		return max;	

	}
	
}

 

 

package TwoPointerBasic;

import java.util.ArrayList;
import java.util.List;

public class TwoPointer3 {
	public static void main(String[] args) {
		TwoPointer3 a = new TwoPointer3();
		String s="bacdgabcda";
		String p="abcd";
		System.out.println(a.solve_array(s,p));	
	}
	//문자열에서 모든 아나그램 찾기
	//주어진 두 개의 문자열을 이용해 p의 문자열이 s의 문자열에 특정 인덱스에서부터 모든 아나그램을 찾아 인덱스 리턴
	//아나그램 : 순서에 상관없이 단어가 일치하는 문자
	
	//문제 해결
	//1. 찾고자 하는 문자열이 소스문자열에서 나오는 부분을 검색
	//2. 나오는 시점부터 모든 문자가 있는지 체크
	
	// 중복 지점 찾기 -> Map -> 찾고자 하는 문자열을 두고 -> while을 이용해 채우기
	
	//문제 해결 [1] -> Map을 이용하는 방법
	// 찾고자 하는 문자열을 Map에 넣어두고								-> counter =4 [찾고자 하는 문자열의 길이만큼]
	// 소스문자열에서 찾으면 value를 하나씩 줄인다 [value=0이 될 때 까지]   	-> counter =0
	//다 찾은 경우나 못 찾은 경우 while문을 돌려서 value를 채운다 [리셋]
	
	//문제 해결 [2] -> 배열을 이용한 키값 방법 [알파벳 26개 자리를 표시] [a가 아스키코드 97]
	//키값을 이용해 -> 0번방 -> 1번방 ...순으로 찾고자 하는 문자열의 길이만큼 뽑아내서 for문을 돌린다. 
	//4자리가 안되는 경우 -> 멈추게 -> for문 조건 설정
	//장점 map에 비해 빠른 속도, 공간복잡도도 낮다 -> O(1)
	public List<Integer> solve_array(String s, String p){
		//1. ds
		List<Integer> result=new ArrayList<>();
		if(s==null||s.length()==0||p==null ||p.length()==0) {
			return result;			
		}
		
		int[] pArr = new int[26];		//찾고자하는 문자열에 대한 키값을 위한 알파벳 배열 0번부터 25번까지
		for(int i=0; i<p.length(); i++) {
			pArr[p.charAt(i)-'a']++;	//26개 짜리 빈 배열에서 -> 문자열 p에 해당하는 알파벳 배열을 만들기 위해 a의 아스키코드값 97을 빼기
			//-> 들어올 때마다 증가시키기위해 증감 연산자 추가
		}	//고유한 키값 생성
		
		for(int i=0; i<s.length()-p.length()+1;i++)	{
			//9-4이지만 6까지 가야하기때문에 +1 [6번이 마지막으로, 찾고자하는 문자열을 체크할수있는 번호]
			int[] sArr = new int[26];	////소스문자열에 대한 키값을 위한 알파벳 배열 0번부터 25번까지
			for(int j=0; j<p.length(); j++) {
				//0번방
				System.out.println("i "+i+" j"+j);				
				sArr[s.charAt(i+j)-'a']++;	//0번방에 바깥의 for문 값을 더해준다. -> 채우기
				//즉, 0번방 -> 4개 체크, 1번방 -> 4개 체크하기 위해 i+j [i: 0번방,1번방 ..., j: 소스문자열의 키값 생성]
			}
		if(check (pArr,sArr)) {
			result.add(i);	//결괏값에 0,5,6을 추가
		}
		}
		return result;
	}

			
		//2. for, while
		//for (0번방, 1번방 ... ) -> for(소스 문자열에서 찾을 문자열 찾기) -> 키값의 배열과 같은지 체크check
		private boolean check(int[] pArr, int[] sArr) {
			for(int i=0; i<pArr.length; i++) {
				if(pArr[i]!=sArr[i]) {
					return false;
				}
			}
			return true;
		}
		
	
}