백준 1764번 - 듣보잡 / Go

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

1764번: 듣보잡

문제 설명

문제

김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.

듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.

출력

듣보잡의 수와 그 명단을 사전순으로 출력한다.

예제 입력 1 복사

3 4
ohhenrie
charlie
baesangwook
obama
baesangwook
ohhenrie
clinton

예제 출력 1 복사

2
baesangwook
ohhenrie
​

출처

• 문제를 만든 사람: author5

알고리즘 분류

• 자료 구조
• 문자열
• 정렬
• 해시를 사용한 집합과 맵

 

---

정답

package main

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

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

	strArr := strings.Split(scan1764(rd), " ")
	n, _ := strconv.Atoi(strArr[0])
	m, _ := strconv.Atoi(strArr[1])

	nArr := make([]string, 0, n)
	for i := 0; i < n; i++ {
		nArr = append(nArr, scan1764(rd))
	}

	mArr := make([]string, 0, m)
	for i := 0; i < m; i++ {
		mArr = append(mArr, scan1764(rd))
	}

	_, _ = wr.WriteString(strings.Join(solution1764(nArr, mArr), "\n"))
	_ = wr.Flush()
}

func solution1764(nArr, mArr []string) (result []string) {
	result = make([]string, 0, len(nArr))
	count := make(map[string]int)
	for _, s := range nArr {
		count[s]++
	}
	for _, s := range mArr {
		count[s]++
		if count[s] == 2 {
			result = append(result, s)
		}
	}

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

	result = append([]string{strconv.Itoa(len(result))}, result...)
	return
}

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

 

---

풀이

 문자열 두 그룹을 주고, 둘 다 포함되는 문자열을 반환하면 되는 문제이다.

 

 첫 N개의 문자열을 키로 하여 map[string]int 를 만들어서 값을 1을 증가시키고, 두 번째 M개의 문자열도 마찬가지로 1을 증가시켜 값이 2인 경우 반환하는 간단한 문제이다.