[Ch.04 - HashTree] 03. 매출액의 종류 #

3. 매출액의 종류

 

설명

현수의 아빠는 제과점을 운영합니다. 현수아빠는 현수에게 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이하의 음이 아닌 정수입니다.

출력

첫 줄에 각 구간의 매출액 종류를 순서대로 출력합니다.

---

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;

public class abcd {
	public ArrayList<Integer> solution(int n, int m, int[] arr) {
		ArrayList<Integer> list = new ArrayList<>();

		for (int i = 0; i < n; i++) {
			HashMap<Integer, Integer> map = new HashMap<>();
			if (i + m != n+1) {

				for (int j = i; j < i + m; j++) {
					map.put(arr[j], map.getOrDefault(arr[j], 0) + 1);

				}
			} else {
				break;
			}

			list.add(map.size());

		}
		return list;

	}

	public static void main(String[] args) {

		abcd T = new abcd();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int[] arr = new int[n];
		int m = kb.nextInt();
		for (int i = 0; i < n; i++) {
			arr[i] = kb.nextInt();
		}
		for (int x : T.solution(n, m, arr)) {
			System.out.print(x + " ");
		}

	}
}

-> 이중for문으로 인한 타임리밋 발생

 

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;

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

}

 

package hashtree04_2;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;
import java.util.Set;

public class Hashtree03 {
	public ArrayList<Integer> solution(int m, int[] arr) {
		
		ArrayList<Integer> answer=new ArrayList<>();
		for(int i=0;i<=arr.length-m;i++) {
			HashMap<Integer, Integer> map = new HashMap<>();
			for(int j=i;j<i+m;j++) {
				map.put(arr[j], map.getOrDefault(arr[j], 0)+1);
			}
			answer.add(map.size());
		}
		return answer;
	}
	public static void main(String[] args) {
		Hashtree03 T = new Hashtree03();
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		int m=kb.nextInt();
		int[] arr =new int[n];
		for(int i=0;i<n;i++)
			arr[i]=kb.nextInt();
		for(int x:T.solution(m,arr)) {
			System.out.print(x+" ");
		}
	}
	

}

-> Map을 이용해 이중 for문 -> Timelimit 발생

-> 매일 구간별로 새로 구하는 게 아니라, 이전날짜 삭제 후 다음날 추가하는 방식으로 변경

 

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.Scanner;

public class Main {
	public ArrayList<Integer> solution(int m, int[] arr) {
		ArrayList<Integer> answer = new ArrayList<>();

		// 구간 마다 첫 번째 값을 지우고, 새로운 값을 추가
		int lt = 0, rt = lt;
		LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();

		// 먼저 맨 처음 구간 설정
		for (int i = 0; i < m; i++) {
			map.put(arr[i], map.getOrDefault(arr[i], 0)+1);			
			
		}
		answer.add(map.size());
		
		for (int i = 0; i < arr.length - m; i++) {
			map.put(arr[i], map.get(arr[i]) - 1);
			if (map.get(arr[i]) == 0)
				map.remove(arr[i]);
			map.put(arr[i + m], map.getOrDefault(arr[i + m], 0) + 1);

			answer.add(map.size());
		}

		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);

		int n = kb.nextInt();
		int m = kb.nextInt();
		int[] arr = new int[n];

		for (int i = 0; i < n; i++)
			arr[i] = kb.nextInt();
		for (int x : T.solution(m, arr))
			System.out.print(x + " ");

	}

}

 

 

+) 세련된 풀이

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;

public class Main {
	// 매출액의 종류
	// N일 매출기록, 연속된 K일 동안 매출액의 종류를 구간별로
	// N일 중, 연속 K일 간 매출액이 다른 경우의 종류의 수 출력
	// 첫 줄에 N일, K일 주어진다.
	// 두 번쨰 줄에 N개의 숫자열 주어지고, 500이하 음이 아닌 정수
	// 첫 줄에 각 구간의 매출액 종류의 개수 순서대로 출력
	public ArrayList<Integer> solution(int n, int k, int[] arr) {
		ArrayList<Integer> answer = new ArrayList<>();
		// 매출액 리스트 객체 생성(중복허용)
		HashMap<Integer, Integer> HM = new HashMap<>();
		// n일, k일로 이루어진 자료구조 -> N일에 대해 K일 동안의 매출액

		// N일에 대해 K일 동안의 매출액 중에서, 같지 않은 매출액의 개수

		// K일까지의 매출액 구하기
		for (int i = 0; i < k - 1; i++) {
			// 0부터 k일보다 하루적을때 즉, k일동안
			HM.put(arr[i], HM.getOrDefault(arr[i], 0) + 1);
			// 맵에 처음부터 i번째 키에, 해당 키의 값이 있으면 +1, 없으면 0을 넣는다.
		}

		// K일부터 매출액 구하기
		int lt = 0;
		// 순서대로 세는 변수에 0으로 초기화
		for (int rt = k - 1; rt < n; rt++) {
			// K일부터 세는 변수로 초기화 [0부터 세기 때문에 k-1] -> N일까지의 K일 동안의 매출액 개수
			HM.put(arr[rt], HM.getOrDefault(arr[rt], 0) + 1);
			// 맵에 뒤에서부터 rt번째 키에, 해당 키의 값이 있으면 +1, 없으면 0을 넣는다.
			answer.add(HM.size());
			// 매출액의 개수를 출력리스트에 추가

			HM.put(arr[lt], HM.get(arr[lt]) - 1);
			// 같은 매출액이 있으면 -1
			if (HM.get(arr[lt]) == 0)
				// 매출액의 개수가 0이면
				HM.remove(arr[lt]);
				// 해당 매출액을 없앤다.
			lt++;
			//순서대로 세는 변수에 +1
		}
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);

		int n = kb.nextInt();
		int k = kb.nextInt();
		int[] arr = new int[n];
		// 인트 배열 arr을 n개의 배열로 초기화
		for (int i= 0; i < n; i++) {
			arr[i] = kb.nextInt();
		}
		for (int x : T.solution(n, k, arr))
			System.out.print(x + " ");
		kb.close();
	}

	
}

 

 

 

(1) 초기값 구하기

(2) 새로운 날 추가하고, 이전날 제거하고 종류 체크 -> 개수가 0개인것들 직접 제거

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    int m = in.nextInt();
    int[] arr =new int[n];
    for(int i=0;i<n;i++){
      arr[i]=in.nextInt();
    }
   	solution(n,m,arr);
  }
  static void solution(int n, int m,int[]arr){
    ArrayList<Integer>list = new ArrayList<>();
    int lt=0;
    int rt=arr.length-1;
    Map<Integer, Integer> map = new HashMap<>();
    for(int i=0;i<m;i++){
      map.put(arr[i], map.getOrDefault(arr[i],0)+1);
    }
    list.add(map.size());
    for(int i=m;i<n;i++){
      map.put(arr[i],map.getOrDefault(arr[i],0)+1);
      map.put(arr[i-m],map.get(arr[i-m])-1);
      if(map.get(arr[i-m])==0) map.remove(arr[i-m]);
      list.add(map.size());
    }
    for(int x:list) System.out.print(x+" ");
    
  }
}

---

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    int k = in.nextInt();
    int[] arr = new int[n];
    for(int i=0;i<n;i++) arr[i]=in.nextInt();
    for(int x: Solution(n,k,arr)) System.out.print(x+" ");
  }
  private static int[] Solution(int n, int k, int[] arr){
    Map<Integer, Integer> map = new HashMap<>();
    int[] answer= new int[n-k+1];
    //초기값 설정
    for(int i=0;i<k;i++){
      map.put(arr[i], map.getOrDefault(arr[i], 0)+1);
    }
    answer[0]=map.size();
    for(int i=1; i<n-k+1; i++){
      map.put(arr[i-1], map.getOrDefault(arr[i-1], 0)-1);
      if(map.get(arr[i-1])==0) map.remove(arr[i-1]); 
      
      map.put(arr[i+k-1], map.getOrDefault(arr[i+k-1],0)+1);
      
      answer[i]=map.size();
    }
    return answer;
  }
}