[프로그래머스] - K번째 수(C#)

K번째 수

오늘은 정렬 카테고리에 포함되어 있는 "K번째 수" 문제를 풀어보도록 하겠습니다. 문제의 제목만으로는 어떤 문제인지 잘 모르겠지만, 살펴보겠습니다.

 

문제 설명

배열 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, 5, 2, 6, 3, 7, 4]를 2번째부터 5번째까지 자른 후 정렬합니다. [2, 3, 5, 6]의 세 번째 숫자는 5입니다.
[1, 5, 2, 6, 3, 7, 4]를 4번째부터 4번째까지 자른 후 정렬합니다. [6]의 첫 번째 숫자는 6입니다.
[1, 5, 2, 6, 3, 7, 4]를 1번째부터 7번째까지 자릅니다. [1, 2, 3, 4, 5, 6, 7]의 세 번째 숫자는 3입니다.

 

시작 코드

using System;

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

 

나의 풀이

using System;

public class Solution {
    public int[] solution(int[] array, int[,] commands) {
        int[] answer = new int[commands.GetLongLength(0)];
        
        for(int i = 0; i < commands.GetLength(0); i++)
        {
            int start = commands[i,0];
            int end = commands[i,1];
            int find = commands[i,2];
            
            int[] temp = new int[end-start+1];
            for(int a = 0; a < temp.Length; a++) { temp[a] = array[a+start-1]; }
            Array.Sort(temp);
            answer[i] = temp[find-1];
        }
        return answer;
    }
}

 

코드 분석

int형 배열 array와 이차원배열 commands가 주어지며 코드가 시작됩니다. int형 배열 answer에  commands의 행의 길이로 선언해주고, for문을 행의 길이만큼 0부터 돌려줍니다. start, end, find에 각각 commands의 0, 1, 2번째 수를 넣어줍니다.

int형 배열 temp를 만들고, 배열의 길이를 end-start+1로 정해줍니다. for문을 하나 더 작성하여 a를 temp의 길이만큼 돌립니다. 그 안에서는 temp[a]에 array[a+start-1]을 실행해줍니다. Array.Sort()를 사용하여 temp를 정렬해주고, answer[i]에 temp[find-1]을 넣어줍니다. 최종적으로 answer를 리턴하면서 끝이 납니다.

 

풀이 설명

array는 검색할 수, commands는 검색하는 방법을 정의해 놓은 수를 나타내는 배열입니다. commands의 수는 순서대로 시작점과 종점 그리고 그 중 몇번째 수를 찾을 것인가를 나타냅니다. 예시를 통해 살펴보겠습니다. 코드를 처음 실행하게 되면 start, end, find는 각각 2, 5, 3으로 할당되고 temp의 길이는 4가 됩니다. for문으로 a를 temp의 길이까지 돌리면 temp[0 ~ 3]에 array[1 ~ 4]까지 들어가게 됩니다. 그렇게 만들어진 temp배열은 [5, 2, 6, 3]입니다. Sort로 오름차순 정렬해주면 [2, 3, 5, 6]이 되고, answer[0]에 temp[2]를 넣어 반환하며 끝나게 됩니다. temp[2]는 5입니다. 이런 방식으로 상위 for문까지 전부 해주면, 5, 6, 3이 최종적으로 answer배열에 저장되어 반환됩니다.

 

<NEXT>

오늘은 정렬 카테고리의 "K번째 수" 문제를 풀어보았습니다. 문제가 직관적이어서 방법을 안다면 쉽게 풀 수 있지만, 방법을 모른다면 어렵게 느껴질 수 있는 문제입니다. 다음에는 월간 코드 챌린지 시즌1 출제문제 중 하나인 "두 개 뽑아서 더하기" 문제를 다뤄보도록 하겠습니다. 감사합니다.