Java 프로그래머스 K번째 수 자바

문제출처 : https://school.programmers.co.kr/learn/courses/30/lessons/42748

프로그래머스

---

[문제 설명]

배열 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 하도록 solution 함수를 작성해 주세요.

[제한사항]

• array의 길이는 1 이상 100 이하입니다.
• array의 각 원소는 1 이상 100 이하입니다.
• commands의 길이는 1 이상 50 이하입니다.
• commands의 각 원소는 길이가 3입니다.

[입출력 예]

array	commands	return
[1, 5, 2, 6, 3, 7, 4]	[[2, 5, 3], [4, 4, 1], [1, 7, 3]]	[5, 6, 3]

입출력 예#1

[1, 5, 2, 6, 3, 7, 4]를 2번째부터 5번째까지 자른 후 정렬합니다. [2, 3, 5, 6]의 세 번째 숫자는 5입니다.

입출력 예#2

[1, 5, 2, 6, 3, 7, 4]를 4번째부터 4번째까지 자른 후 정렬합니다. [6]의 첫 번째 숫자는 6입니다.

입출력 예#3

[1, 5, 2, 6, 3, 7, 4]를 1번째부터 7번째까지 자릅니다. [1, 2, 3, 4, 5, 6, 7]의 세 번째 숫자는 3입니다.

 

[문제 풀기 전 생각 및 정리]

• 2차원 배열인 commands안의 각각의 인덱스는 1차원 배열이다.
• 그 1차원 배열의 1번째 숫자는 array  배열 자르는 시작위치, 2번째 숫자는 array  배열 자르는 마지막 위치, 3번째 숫자는 앞에서 자른 배열 중 오름차순 기준으로 3번째 위치한 수이다.
• array 배열은 어떻게 자를 것인가?
• 2차원 배열 commands 배열을 반복문을 통해 어떻게 순차적으로 값을 사용하고 정렬할 것인가?

[나의 풀이]

import java.util.ArrayList;
import java.util.Collections;

public class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];

        for(int i = 0; i < commands.length; i++){
            ArrayList<Integer> list = new ArrayList<>();

            for(int j = commands[i][0] - 1; j < commands[i][1]; j++){
                list.add(array[j]);
            }

            Collections.sort(list);

            answer[i] = (int) list.get(commands[i][2]-1);
        }

        return answer;
    }
}

• 자른 위치는 commands[0][0]인 2부터 , commands[2][0]인 5까지 자름.
• 이때, 1차원 배열 array는 index가 0부터 시작하기 때문에, 2부터 잘라야 하므로 index=1 인 값을 list에 add
• 변수 j에 대한 반복문이 돌면 [5, 2, 6, 3]의 배열이 생성되고, Collections.sort(list)로 오름차순 정렬이 되면서, [2, 3, 5, 6]이 된다.
• 그리고 정답 변수 배열에는 list의 3번째 값이 commands[i][2]-1 값인 5를 저장
• 변수 i에 대한 반복문이 모두 돌고 나면 answer = [5, 6, 3]이 나오게 되는 것이다.

하지만 이 소스는 너무 번잡하다.

for문 안에 내용들을 별도의 메서드로 빼면 어떨까? 라는 생각이 들어 아래와 같이 코드를 리팩토링 해봤다.

import java.util.ArrayList;
import java.util.Collections;
class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];

        for(int i = 0; i < commands.length; i++){
            answer[i] = result(commands[i][0], commands[i][1], commands[i][2], array);
        }

        return answer;
    }

    public int result(int st, int ed, int seq, int[] array){
        ArrayList<Integer> list = new ArrayList<>();

        for(int j = st - 1; j < ed; j++){
            list.add(array[j]);
        }

        Collections.sort(list);

        return (int) list.get(seq-1);
    }
}

첫 번째 코드 중 첫번째 for문의 안의 반복되는 내용을 result 메서드를 별도로 분리했다.

그래서 연산은 result 메서드에서만 처리해서 answer 배열에 저장하는 방식을 채택했다.

뭐, 사람마다 코딩하는 방식이 다르겠지만, 개인적으로 나는 이렇게 메서드를 별도로 분리하는 것이 직관적으로도 보기 편하고,

상황에 따라 코드가 정리되는 기분이라 이 방식을 추천한다!

[다른 사람들의 풀이]

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[] temp = Arrays.copyOfRange(array, commands[i][0]-1, commands[i][1]);
            Arrays.sort(temp);
            answer[i] = temp[commands[i][2]-1];
        }

        return answer;
    }
}

역시 라이브러리의 힘...

위의 내 메서드에서 Collections.sort 역할을 제외하고 나머지 기능을 Arrays.copyOfRange라는 메서드가 하고 있다.

사용법은 다음과 같다.

Arrays.copyOfRange : 특정 배열의 원하는 범위만큼 복사하여 새로운 배열을 만드는 메서드함수
Arrays.copyOfRange(원본 배열, 복사하려는 시작 요소의 인덱스, 복사하려는 마지막 요소의 인덱스의 바로 다음 인덱스)

물론 이런 Java API를 사용하면 소스는 간결해지나, 속도는 훨씬 느려진다..

API를 쓰는 게 잘못된 게 아니지만, 성능 확인을 하면서 어떤 게 지금 프로그램에 적합한지 찾는 것도 중요한 작업 중에 하나인 듯하다.

[정리]

개인 피셜 난이도 : ★☆☆☆☆

리스트와 배열을 적절히 사용해야 하는 것을 감안하면 다른 문제들 별 한 개짜리랑 비교한다면,

이 문제는 별 1.3~1.5 개 정도는 되는 것 같다.

다른 분들이 저런 API를 알려주신 덕에 이렇게 배우고 알아감에 정말 감사하다!

그래도 저런 API를 알기 전에는, 본인만의 로직으로 하드코딩이 되지 않는 선에서

직접 짜보는 것이 알고리즘 문제를 푸는데 도움이 더 되는 것 같긴 하다.

 

언제나 새로운 정보 공유와 잘못된 정보

비판/지적/태클은 환영입니다!

 

끝.