코딩 테스트 합격자 되기 - week 1

1) 배열 정렬하기

• 정수 배열의 길이는 2 이상 10^5 이하입니다.
•  제약조건
  • 정수 배열의 길이는 2 이상 10^5 이하
  • 정수 배열의 각 데이터 값은 -100,000 이상 100,000 이하

public static int[] solution(int[] arr) {
    int[] copy = arr;
    Arrays.sort(copy);
    return arr;
}

 

• 문제 분석
  • 데이터의 최대 갯수는 10^5.
  • 컴퓨터가 1초당 하는 연산은 1억 (10^8).
  • 만약에 제한 시간이 3초면, 총 3억번의 연산 이하로 해야함..!
    • O(N^2) = O(10^5)^2 = O(10^10) -> 100억
      • 제한시간이 3초였으면 3억번의연산 이하로 해야하는데, O(N^2) 알고리즘을 사용하면 10^10 (100억)으로 최대 연산이 갈 수 있음! 그래서 O(N^2)는 제외.
    •  O(N log N) = O(10^5 log 10^5) -> O(10^5 * 17)-> 170만번  
      • 170만번은 3억번의 연산 이하여서 O(N log N)의 알고리즘(혹은 그 이하)를 사용할 수 있음!
• 그래서 실제 문제를 풀 때는 문제지에 적힌 실제 제한 시간(Time Limit)을 확인하고, 그 시간 안에 N을 넣었을 때 연산 횟수가 1억~수억 번을 넘지 않는지 체크하는 습관을 들이는 것이 중요함

 

2) 배열 제어하기

public static int[] solution(int[] arr) {
    return Arrays.stream(arr)
            .distinct() // 중복 제거
            .boxed()// 내림차순 하기 위해 reference type으로 변환
            .sorted(Collections.reverseOrder()) // 내림차순
            .mapToInt(Integer::intValue) // reference -> primitie
            .toArray();
}

• 자바에는 이런식으로 코테에 유용한 표준 API들이 많고 굳이 직접 적지 않아도 됨
• 시간 복잡도
  • 중복 제거 (distinct) -> O(N)
  • 정렬(sort) -> O(N log N) 
  • 최종 시간 복잡도는 O(N log N)

3) 두개 뽑아서 더하기

public static int[] solution(int[] arr) {
    Set<Integer> set = new HashSet<>();
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            set.add(arr[i] + arr[j]);
        }
    }
    return set.stream()
            .sorted()
            .mapToInt(Integer::intValue)
            .toArray();
}

• 시간 복잡도
  • 이중for문
    • 총 실행 휫수는 (N(N-1))/2 = (N^2)/2 - N/2 -> 최종적으로 O(N^2)
  • 정렬
    • 정렬할 데이터는 N^2
    • 정렬 알고리즘 (.sorted)의 시간복잡도는 O(N log N)
    • 데이터는 N^2이므로 최종적으로 O(N^2 log N^2)가 됨
  • 그래서 이중for문 + 정렬은 O(N^2) + O(N^2 log N^2). 하지만 가장 큰 텀안 중요해서 최종적으로 O(N^2 log N^2)만 남음.
  • 최종 시간 복잡도는 O(N^2 log N^2)