백준 1543번 - 문서 검색 / Go

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

1543번: 문서 검색

문제 설명

문제

세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한다. 예를 들어, 문서가 abababa이고, 그리고 찾으려는 단어가 ababa라면, 세준이의 이 함수는 이 단어를 0번부터 찾을 수 있고, 2번부터도 찾을 수 있다. 그러나 동시에 셀 수는 없다.

세준이는 문서와 검색하려는 단어가 주어졌을 때, 그 단어가 최대 몇 번 중복되지 않게 등장하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문서가 주어진다. 문서의 길이는 최대 2500이다. 둘째 줄에 검색하고 싶은 단어가 주어진다. 이 길이는 최대 50이다. 문서와 단어는 알파벳 소문자와 공백으로 이루어져 있다.

출력

첫째 줄에 중복되지 않게 최대 몇 번 등장하는지 출력한다.

예제 입력 1 복사

ababababa
aba

예제 출력 1 복사

2

예제 입력 2 복사

a a a a a
a a

예제 출력 2 복사

2

예제 입력 3 복사

ababababa
ababa

예제 출력 3 복사

1

예제 입력 4 복사

aaaaaaa
aa

예제 출력 4 복사

3
​

출처

• 문제를 번역한 사람: baekjoon
• 데이터를 추가한 사람: chan120317, jaehoo1
• 문제의 오타를 찾은 사람: hist0613

알고리즘 분류

• 문자열
• 그리디 알고리즘
• 브루트포스 알고리즘

 

---

정답

package main

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

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

	document := scan1543(rd)
	word := scan1543(rd)

	_, _ = wr.WriteString(solution1543(document, word))
	_ = wr.Flush()
}

func solution1543(document, word string) (result string) {
	return strconv.Itoa(strings.Count(document, word))
}

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

func Benchmark1543(b *testing.B) {
	for i := 0; i < b.N; i++ {
		solution1543("ababababa", "aba")
	}
}

func Test_solution1543(t *testing.T) {
	type args struct {
		document string
		word     string
	}
	tests := []struct {
		name       string
		args       args
		wantResult string
	}{
		{name: "", args: args{document: "ababababa", word: "aba"}, wantResult: "2"},
		{name: "", args: args{document: "a a a a a", word: "a a"}, wantResult: "2"},
		{name: "", args: args{document: "ababababa", word: "ababa"}, wantResult: "1"},
		{name: "", args: args{document: "aaaaaaa", word: "aa"}, wantResult: "3"},
	}
	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			if gotResult := solution1543(tt.args.document, tt.args.word); gotResult != tt.wantResult {
				t.Errorf("solution1543() = %v, want %v", gotResult, tt.wantResult)
			}
		})
	}
}

 

 

---

풀이

 문자열에 특정 단어가 몇번 들어가는지 확인하는 문제이다. 

 

 "a a a a a" 같은 경우 "a a"가 4번 들어있는데, 글자를 중복해서 확인하지 않아야하는게 중요한 문제이다.

 

 처음에는 정규식을 이용해서 풀었다.

package main

import (
	"bufio"
	"os"
	"regexp"
	"strconv"
	"strings"
)

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

	document := scan1543(rd)
	word := scan1543(rd)

	_, _ = wr.WriteString(solution1543(document, word))
	_ = wr.Flush()
}

func solution1543(document, word string) (result string) {
	rgx, _ := regexp.Compile(word)
	stringArray := rgx.FindAllString(document, -1)
	return strconv.Itoa(len(stringArray))
}

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

그런데 알고보니 strings.Count()라는 메소드를 go에서 제공하고 있으며 해당 메소드가 시간이 4ms로 더 우수한 것을 확인 할 수 있다.