Yong's Tech Story

문제 풀이 (JAVA)

import java.io.*;
import java.util.*;
public class part4_4 {

	public static void main(String[] args) throws IOException {
		// 모든 아나그램 찾기
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String a = br.readLine();
		String b = br.readLine();
		int answer = solution(a.toCharArray(), b.toCharArray());
		
		bw.write(Integer.toString(answer));
		bw.flush();
		bw.close();
		
	}
	private static int solution(char []  a , char [] b) {
		int result=0;
		int lt=0, rt=0;
		int len = a.length;

		HashMap<Character,Integer> map1 = new HashMap<>();
		HashMap<Character,Integer> map2 = new HashMap<>();		
		for(Character ch : b) {
			map2.put(ch, map2.getOrDefault(ch,0)+1);
		}
		while(lt < len && rt < len) {
			if((rt-lt) == b.length) { // T의 문자열 길이와 슬라이딩윈도우 크기가 같다면		
				if(map2.equals(map1)== true) { // 해쉬맵이 같을시 동일하므로 결과값 증가
					result++;
				}
				if(map1.containsKey(a[lt])) { // 슬라이딩 윈도우 해시맵에 키가 존재한다면 -1 
					map1.put(a[lt], map1.getOrDefault(a[lt], 0)-1);
					if( map1.get(a[lt]) == 0) { // 왼쪽 인덱스 제거 후 0이라면 중복값x 
						map1.remove(a[lt]); // 해당 왼쪽 인덱스 값 제거
					}
				}
				lt++;
				if(rt==len-1) { // rt가 마지막 인덱스에 왔을때 처리문
					if(map2.containsKey(a[rt])) {
						map1.put(a[rt], map1.getOrDefault(a[rt], 0)+1);
					}
					if(map2.equals(map1)== true) {
						result++;
					}
					rt++; // while문 종료
				}				
			}			
			if((rt-lt) < b.length) { // 인덱스가 T의 길이만큼이 아니라면 오른쪽 인덱스 값을 해시맵에 추가
				if(map2.containsKey(a[rt])) {
					map1.put(a[rt], map1.getOrDefault(a[rt], 0)+1);
				}
				rt++;				
			}
		}
		
		return result;
	}
}

주요 핵심 포인트

1.  해당 문제 또한 4-3과 비슷하게 풀었다. 투 포인터 인덱스를 0부터 시작하여 lt와 rt의 차를 이용하여 길이보다 작다면 계속해서 오른쪽 인덱스 값을 넣고 같아지면 값을 비교하여 처리하고, 왼쪽 포인터를 다시 증가시키는 로직을 반복하였다.

2.  오른쪽 끝 인덱스 처리를 위하여 오른쪽 인덱스가 끝자리에 왔다면 값을 처리해주고 while문이 종료되도록 rt를 하나 증가시켰다.

개선해야할 사항

1. 인프런에서 푼 코드는 기존에 값을 T-1만큼 해시맵에 추가해두고 마지막행부터 rt를 시작하도록 하였다. 나도 다음부터는 미리 값을 넣어놓고 비교해야겠다.

문제 풀이 (JAVA)

import java.io.*;
import java.util.*;
public class part4_3 {

	public static void main(String[] args) throws IOException{
		// 매출액의 종류
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st= new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		String str = br.readLine();
		String [] a = str.split(" ");
		List<Integer> answer = solution(a,N,K);
		for(Integer s : answer) {
			bw.write(s+" ");
		}
		bw.flush();
		bw.close();
	}
	private static List<Integer> solution(String [] a, int N, int K) {

		HashMap<String,Integer> map = new HashMap<>();
		List<Integer> list =new ArrayList<>();
		int lt=0, rt=0;
		int cnt=0;
		while(lt < N  && rt < N) {			
			// 오른쪽 포인터 rt와 왼쪽 포인터 lt의 차가 K보다 작다면 윈도우가 다 안찼으므로
			if((rt-lt) < K) {
				// map에 추가한다. key가 존재할시 기존 값에 +1을 한다.
			   map.put(a[rt], map.getOrDefault(a[rt], 0)+1);
			   rt++; // 오른쪽 슬라이드 포인터 증가
			// K의 길이와 포인터의 차가 같다면 윈도우의 사이즈가 K인것이므로
			}else if((rt-lt) == K){
				list.add(map.size()); // 해당 윈도우의 맵 사이즈가 숫자의 종류이므로 리스트 추가
				map.put(a[lt], map.getOrDefault(a[lt], 0)-1); // 맨 왼쪽 슬라이드 값 -1
				if(map.get(a[lt]) == 0) { // 해당 값이 0이 된다면 중복되는 맵이 없으므로
					map.remove(a[lt]); // 해당 숫자 맵에서 제거
				}
				// 오른쪽 포인터가 마지막을 왔을때 증가된 포인터 처리
				if(rt==N-1) {
					// 해당 값을 맵에 추가하여 리스트에 더하고 종료한다.
					map.put(a[rt], map.getOrDefault(a[rt],0)+1);
					list.add(map.size());
					break;
				}
				lt++; // 왼쪽 슬라이드 포인터 증가 
			}

		}		
		return list;
	}
}

해시 함수 정리

map.put(key,value) : map에 해당되는 key에 value를 INSERT or UPDATE 한다.

map.get(key) : key에 해당하는 value를 리턴한다.

map.containsKey(key) : map에 key가 존재하는지 확인하여 존재하면 true, 존재하지 않을 경우 false를 리턴한다.

map.getOrDefault(key,0) : map에 key가 존재하면 key의 value를 리턴하고, key가 존재하지 않으면 0을 리턴한다.

map.size() : map의 사이즈를 리턴한다.

map.remove(key) : key의 value를 출력하고, 해당 되는 key를  map에서 제거한다.

for (Character key : map.keySet()) : key를 순서대로 탐색한다.

주요 핵심 포인트

1.  해당 문제는 슬라이딩윈도우와 해쉬맵을 사용하여 풀어보는 응용 문제이다.

2. K의 길이와 lt , rt의 포인터 인덱스 번호의 차를 이용하여 길이가 rt와 lt를 증가시키면서 풀었다.

3. K개의 길이만큼 도달했을시 getOrDefault 함수를 사용하여 기존값에 -1을 하여 0이 된다면 중복값이 없으므로 해당 값을 remove하고, 1이라면 중복값이므로 해쉬맵에서 제거하지 않고 두었다. 결과적으로 중복값은 남되 새로운 값은 추가할수 있게 된다.

4. 마지막 rt의 인덱스를 쓰고 증가시켰을때 마지막 윈도우를 처리하기 위하여 break 문을 추가하였다.

문제 풀이 (JAVA)

import java.io.*;
import java.util.*;
public class part3_6 {

	public static void main(String[] args) throws IOException {
		// 최대 길이 연속부분수열
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String str = br.readLine();
		StringTokenizer st = new StringTokenizer(str);
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int [] a = new int[N];
		
		StringTokenizer st2 =new StringTokenizer(br.readLine());
		int i=0;
		while(st2.hasMoreTokens()) {
			a[i++]=Integer.parseInt(st2.nextToken());
		}
		int answer = solution(a,N,K);
		
		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
	}
	private static int solution(int [] a, int N, int K) {
		int result=0;
		int lt=0, rt=0;
		int zerocnt=0; // 0의 개수 카운트 
		while(lt < N && rt < N) {
			if(a[rt]==0) { // 오른쪽 포인터 값이 0이고 
				if(zerocnt==K) { // 기존 0의 개수가 K개라면 0을 K+1번째 만남 
					// 두 포인터 사이의 거리가 기존값보다 크다면
					if(result < Math.abs(rt-lt)) { 
						result = Math.abs(rt-lt);
					}
					// 오른쪽 포인터를 멈추고 다음 0을 만날때까지 왼쪽 포인터 증가
					if(a[lt]==1) {
						lt++;
					}else {
						zerocnt-=1; 
						// 왼쪽 포인터가 0이라면 0의 개수카운트 감소후 다음 포인터로 증가
						lt++;
					}
				}else if(zerocnt < K) { // 다음 0을 만났을때
					zerocnt++; // 0 개수와 오른쪽 포인터 증가
					rt++;
				}
			}else if(a[rt]==1) { // 1이라면 오른쪽포인터 증가
				rt++;
			}
		}
		return result;
	}
}

주요 핵심 포인트

1. 해당 문제를 풀때, 0의 개수를 3번째로 만났을때 왼쪽 포인터와 오른쪽포인터의 최대길이가 되므로 0의 개수카운트를 이용하여 투 포인터를 증가시켰다.

2. 0의 개수가 K개 미만이라면 오른쪽 포인터를 반복 증가 시켰고, K가 됬을시 왼쪽 포인터를 증가시켜 다음 0을 만난다면 오른쪽 포인터가 다시 다음 0을 찾을 수 있도록 포인터를 증가시켰다.

3. 투포인터와 슬라이딩 윈도우 알고리즘을 이해하여 풀수 있게된 문제로 까먹을시 다시 개념을 공부해야 한다.

문제 풀이 (JAVA)

import java.util.*;
public class part3_5 {

	public static void main(String[] args) {
		// 연속된 자연수의 합
		Scanner input =new Scanner(System.in);
		
		int n = input.nextInt();
		int answer = solution(n);
		
		System.out.print(answer);

	}
	private static int solution(int n) {
		int result=0;
		int sum=1;
		int lt=1,rt=1;
		
		while(lt < n && rt < n) {
			if(sum==n) {
				// n이 되는 sum은 결과값 증가
				result++; 
				// 다음 연속된 숫자를 구하기위하여 왼쪽 포인터 lt 값을 뺀다.
				sum-= lt;
				lt++; // 다음값을 위한 왼쪽 포인터 증가
			}else if(sum < n) { // n이 안된다면 
				++rt; // 오른쪽 포인터 증가
				sum += rt; // 증가 된 값을 sum에 추가
			}else if(sum > n) { // n을 초과한다면 
				sum -= lt; // 왼쪽 포인터 lt 값을 n이 되거나 작게 될때까지 뺀다.
				lt++; // 왼쪽 포인터 증가
			}
		}
		return result;
	}
}

주요 핵심 포인트

1. 해당 문제는 투포인터와 슬라이딩 윈도우 알고리즘 개념을 혼합한 응용문제이다.

2. N이 되는 순간 왼쪽 포인터를 1씩 증가시키고 마지막 값을 빼고 오른쪽 포인터 값을 추가 시키는 작업을 반복함으로써   N이 되는 개수를 카운트한다.

 3. 인덱스가 증가할때마다 첫값과 마지막값을 바꿔주는 슬라이딩윈도우 방식의 알고리즘과, 투 포인터를 잘 활용하여 풀도록 하였다.