01-09 18:44
Recent Posts
Recent Comments
๊ด€๋ฆฌ ๋ฉ”๋‰ด

miinsun

[Algorithm]์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ž๋ฐ”_32 ๋งค์ถœ์•ก์˜ ์ข…๋ฅ˜ ๋ณธ๋ฌธ

Algorithm/Java

[Algorithm]์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ž๋ฐ”_32 ๋งค์ถœ์•ก์˜ ์ข…๋ฅ˜

miinsun 2022. 1. 5. 19:37

 

๐Ÿ’ฌ ๋ฌธ์ œ ์„ค๋ช…

ํ˜„์ˆ˜์˜ ์•„๋น ๋Š” ์ œ๊ณผ์ ์„ ์šด์˜ํ•ฉ๋‹ˆ๋‹ค. ํ˜„์ˆ˜์•„๋น ๋Š” ํ˜„์ˆ˜์—๊ฒŒ N์ผ ๋™์•ˆ์˜ ๋งค์ถœ๊ธฐ๋ก์„ ์ฃผ๊ณ  ์—ฐ์†๋œ K์ผ ๋™์•ˆ์˜ ๋งค์ถœ์•ก์˜ ์ข…๋ฅ˜๋ฅผ ๊ฐ ๊ตฌ๊ฐ„๋ณ„๋กœ ๊ตฌํ•˜๋ผ๊ณ  ํ–ˆ์Šต๋‹ˆ๋‹ค.

๋งŒ์•ฝ N=7์ด๊ณ  7์ผ ๊ฐ„์˜ ๋งค์ถœ๊ธฐ๋ก์ด ์•„๋ž˜์™€ ๊ฐ™๊ณ , ์ด๋•Œ K=4์ด๋ฉด
20 12 20 10 23 17 10

๊ฐ ์—ฐ์† 4์ผ๊ฐ„์˜ ๊ตฌ๊ฐ„์˜ ๋งค์ถœ์ข…๋ฅ˜๋Š”
์ฒซ ๋ฒˆ์งธ ๊ตฌ๊ฐ„์€ [20, 12, 20, 10]๋Š” ๋งค์ถœ์•ก์˜ ์ข…๋ฅ˜๊ฐ€ 20, 12, 10์œผ๋กœ 3์ด๋‹ค.
๋‘ ๋ฒˆ์งธ ๊ตฌ๊ฐ„์€ [12, 20, 10, 23]๋Š” ๋งค์ถœ์•ก์˜ ์ข…๋ฅ˜๊ฐ€ 4์ด๋‹ค.
์„ธ ๋ฒˆ์งธ ๊ตฌ๊ฐ„์€ [20, 10, 23, 17]๋Š” ๋งค์ถœ์•ก์˜ ์ข…๋ฅ˜๊ฐ€ 4์ด๋‹ค.
๋„ค ๋ฒˆ์งธ ๊ตฌ๊ฐ„์€ [10, 23, 17, 10]๋Š” ๋งค์ถœ์•ก์˜ ์ข…๋ฅ˜๊ฐ€ 3์ด๋‹ค.

N์ผ๊ฐ„์˜ ๋งค์ถœ๊ธฐ๋ก๊ณผ ์—ฐ์†๊ตฌ๊ฐ„์˜ ๊ธธ์ด K๊ฐ€ ์ฃผ์–ด์ง€๋ฉด ์ฒซ ๋ฒˆ์งธ ๊ตฌ๊ฐ„๋ถ€ํ„ฐ ๊ฐ ๊ตฌ๊ฐ„๋ณ„ ๋งค์ถœ์•ก์˜ ์ข…๋ฅ˜๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์„ธ์š”.

 

 

๐Ÿ”จ ์ž…์ถœ๋ ฅ ์˜ˆ

์ž…๋ ฅ - ์ฒซ ์ค„์— N(5<=N<=100,000)๊ณผ K(2<=K<=N)๊ฐ€ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค.

๋‘ ๋ฒˆ์งธ ์ค„์— N๊ฐœ์˜ ์ˆซ์ž์—ด์ด ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. ๊ฐ ์ˆซ์ž๋Š” 500์ดํ•˜์˜ ์Œ์ด ์•„๋‹Œ ์ •์ˆ˜์ž…๋‹ˆ๋‹ค.

7 4
20 12 20 10 23 17 10

์ถœ๋ ฅ - ์ฒซ ์ค„์— ๊ฐ ๊ตฌ๊ฐ„์˜ ๋งค์ถœ์•ก ์ข…๋ฅ˜๋ฅผ ์ˆœ์„œ๋Œ€๋กœ ์ถœ๋ ฅํ•ฉ๋‹ˆ๋‹ค.

3 4 4 3

 

 

๐Ÿ’ป Solution.java

import java.util.*;

public class Main {

	public ArrayList<Integer> solution(int n, int k, int[] arr) {
        ArrayList<Integer> answer = new ArrayList<>();
        HashMap<Integer, Integer> HM = new HashMap<>();
        
        for(int i = 0; i < k - 1; i++) {
        	HM.put(arr[i], HM.getOrDefault(arr[i], 0) + 1);
        }
        int lt = 0;
        for(int rt = k - 1; rt < n; rt++) {
        	HM.put(arr[rt], HM.getOrDefault(arr[rt], 0) + 1);
        	answer.add(HM.size());
        	HM.put(arr[lt], HM.get(arr[lt]) - 1);
        	
        	if(HM.get(arr[lt]) == 0)
        		HM.remove(arr[lt]);
        	lt++;
        }
        
        return answer;
	}
	
	public static void main(String[] args){
		Main main  = new Main();
		Scanner sc =new Scanner(System.in);
		
		int n = sc.nextInt();
		int k = sc.nextInt();
		int[] arr = new int [n];
		
		for(int i = 0; i < n; i++) {
			arr[i] = sc.nextInt();
		}
		
		for(int x : main.solution(n, k, arr)) System.out.print(x + " ");
		
		sc.close();
		return ;
	}
}

 

 

 

Comments