[JAVA] 알고리즘 문제풀이 입문 3-2, 3-3번

강의: https://inf.run/w779

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 - 인프런 | 강의

 

3-2번

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Collection;

import java.util.Collections;

import java.util.Scanner;

 

public class Main {

  public ArrayList<Integer> solution(int n, int m, int[] arr1, int[] arr2){

    ArrayList<Integer> answer = new ArrayList<>();

    for(int i = 0; i < n; i++){

      for(int j = 0; j < m; j++){

        if(arr1[i] == arr2[j]){

          answer.add(arr1[i]);

        }

      }

    }

    Collections.sort(answer);

    return answer;

  }

  public static void main(String[] args){

    Main t = new Main();

    Scanner in = new Scanner(System.in);

    int n = in.nextInt();

    int[] arr1 = new int[n];

    for(int i = 0; i < n; i++){

      arr1[i] = in.nextInt();

    }

    int m = in.nextInt();

    int[] arr2 = new int[m];

    for(int i = 0; i < m; i++){

      arr2[i] = in.nextInt();

    }

    in.close();

    for(int x : t.solution(n, m, arr1, arr2)){

      System.out.print(x+" ");

    }

  }

}

이렇게 구성했는데 시간초과가 뜬다. 이중 for문이 문제인듯.

3-1번처럼 p1, p2를 이용해 코드를 수정했다.

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Scanner;

 

public class Main {

  public ArrayList<Integer> solution(int n, int m, int[] arr1, int[] arr2){

    ArrayList<Integer> answer = new ArrayList<>();

    int p1 = 0, p2 = 0;

    Arrays.sort(arr1);

    Arrays.sort(arr2);

    while(p1 < n && p2 < m){

      if(arr1[p1] == arr2[p2]){

        answer.add(arr1[p1++]);

        p2++;

      }else if(arr1[p1] > arr2[p2]){

        p2++;

      }else{

        p1++;

      }

    }

    return answer;

  }

  public static void main(String[] args){

    Main t = new Main();

    Scanner in = new Scanner(System.in);

    int n = in.nextInt();

    int[] arr1 = new int[n];

    for(int i = 0; i < n; i++){

      arr1[i] = in.nextInt();

    }

    int m = in.nextInt();

    int[] arr2 = new int[m];

    for(int i = 0; i < m; i++){

      arr2[i] = in.nextInt();

    }

    in.close();

    for(int x : t.solution(n, m, arr1, arr2)){

      System.out.print(x+" ");

    }

  }

}

고친 코드대로 하면 answer에 작은 수 부터 들어가므로 answer을 따로 오름차순 정렬 해 줄 필요가 없다.

 

3-3번

import java.util.Scanner;

 

public class Main {

  public int solution(int n, int m, int[] arr){

    int answer = Integer.MIN_VALUE;

    int sum = 0;

    for(int i = 0; i < m; i++){

      sum += arr[i];

    }

    answer = sum;

    for(int i = m; i < n; i++){

      sum += (arr[m] - arr[i - m]);

      answer = Math.max(answer, sum);

    }

    return answer;

  }

  public static void main(String[] args){

    Main t = new Main();

    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();

    }

    in.close();

    System.out.print(t.solution(n, m, arr));

  }

}