자료구조 & 알고리즘/프로그래머스

[al.go] #.42748 - 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,4],[1,7,3]] [5,6,3]

문제 해결하기

이 문제는 굉장히 간단하다. commands 의 원소 각각에서 Go 슬라이스의 인덱스로 따지자면 i-1 에서 j 까지 짜르고, 해당 배열을 정렬, k-1 에 해당하는 값을 반환하면 된다. 따라서 아래의 코드가 전부다.

func solution(array []int, commands [][]int) []int

아래의 코드에서 기존 배열에 대해 슬라이스로 자르고 곧 바로 정렬을 하려고 하면 문제가 생긴다. 주석에도 나와있듯이 같은 내부 배열 메모리를 사용하기 때문이다. Go 의 슬라이스는 내부적으로 배열을 가지고 있는데, sort.Ints() 함수는 원본을 변경하기 때문에 내부 배열이 정렬된다. 

func solution(array []int, commands [][]int) []int {
	var result []int

	for _, cmd := range commands {
		// p := array[cmd[0]-1:cmd[1]] 인 경우 같은 내부 공규 메모리 사용으로 정렬시 문제 발생
		p := append([]int{}, array[cmd[0]-1:cmd[1]]...)
		sort.Ints(p)

		result = append(result, p[cmd[2]-1])
	}
	return result
}

func TestSolution(t *testing.T) {
	cases := []struct {
		array    []int
		commands [][]int
		expect   []int
	}{
		{[]int{1, 5, 2, 6, 3, 7, 4}, [][]int{{2, 5, 3}, {4, 4, 1}, {1, 7, 3}}, []int{5, 6, 3}},
	}
	for _, c := range cases {
		r := solution(c.array, c.commands)
		if len(r) != len(c.expect) {
			t.Errorf("got %#v, want %#v", r, c.expect)
			return
		}
		for i, v := range r {
			if v != c.expect[i] {
				t.Errorf("#%d, got %#v, want %#v", i, r, c.expect)
			}
		}
	}
}

예를 들어 array 에 대해 [5,4,3,2,1] 가 들어있는 경우 array[1:4] 라고 처리하게 되면 [4,3,2] 가 나오고 이를 정렬하면 [2,3,4] 가 나온다. 그런데 여기서 같은 내부 배열을 공유하므로 최종적으로 array 에는 [5,2,3,4,1] 이 나오게 되는 것이다.

package main

import (
	"fmt"
	"sort"
)

func main() {
	array := []int{5, 4, 3, 2, 1}
	// p := append([]int{}, array[1:4]...)
	p := array[1:4]

	sort.Ints(p) // 이것은 내부 배열을 변경한다.
  
	fmt.Println(array) // -> [5,2,3,4,1]
}

이것이 Go 슬라이스가 가진 성질이다. 슬라이스는 그저 내부 배열의 에 지나지 않는다는 사실을 인지하자. 따라서 별도의 내부 배열을 사용하도록 처리해줄 필요가 있다. 위의 append[]int{}, ...) 는 그런 의미에서 쓰였다.

더 읽을거리

https://github.com/pronist/al.go/tree/main/programmers/_42748

https://programmers.co.kr/learn/courses/30/lessons/42748