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 문을 추가하였다.