[알고리즘]매출액의 종류

▷ 문제

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

▷ 풀이

1. 다중 for문 사용

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

public class Main {	
    public void solution(int n, int k, int[] arr){
      HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
      int key = 0;

      for(int i=0; i<n-k+1; i++){
        ArrayList<Integer> list = new ArrayList<Integer>();

        for(int j=i; j<i+k; j++){
          if(!list.contains(arr[j])){
            list.add(arr[j]);
          }
        }

        map.put(key++, list.size());
      }

      map.values().forEach((value) -> System.out.print(value + " "));
    }

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

        int n = kb.nextInt();
        int k = kb.nextInt();
        int[] arr = new int[n];
        for(int x=0; x<n; x++){
          arr[x] = kb.nextInt();
        }

        main.solution(n, k, arr);
    }
  }

 

2. 포인터 사용

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

public class Main {	
    public ArrayList<Integer> solution(int n, int k, int[] arr){
      ArrayList<Integer> answer = new ArrayList<Integer>();
      HashMap<Integer, Integer> map = new HashMap<>();
      int lt = 0;

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

      for(int rt=k-1; rt<n; rt++){
        map.put(arr[rt], map.getOrDefault(arr[rt], 0) + 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 main = new Main();
        Scanner kb = new Scanner(System.in);

        int n = kb.nextInt();
        int k = kb.nextInt();
        int[] arr = new int[n];
        for(int x=0; x<n; x++){
          arr[x] = kb.nextInt();
        }

        for(int x : main.solution(n, k, arr)){
          System.out.print(x + " ");
        };
    }
  }

▷ 핵심 포인트

1. 포인터를 쓸 경우 시간을 단축시킬 수 있으므로 상황에 맞게 알맞는 방법을 택합니다.