[GoLang] 백준 1920번 수 찾기

개요

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

해당 문제는 5년 전 고등학생때 했었던 문제입니다.

하도 풀어도 시간초과가 발생해서 포기했던 기억이 나네요.

 

1년전에도 시간초과로... ^^

어떻게 하면 M개의 난수가 A배열에 있는 지를 찾는지가 관건인 문제였습니다.

지금 보니 시간 복잡도를 조금만 줄이면 되는 문제로 이진 탐색으로 해결했습니다.

 

이진 탐색 알고리즘

알고리즘을 배우면 가장 먼저 배우는 알고리즘으로 작년에 다시 시도했을 때도 알고 있던 알고리즘이었습니다.

이를 적용할 생각이 없던 게 아쉽네요

 

정의는 아래 그림으로 보시면 이해하는 것이 편할 겁니다.

이진탐색 나무위키 이미지

위하고 문제의 다른 점은 어떤 수들이 오는지 모르고 정렬되지 않고 입력된다는 점입니다.

탐색하면서 절반 씩 범위를 줄이기 때문에 시간 복잡도는 O(logN)입니다.

이를 적용해서 탐색하면은 문제에서 추구하는 시간 안에 계산을 맞출 수 있습니다.

 

코드

Go에서는 기본적으로 Search 함수를 통해 이진 탐색을 구현할 수 있습니다

하지만 이 문제에서는 bool이 아닌 0,1로 결과를 나타내기에 따로 binarySearch 함수를 만들었습니다.

package main

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

func binarySearch(arr []int, elem int) int {
	// 시작과 끝 인덱스를 설정
	start, end := 0, len(arr)-1
	for start <= end {
		// 중간 값을 기준으로 시작과 끝을 변경 및 탐색 반복
		mid := (end + start) / 2
		if arr[mid] > elem {
			end = mid - 1
		} else if arr[mid] < elem {
			start = mid + 1
		} else {
			//arr[mid] == elem 일 경우 return 1
			return 1
		}
	}
	return 0
}

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

	var n int
	var m int

	// 배열 길이 및 데이터 입력
	// Fscanln 은 줄 바꿈을 기준으로 입력
	// Fscan 은 공백을 기준으로 입력
	fmt.Fscanln(reader, &n)
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(reader, &arr[i])
	}
	fmt.Fscanln(reader)
	sort.Ints(arr)
	fmt.Fscanln(reader, &m)
	for i := 0; i < m; i++ {
		var elem int
		fmt.Fscan(reader, &elem)
		fmt.Println(binarySearch(arr, elem))
	}
}