[문제풀이] 03-03. 최대 매출

인프런, 자바(Java) 알고리즘 문제풀이

Two pointers, Sliding window - 0303. 최대 매출

🗒️ 문제

🎈 나의 풀이

	private static int solution(int n, int m, String[] strArr) {
        int answer = 0, sum = 0;

        for(int i=0; i<m; i++) {
            sum += Integer.parseInt(strArr[i]);
        }

        answer = sum;

        for(int i=m; i< n; i++) {
            sum -= Integer.parseInt(strArr[i - m]);
            sum += Integer.parseInt(strArr[i]);
            answer = Math.max(sum, answer);
        }

        return answer;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] strArr = sc.nextLine().split(" ");

        int n = Integer.parseInt(strArr[0]);
        int m = Integer.parseInt(strArr[1]);
        strArr = sc.nextLine().split(" ");

        System.out.println(solution(n, m, strArr));
    }

🖍️ 강의 풀이

    public int solution(int n, int k, int[] arr){
		int answer, sum=0;
		for(int i=0; i<k; i++) sum+=arr[i];
		answer=sum;
		for(int i=k; i<n; i++){
			sum+=(arr[i]-arr[i-k]);
			answer=Math.max(answer, sum);
		}
		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];
		for(int i=0; i<n; i++){
			arr[i]=kb.nextInt();
		}
		System.out.print(T.solution(n, k, arr));
	}

💬 짚어가기

해당 문제는 sliding window 알고리즘을 통해 쉽게 풀 수 있다. window를 통해 한 영역을
바라보고, 이를 sliding 시켜가며 전체를 순회하는 방식이다. 글로 설명하니 바로 와닿지 않지만,
코드를 통해 쉽게 이해할 수 있을 것이다.

해당 알고리즘 역시 매번 배열을 처음부터 순회하는 것이 아닌, 나의 관심사 영역만 순회하도록 함으로
시간 복잡도를 줄일 수 있다.