목표
코딩테스트 연습하면서 어떻게하면 조금더 효율적으로 코드를 작성할 수 있을지 공부하고 어떤 알고리즘을 쓰면 조금더 효율성이 높을지를 조금더 생각하면서 공부하는게 내 목표이다.
문제
내가 생각했을때 문제에서 원하는부분
배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 한다.
array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면
array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]이다.
1에서 나온 배열을 정렬하면 [2, 3, 5, 6]이다.
2에서 나온 배열의 3번째 숫자는 5이다.
배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때,
commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 해준다.내가 이 문제를 보고 생각해본 부분
commands 배열을 순회하면서 각 commands에 대해 처리해준다.
각 commands는 [i,j,k] 형태이다. 여기서 i는 시작 인덱스, j는 끝 인덱스, k는 정렬 후 선택할 숫자의 인덱스이다.
array 배열을 i번째부터 j번째까지 slice 해서 잘라준다.
잘린 배열을 정렬한다.
정렬된 배열의 k번째 숫자를 선택한다.
이렇게 구한 숫자를 결과 배열에 차례대로 담아 리턴해준다.코드로 구현
import java.util.Arrays;
class Solution {
public int[] solution(int[] array, int[][] commands) {
int[] answer = new int[commands.length];
for(int i = 0; i < commands.length; i++) {
int[] command = commands[i];
int start = command[0] - 1;
int end = command[1];
int index = command[2] - 1;
int[] sliced = Arrays.copyOfRange(array, start, end);
Arrays.sort(sliced);
answer[i] = sliced[index];
}
return answer;
}
}시간복잡도 O(NlogN)를 사용했다.
장점으로는
전체 수행시간이 N에 대한 log와 선형 시간만 소요된다.
입력 데이터랑이 커져도 시간 복잡도가 급격히 증가하지 않는다.
일반적으로 좋은 효율의 정렬 알고리즘을 사용한다.
단점으로는
최악의 경우 O(N^2)의 시간복잡도 발생한다.
입력데이터가 이미 정렬되어 있다면 효율적이지 못하다.
추가메모리 사용이 발생할 수 있다.
다음에 적용해보고싶은 시간복잡도는
정렬 알고리즘을 사용한다거나
이진 검색 알고리즘사용하거나
분할 정복 접근
Memorization 기법을 사용해보고싶다.
마무리
오늘 하루도 이렇게 알고리즘을 공부하면서 조금더 알고리즘을 생각해볼 수 있는 계기가 된것같아서 기쁘고 비기너 레벨을 풀고있지만 그동안 알고리즘 공부를 너무 안했다는 생각이 너무 많이 들었다. 코딩테스트 문제를 많이 풀다보면 언젠간 나도 아 이문제는 어떤 알고리즘을 사용하면 빠르지 않을까 라고 생각하는 날이 오지 않을까 싶다.
Junior backend developer