[프로그래머스 Java] K번째 수

코딩테스트 연습 - K번째수

⏱소요 시간 - 1시간 5분

 

🔑해결 방법

 

이차원 배열과의 관계를 찾아내야 해서 엄~청 헷갈렸던 문제

이차원 배열의 요소의 인덱스를 적어놓고, 인덱스와 매치하면서 for문을 차분히 돌려보면 규칙을 발견할 수 있다.

항상 이차원 배열만 만나면 뇌가 굳는 것 같다ㅠㅠ 평정심을 갖고 문제를 풀어야겠다.

 

문제는 다음과 같은 흐름으로 전개된다.

 

1. 주어진 배열을 i번째 숫자 ~ j번째 숫자까지 잘라 array2[] 배열에 저장한다.

2. 자른 배열을 정렬한다.

3. 정렬된 배열에서 k번째 수를 answer[] 배열에 저장한다.

 

이러한 흐름이 for문 안에 들어가서 i = 0, i = 1, i = 2.... 순으로 반복된다.

 

int[] array2 = Arrays.copyOfRange(array, commands[i][0] - 1, commands[i][1]);
				
Arrays.sort(array2);
			
answer[i] = array2[commands[i][2] - 1];

 

풀어서 설명해보자면, 다음과 같은 2차원 배열을 살펴보자.

 

첫 번째 자르는 시작 기준이 되는 2, 4, 1의 열 인덱스는 0,0,0으로 고정된다.

행 인덱스만 0,1,2로 증가한다.

 

두 번째 자르는 마지막 기준이 되는 5,4,7의 열 인덱스는 1,1,1로 고정된다.

행 인덱스만 0,1,2로 증가한다.

 

세 번째 k번째 숫자를 구하는 3,1,3의 열 인덱스는 2,2,2로 고정된다.

행 인덱스만 0,1,2로 증가한다.

 

 

이와 같은 흐름을 파악하면 쉽게 수식을 만들어낼 수 있다.

배열의 인덱스는 0부터 시작하기 때문에 경우에 따라 -1씩 해주었다는 것만 기억하면 될 것이다.

 

 

🔎소스 코드

 

Arrays.copyOfRange() : 배열의 일부를 복사해서 새로운 배열을 만들어 반환 (끝 범위는 포함하지 않음)

 

Arrays 클래스

 

package step1;

import java.util.Arrays;

// K번째 수
public class Ex06 {

	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 } };
		
		System.out.println(solution(array, commands));

	}
	
	public static int[] solution(int[] array, int[][] commands) {
		
		int[] answer = new int[commands.length];
	
		for(int i = 0; i < commands.length; i++) {
			
			int[] array2 = Arrays.copyOfRange(array, commands[i][0] - 1, commands[i][1]);
				
			Arrays.sort(array2);
			
			answer[i] = array2[commands[i][2] - 1];

		}

		return answer;
		
	}

}