[Go] 백준 1141번 접두사 (HasPrefix)

문제

https://www.acmicpc.net/problem/1141

입력

첫째 줄에 단어의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 단어가 주어진다. 단어는 알파벳 소문자로만 이루어져 있고, 길이는 최대 50이다. 집합에는 같은 단어가 두 번 이상 있을 수 있다.

출력

첫째 줄에 문제의 정답을 출력한다.

---

문제 풀이

문제 해석 및 계획

처음 생각은 입력을 슬라이스에 저장하고 반복문을 통하여 접두사가 될 수 있는지 확인하여 부분집합에 포함시키지 않는 방법을 생각하였습니다.

두 번째 생각은 tree형식으로 자료구조를 잡고 가지의 수를 세면 된다는 것을 알았습니다.

오답 노트

입력받은 문자열끼리 접두사가 되는 경우 relate로 기록하고 부분집합에 포함하지 못하도록 ban에 기록하였습니다. 테스트 케이스들은 성공을 하였지만 반례를 찾지 못하였습니다. 3중 for문 중 2번째 for문에서 정렬이 되지 않은 slice를 항상 0부터 확인하여 오류가 있는 것으로 보입니다.

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main(){
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)

	defer writer.Flush()

	var N int
	fmt.Fscan(reader, &N)

	strGroup := make([]string, N)
	for i:=0 ; i<N ; i++{
		fmt.Fscan(reader, &strGroup[i])
	}
	relate := make([][]int,N)
	for i:=0 ; i<N ; i++ {
		for j:=0 ; j<N ; j++ {
			if i == j {
				continue
			}
			check := checkInclude(strGroup[i], strGroup[j])
			if check {
				relate[i] = append(relate[i], j)
			}
		}
	}
	answer := 0
	for i:=0 ; i<N ; i++ {
		group := []int{i}
		ban := make([]bool,N)
		for len(group) >0  {
			now := group[0]
			group = group[1:]
			ban[now] = true
			for j:=0 ; j<len(relate[now]) ; j++ {
				ban[relate[now][j]]=true
			}
			for j:=0 ; j<N ; j++{
				if ban[j] == false {
					group = append(group, j)
					break
				}
			}
		}
		if answer < len(group){
			answer = len(group)
		}
	} 

	fmt.Fprint(writer, answer)
}

func checkInclude(strA, strB string) bool{
	
	length := len(strA)
	if  len(strB) < length  {
		length = len(strB)
	}

	include := true
	for k:=0 ; k<length ; k++{	
		if strA[k] != strB[k]{
			include = false
			break
		}
	}
	
	return include
}

정답

위에서 생성한 checkInclude가 go언어에서 strings패키지의 HasPrefix로 존재하였습니다. 입력을 길이 순서로 정렬하고 짧은 문자열이 나머지 큰 문자열에 포함된다면 그 값은 뿌리가 될 것이기에 전체 개수에서 줄여나가는 방식을 선택하였습니다.

두 번째 생각이었던 가지를 뻗어 나가는 방식에서 뿌리가 되는 문자열을 제거하는 방식을 선택하였습니다.

package main

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

func main() {
    reader := bufio.NewReader(os.Stdin)
    writer := bufio.NewWriter(os.Stdout)

    defer writer.Flush()

    var N int
    fmt.Fscan(reader, &N)

    strGroup := make([]string, N)
    for i := 0; i < N; i++ {
        fmt.Fscan(reader, &strGroup[i])
    }

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

    answer := N

    for i := 0; i < N; i++ {
        for j := i + 1; j < N; j++ {
            if strings.HasPrefix(strGroup[j], strGroup[i]) {
                answer--
                break
            }
        }
    }

    fmt.Fprint(writer, answer)
}

---

느낀 점

언어의 모든 패키지를 기억할 수 없지만 오랜 시간 고민하고 찾아낸 패키지는 기억에 오래 남는 편입니다. 또한 알고리즘 문제를 풀 때 필요한 패키지들이 많이 겹치는 편입니다. 이번에 HasPrefix라는 메서드를 몰랐을 때 checkInclude라는 함수를 생성하여 사용하긴 하였지만 패키지를 사용한다면 보다 빠르고 간결하게 코드를 짤 수 있기에 코딩 테스트를 통하여 편리하고 유용한 패키지를 발견할 수 있겠다고 생각되었습니다.