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

[프로그래머스] #.12915 - 문자열 내 마음대로 정렬하기

문자열 내 마음대로 정렬하기

문제 설명

문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다. 예를 들어 strings가 ["sun", "bed", "car"]이고 n이 1이면 각 단어의 인덱스 1의 문자 "u", "e", "a"로 strings를 정렬합니다.

제한 조건

  • strings는 길이 1 이상, 50이하인 배열입니다.
  • strings의 원소는 소문자 알파벳으로 이루어져 있습니다.
  • strings의 원소는 길이 1 이상, 100이하인 문자열입니다.
  • 모든 strings의 원소의 길이는 n보다 큽니다.
  • 인덱스 1의 문자가 같은 문자열이 여럿 일 경우, 사전순으로 앞선 문자열이 앞쪽에 위치합니다.

입출력 예

strings n return
["sun", "bed", "car"] 1 ["car", "bed", "sun"]
["abce", "abcd", "cdx"] 2 ["abcd", "abce", "cdx"]

문제 해결하기

5번째 조건은 중요하다. 입출력 예에서 두 번째 예에서 abce, abcd 의 인덱스 2 에 해당하는 값은 c 인데, 두 문자가 서로 같기 때문에 문자열 자체에 대해서 사전순으로 정렬해야 한다. 따라서 사전순으로 인덱스 3 인 de 보다 앞에 있으므로 먼저 나오는 것이다. 이렇게 정렬에 특정 조건이 있는 경우 직접 정렬 인터페이스를 구현해보는 것도 좋다. 또한 strings, n 이 세트로 묶여있기 때문에 하나의 데이터 타입으로 만들어보자.

sort.Interface

sort.Interface 인터페이스는 sort.Sort() 등 정렬과 관련된 함수를 사용할 때 파라매터로 넣을 수 있는 타입이다. 이를 구현하면 커스텀 정렬함수를 만들어낼 수 있다.

$ go doc sort.Interface
package sort // import "sort"

type Interface interface {
        // Len is the number of elements in the collection.
        Len() int
        // Less reports whether the element with
        // index i should sort before the element with index j.
        Less(i, j int) bool
        // Swap swaps the elements with indexes i and j.
        Swap(i, j int)
}
    A type, typically a collection, that satisfies sort.Interface can be sorted
    by the routines in this package. The methods require that the elements of
    the collection be enumerated by an integer index.

StringSlice

StringSlice 타입은 이름은 Slice 지만 사실 구조체다. 외부에서 들어온 strings, n 변수를 갖는다.

type StringSlice struct {
	strings []string
	n       int
}

Len(), Swap(i, j int)

두 메서드는 각각 길이와 정렬시 데이터 교환처리를 명시해주면 된다.

func (s StringSlice) Len() int {
	return len(s.strings)
}

func (s StringSlice) Swap(i, j int) {
	s.strings[i], s.strings[j] = s.strings[j], s.strings[i]
}

Less(i, j int) bool

이 메서드는 별도로 알아본다. 제한 조건을 채우기 위해서는 Less() 메서드의 구현이 중요하다. strings 필드는 문자열이 배열 형태로 들어가 있고, 각 원소에서 인덱스 n 을 기준으로 정렬을 실행해야 한다. 또한 인덱스 n 이 같은 문자를 가진 경우 문자열 자체를 사전순으로 나열해야 한다. 코드는 다음과 같다.

func (s StringSlice) Less(i, j int) bool {
	if s.strings[i][s.n] == s.strings[j][s.n] {
		return s.strings[i] < s.strings[j]
	}
	return s.strings[i][s.n] < s.strings[j][s.n]
}

문자가 서로 같은 경우에 대해서는 s.strings[i][s.n] 이 아닌 s.strings[i] 를 연산자로 함을 주목하자.

func solution(strings []string, n int) []string

sort.Sort() 함수를 호출하여 정렬된 strings 변수를 반환하면 끝이다. sort.Sort() 함수는 반환대신 원본을 변경하기 때문에 이 점에 대해서는 주의하자.

func solution(strings []string, n int) []string {
	sort.Sort(StringSlice{strings, n})
	return strings
}

func TestSolution(t *testing.T) {
	cases := []struct {
		strings []string
		n       int
		expect  []string
	}{
		{[]string{"sun", "bed", "car"}, 1, []string{"car", "bed", "sun"}},
		{[]string{"abce", "abcd", "cdx"}, 2, []string{"abcd", "abce", "cdx"}},
	}
	for _, c := range cases {
		r := solution(c.strings, c.n)
		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("got %#v, want %#v", v, c.expect[i])
			}
		}
	}
}

더 읽을거리

github.com/pronist/al.go/tree/main/programmers/_12915

programmers.co.kr/learn/courses/30/lessons/12915