백준 11656번 - 접미사 배열 / Go

문제: https://www.acmicpc.net/problem/11656

11656번: 접미사 배열

문제 설명

문제

접미사 배열은 문자열 S의 모든 접미사를 사전순으로 정렬해 놓은 배열이다.

baekjoon의 접미사는 baekjoon, aekjoon, ekjoon, kjoon, joon, oon, on, n 으로 총 8가지가 있고, 이를 사전순으로 정렬하면, aekjoon, baekjoon, ekjoon, joon, kjoon, n, on, oon이 된다.

문자열 S가 주어졌을 때, 모든 접미사를 사전순으로 정렬한 다음 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다.

출력

첫째 줄부터 S의 접미사를 사전순으로 한 줄에 하나씩 출력한다.

예제 입력 1 복사

baekjoon

예제 출력 1 복사

aekjoon
baekjoon
ekjoon
joon
kjoon
n
on
oon
​

출처

• 문제를 만든 사람: baekjoon

알고리즘 분류

• 문자열
• 정렬

 

---

정답

package main

import (
	"bufio"
	"os"
	"sort"
	"strings"
	"testing"
)

func main() {
	rd := bufio.NewReader(os.Stdin)
	wr := bufio.NewWriter(os.Stdout)

	word := scan11656(rd)

	_, _ = wr.WriteString(solution11656(word))
	_ = wr.Flush()
}

func solution11656(word string) (result string) {
	strArr := make([]string, 0, len(word))
	for i := range word {
		strArr = append(strArr, word[i:])
	}

	sort.Slice(strArr, func(i, j int) bool {
		return strArr[i] < strArr[j]
	})

	result = strings.Join(strArr, "\n")
	return
}

func scan11656(rd *bufio.Reader) string {
	str, _ := rd.ReadString('\n') // 여기서 text는 마지막에 줄바꿈 문자를 포함하므로
	str = strings.TrimSpace(str)  // 줄바꿈 문자를 제거해야 함
	return str
}

func Benchmark11656(b *testing.B) {
	for i := 0; i < b.N; i++ {
		solution11656("baekjoon")
	}
}

func Test_solution11656(t *testing.T) {
	type args struct {
		word string
	}
	tests := []struct {
		name       string
		args       args
		wantResult string
	}{
		{name: "", args: args{word: "baekjoon"}, wantResult: "aekjoon\nbaekjoon\nekjoon\njoon\nkjoon\nn\non\noon"},
	}
	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			if gotResult := solution11656(tt.args.word); gotResult != tt.wantResult {
				t.Errorf("solution11656() = %v, want %v", gotResult, tt.wantResult)
			}
		})
	}
}

 

---

풀이

 단어에 포함되는 모든 접미사를 뽑아서 사전 순으로 출력하는 문제이다.

 

 Golang은 python과 달리 정렬 기능이 단순하지 않다. 그러나 사용이 어렵지만은 않은데 sort.Slice() 함수를 이용하여 정렬 기준만 입력해주면 간단히 해결할 수 있다. 문자열 비교를 통해 사전 순 비교가 가능하므로 바로 해결 가능하다.