글 읽기 - 시간 초과.. 더 이상 어떻게 줄일수 있을까요..;;

motal 5년 전 0

혹시 더 최적화 할 수 있는 알고리즘을 제가 모르는걸까요? 힌트라도 부탁 드립니다.

package main
import (
	"fmt"
	"sort"
)
func main() {
	var N, H int
	fmt.Scanf("%d %d", &N, &H)
	arr1 := make([]int, N/2)
	arr2 := make([]int, N/2)
	for i := 0; i < N; i++ {
		var K int
		fmt.Scanf("%d", &K)
		if i % 2 == 0 {
			arr1[i/2] = K
		} else {
			arr2[(i-1)/2] = K
		}
	}
	sort.Slice(arr1, func(i, j int) bool {
		return arr1[i] < arr1[j]
	})
	sort.Slice(arr2, func(i, j int) bool {
		return arr2[i] < arr2[j]
	})
	var cnt int
	min := 100000000
	for h := 0; h < H; h++ {
		v := N - binarySearch(arr1, h+1) - binarySearch(arr2, H-h)
		if min > v {
			min = v
			cnt = 1
		} else if min == v {
			cnt++
		}
	}
	fmt.Println(min, cnt)
}

func binarySearch(arr []int, t int) int {
	l, r := 0, len(arr)-1
	for l <= r {
		m := l + (r-l)/2
		if arr[m] >= t {
			r = m - 1
		} else {
			l = m + 1
		}
	}
	return l
}

doju 5년 전 1

fmt.Scanf가 굉장히 느리다는 말(Stack Overflow)이 있네요. 더 빠른 입력 방법을 찾아 보시면 좋을 것 같습니다.
제가 읽은 Go 코드 중 하나에서는 bufio.NewScanner(os.Stdin)를 사용해 입력받은 뒤 byte 배열을 직접 정수로 변환하고 있었습니다.

풀이의 효율 면에서는 O(N + H) 풀이가 있지만, 질문하신 것과 같은 O((N + H) log N) 풀이도 충분히 통과할 수 있어 보입니다.

motal 5년 전 0

오 감사합니다.

bufio.NewScanner로 하니 굉장히 빠르네요~!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간 초과.. 더 이상 어떻게 줄일수 있을까요..;;

motal 5년 전 0

doju 5년 전 1

motal 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말