Yong's Tech Story

문제 풀이 (JAVA)

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

	public static void main(String[] args) throws IOException {
		// 학급 회장(해쉬)
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());
		char [] ch = new char[N];
		String str = br.readLine();
		ch = str.toCharArray();
		char answer = solution(ch);
		
		bw.write(answer);
		bw.flush();
		bw.close();
	}
	private static char solution(char [] charr) {
		char result =' ';
		int max=0;
		HashMap<Character,Integer> map = new HashMap<>();
		for(int i=0; i< charr.length; i++) {
			// or if문 (map.containsKey(charr[i]))
			map.put(charr[i], map.getOrDefault(charr[i],0)+1);
		}
		for(Character key : map.keySet()) {
			if(max < map.get(key)) {
				max = map.get(key);
				result = key;
			}
		}
		return result;
	}
}

해시 함수 정리

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. 가장 기초가 되는 key , value 개념을 알아야 풀 수 있는 문제이다.

문제 풀이 (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. 인덱스가 증가할때마다 첫값과 마지막값을 바꿔주는 슬라이딩윈도우 방식의 알고리즘과, 투 포인터를 잘 활용하여 풀도록 하였다.

문제 풀이 (JAVA)

import java.util.*;
public class part3_3 {

	public static void main(String[] args) {
		// 최대 매출
		Scanner input =new Scanner(System.in);
		
		int N = input.nextInt();
		int K = input.nextInt();
		
		int [] a = new int[N];
		for(int i=0; i<N; i++) {
			a[i]=input.nextInt();
		}
		int answer = solution(N,K,a);
		System.out.print(answer);
		
	}
	private static int solution(int N, int K, int [] a) {
		int result=0;
		int sum=0;
		for(int i=0; i<K; i++) {
			sum+=a[i];
		}
		result=sum; // 첫번째 윈도우 sum 계산
		int p1=K; // 포인터는 첫번째 윈도우 +1번째를 바라본다.
		while(p1 < N) {
			// 한칸씩 옮기며 마지막 행(p1)은 더하고 첫번째 행(p1-k)은 뺀다.
			sum += (a[p1] - a[p1-K]);
			if(result <sum) { // 해당 윈도우가 가장 크다면 값 변경
				result=sum;
			}
			p1++; //포인터 증가 
		}
		
		return result;
	}
}

주요 핵심 포인트

1.  슬라이딩 윈도우 알고리즘은 매번 비교하는 값이 1씩 증가하며 값을 구하는데, 1씩 증가할때마다 첫번째 값은 빼고, 증가한 마지막 값을 더해주어 값을 변경해주는 알고리즘으로 O(n^2)번을 O(n)번으로 축약시켜 효율성 테스트를 통과해야 하는 문제이다.