[JAVA] String 문자열 연결 연산자 vs ArrayList .add 시간복잡도 비교

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

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

 

이 코드로 제출하니 Time Limit Exceeded 가 나왔다.

해당 오류는 시간이 초과되었다는건데, O(n)으로 풀어야 할 문제를 O(n^2)으로 풀었거나 할 때 나온다.

import java.util.*;

 

public class Main {

  public String solution(int n, int k, int[] arr){

    String answer = "";       ////강사님 코드와 다른 부분

    HashMap<Integer, Integer> map = new HashMap<>();

    for(int i = 0; i < k-1; i++)

      map.put(arr[i], map.getOrDefault(arr[i], 0)+1);

    int lt = 0;

    for(int rt = k-1; rt < n; rt++){

      map.put(arr[rt], map.getOrDefault(arr[rt], 0)+1);

 

      answer = answer + 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 t = new Main();

    Scanner in = new Scanner(System.in);

   

    int n = in.nextInt();

    int k = 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, k, arr));

  }

}

 

강사님의 코드와 비교해보니 solution 리턴값 변수형이 달랐다.

String answer = "";

answer = answer + map.size() + " ";    //내가 짠 코드

 

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

answer.add(map.size());     //강사님이 짠 코드

둘이 뭐가 다르길래 타임아웃이 났을까?

 

 

나는 answer 을 String 형의 변수로 선언하고 문자열 연결 연산자를 사용해

출력 할 항목이 나올 때 마다 answer에 추가해주는 방법을 썼다.

Java의 문자열은 변경될 수 없기 때문에 해당 방법을 사용하면

+연산자를 사용할 때 마다 인스턴스가 새로 생성되는데(인스턴스는 heap영역에 생성된다),

두 문자열을 연결할 경우에는 양쪽의 내용을 모두 복사해서 붙여야 하므로 시간복잡도가 O(n^2)가 된다.

 

 

ArrayList는 Collection 프레임워크에 속해 있으며 객체 배열을 사용한다. 동적 할당이라 저장공간 크기가 가변적이며, 물리 공간과 논리 공간이 동일하기 때문에 get, set 메서드를 이용한 인덱스 연산자를 사용할 수 있다.

배열의 끝에 원소를 삽입할 때 시간복잡도가 O(n)이다.

 

 

그래서 내가 처음 방법으로 시도했을 때 시간초과가 난 것이었다.

자료형과 동작마다 시간복잡도가 다르다는 걸 염두에 두고 코드를 짜야된다는 걸 깨달았다...

 

 

 

 

 

*참고사이트*

https://mong9data.tistory.com/132  (배열 자료형에 대한 시간복잡도와 여러 정보가 굉장히 잘 정리되어 있음)

https://xonmin.tistory.com/31

https://st-lab.tistory.com/161

https://heannim-world.tistory.com/95