매출액의 종류

 

문제 이해

 

매출액이 입력되고 K가 입력되면 연속 K개의 구간을 각각 구한 후 그 안에 매출액 종류의 개수를 각각 출력하는 문제이다.

 

문제 해결

 

처음에는 K개를 포함할 수 있는 만큼 for문을 돌며 map안에 K개를 담아준 후 map의 size를 출력해주는 간단한 코드로 작성했다. 하지만 Timeout Error가 발생했다. 이는 중첩된 루프로 인해 매번 K개의 새로운 해시맵이 만들어지므로 시간 복잡도가 커지는 이유 때문이다.

Timeout Error 뜬 코드

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

public class P03_매출액의종류 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int K = in.nextInt();
        in.nextLine();

        String sales = in.nextLine();
        String[] splitSales = sales.split(" ");

        for(int i = 0; i <= N - K; i++) { //k개를 포함할 수 있는만큼 반복
            HashMap<String, Integer> map = new HashMap<>();
            for(int j = i; j < i + K; j++) { //map 안에 k개를 담아줌.
                map.put(splitSales[j], map.getOrDefault(splitSales[j],0)+1);
            }
            System.out.print(map.size() + " ");
        }
    }
}

 

 

그래서 새로 접근한 방법은 입력 받은 배열을 하나씩 탐색하면서

 

우선 스캐너 객체로 각각 N과 K를 입력받아 준 후, sales 변수에 매출액을 입력받고 공백을 기준으로 잘라 splitSales배열에 넣어주었다.

Scanner in = new Scanner(System.in);
int N = in.nextInt();
int K = in.nextInt();
in.nextLine();

String sales = in.nextLine();
String[] splitSales = sales.split(" ");

 

그 후 처음에는 처음 K개의 요소를 살펴보고, 각 매출액의 등장 횟수를 해시맵에 저장한다.

HashMap<String, Integer> map = new HashMap<>(); //초기 매출액 맵 세팅
for(int i = 0; i < K; i++) {
    map.put(splitSales[i], map.getOrDefault(splitSales[i],0)+1);
}
System.out.print(map.size() + " ");

 

그리고 그 이후부터 한 칸씩 이동하며 앞에 있는 매출액을 제거하고 뒤에있는 매출액은 추가하며 맵에 담는 과정을 해준다.

여기에서 prev 변수는 이전 맵에서 담았던 첫 번째 요소 (i-K)이고, 이게 prevCount는 이전 맵에서 처리된 첫 번째 요소의 등장 횟수를 나타낸다. 즉 이 요소가 1, 하나만 등장했던 경우는 맵에서 제거하고, 그렇지 않은 경우는 등장 횟수를 하나 줄여 업데이트 한다.

for(int i = K; i < N; i++) { // 이전 맵에서 다음 순서를 추가하고 맨 처음에 들어있던 매출액을 방식으로
    int prev = i - K;
    int prevCount = map.get(splitSales[prev]);
    if(prevCount == 1) { // 한 번 등장
        map.remove(splitSales[prev]); //맵에서 제거
    } else {
        map.put(splitSales[prev], prevCount - 1); //하나 줄여 업데이트
    }

 

그리고 새로운 요소를 맵에 추가한다. 이때, 해당 요소가 이미 맵에 존재한다면 기존 등장 횟수에 1을 더하고, 존재하지 않는 1로 초기화한다. 그리고 map의 size를 출력해주면 된다.

map.put(splitSales[i], map.getOrDefault(splitSales[i],0)+1);
System.out.print(map.size() + " ");

 

 

최종 코드

 

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

public class P03_매출액의종류 {
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int K = in.nextInt();
        in.nextLine();

        String sales = in.nextLine();
        String[] splitSales = sales.split(" ");

        HashMap<String, Integer> map = new HashMap<>(); //초기 매출액 맵 세팅
        for(int i = 0; i < K; i++) {
            map.put(splitSales[i], map.getOrDefault(splitSales[i],0)+1);
        }
        System.out.print(map.size() + " ");

        for(int i = K; i < N; i++) { // 이전 맵에서 다음 순서를 추가하고 맨 처음에 들어있던 매출액을 방식으로
            int prev = i - K;
            int prevCount = map.get(splitSales[prev]);
            if(prevCount == 1) {  // 한 번 등장
                map.remove(splitSales[prev]); //맵에서 제거
            } else {
                map.put(splitSales[prev], prevCount - 1); //하나 줄여 업데이트
            }

            map.put(splitSales[i], map.getOrDefault(splitSales[i],0)+1);
            System.out.print(map.size() + " ");
        }
    }
}