4-3 매출액의 종류(Hash, Sliding Window)

 

문제 링크 : https://cote.inflearn.com/contest/10/problem/04-03

 

** 맨 처음 제출한 코드

import java.util.*;
import java.util.stream.Stream;
import java.io.*;
 
class Main{
    static int n,m,k;
    static StringTokenizer st;
    static StringBuilder sb;
    public static void main(String[] args)throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine(), " ");
        int[] arr = new int[n];
        for(int i=0; i<n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int start=0;
        int end=m;
        sb = new StringBuilder();
        while(end<=n) {
            Map<Integer, Integer>map = new HashMap<>();
            int cnt=0;
            for(int i=start; i<end; i++) {
                int tmp = arr[i];
                if(map.containsKey(tmp)) {
                    continue;
                }else {
                    cnt++;
                    map.put(tmp, 1);
                }
            }
            start++;
            end++;
            sb.append(cnt+" ");
        }
        System.out.println(sb.toString());
        br.close();
        bw.close();
    }
}

 

- 시간초과 발생

- 투포인터 느낌으로 start와 end 포인터를 통해 윈도우의 크기만큼 반복을 진행하고자 하였으나, 윈도우의 크기가 N의 최대 크기인 10만까지 가능했었음.

- 10만의 제곱으로 인해 제한시간 초과가 발생. 개인적인 생각으로 문제의 답은 맞지 않았을까 함.

- 맵을 while 안에 생성하는 것으로 계속 초기화를 하면 정확성 있는 답을 얻을 것이라 생각했음.

 

** 변경 이후 코드 (1차)

import java.util.*;
import java.util.stream.Stream;
import java.io.*;
 
class Solution{
    static int n,m,k;
    static StringTokenizer st;
    static StringBuilder sb;
    public static void main(String[] args)throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine(), " ");
        int[] arr = new int[n];
        for(int i=0; i<n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Map<Integer, Integer>map = new HashMap<>();
        sb = new StringBuilder();
        int start=0;
        for(int i=0; i<n; i++) {
            int key = arr[i];
            if(map.containsKey(key)) {
                int tmp = map.get(key);
                tmp++;
                map.put(key, tmp);
            }else {
                map.put(key, 1);
            }
            if(i==m-1) {
                sb.append(map.size()+" ");
                continue;
            }
            if(i>=m) {
                int now = arr[start++];
                int value = map.get(now);
                if(value>1) {
                    value--;
                    map.put(now, value);
                }else {
                    map.remove(now);
                }
                sb.append(map.size()+" ");
            }
        }
        System.out.println(sb.toString());
        br.close();
        bw.close();
    }
}
 

 

- 기존 코드는 투포인터의 최대 장점 O(n) 시간복잡도의 장점을 살리지 못했음. 최악 O(n²)

- 슬라이딩 윈도우를 진행하며, Map에 해당 key가 존재한다면 Value를 1씩 증가하는 방식을 사용

- 반복의 범위를 통해 변수 i(포인터 중 Right)가 윈도우의 크기를 넘어선다면, Left포인터 증가를 실시

- 이 과정중, Value가 1초과면 값을 1낮추고, 1보다 같거나 작다면 Map에서 삭제를 진행

 

** 변경 이후 코드(2차)

import java.util.*;
import java.util.stream.Stream;
import java.io.*;
 
class Solution{
    static int n,m,k;
    static StringTokenizer st;
    static StringBuilder sb;
    public static void main(String[] args)throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine(), " ");
        int[] arr = new int[n];
        for(int i=0; i<n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Map<Integer, Integer>map = new HashMap<>();
        sb = new StringBuilder();
        int start=0;
        for(int i=0; i<m; i++) {
            map.put(arr[i], map.getOrDefault(arr[i], 0)+1);
        }
        sb.append(map.size()+" ");
        for(int i=m; i<n; i++) {
            map.put(arr[i], map.getOrDefault(arr[i], 0)+1);
            map.put(arr[start], map.get(arr[start])-1);
            if(map.get(arr[start])==0)map.remove(arr[start]);
            start++;
            sb.append(map.size()+" ");
        }
        System.out.println(sb.toString());
        br.close();
        bw.close();
    }
}
 

- map.getOrDefault라는 함수를 통해, Key가 존재하면 그에 해당하는 Value를 가져오고 아니면 0을 반환하는 기능이 있다는 것을 새롭게 배움.

- 이를 통해 기존의 if-else를 통한 코드의 길이보다 훨씬 간결해지며 보기 좋아졌음.