[알고리즘/Programmers] LV1. k번째 수

Programmers LV1. k번째 수

 

문제 설명

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.

예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면

1. array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
2. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
3. 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]

 

728x90

 

사용 언어

Java

해결 방법

1. i,j 길이만큼 ArrayList에 담아 정렬 후 answer에 k번째 수 담기 (내가 푼 방법)

2. Arrays.copyOrRange() 메서드 사용

 

알고리즘 로직은 간단하다.
문제 요구사항 그대로
array 배열의 i번째~k번째 위치를 뽑고, k번째 위치의 값을 결과에 포함하면 된다.

이 작업을 command 길이만큼 반복해서 결과를 리턴한다.

 

알고리즘 자체는 안어려운데 어떻게 구현하느냐의 차이인 것 같다.

나는 무엇이 적절한지 감이 안와서 무자비하게(..) 1번 방법으로 시도해보았다.

다른 풀이를 보니 Arrays의 메서드를 활용하면 풀이 방법이 아주 간단해진다. (수행시간이 더 나은지는 모르겠지만..?)

 

알게된 것

• 배열 API 복사 메서드
  • Arrays.copyOf(배열, 복사할 길이)
  • Arrays.copyOfRange(배열, 복사시작인덱스, 복사끝인덱스)

 

코드

public class test_42748 {
	public static void main(String[] args) {
		int[] array = {1, 5, 2, 6, 3, 7, 4};
		int[][] commands = {{2, 5, 3}, {4, 4, 1}, {1, 7, 3}}; // i,j,k

		int[] result = solution(array, commands);

		for(int i=0; i< result.length; i++) {
			System.out.print(result[i] + ", ");
		}
	}
	// 내가 푼 풀이
	public static int[] solution(int[] array, int[][] commands) {
		int[] answer = new int[commands.length];

		List<Integer> list;

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

			// i~j 번째 자르기
			int i = commands[l][0];
			int j = commands[l][1];
			int k = commands[l][2];
			for(int a=i-1; a<j; a++) { list.add(array[a]); }

			// 정렬하기
			Collections.sort(list);

			// k번째 수 answer에 담기
			answer[l] = list.get(k-1);
		}
		return answer;
	}

	// Arrays.copyOfRange
	public static int[] solution2(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;
	}
}

 

---

 

분명 그리 어려운 문제는 아니다. 근데 빠릿빠릿 풀리지가 않는다. 그랬던 이유는 '자바 문법의 약함'인 것 같다. 하나 둘 익혀가는 문법들을 까먹지 않고 자주 들여다보고 어떻게 쓰는지 계속 익혀야할 것 같다.