글 읽기 - [golang] 시간초과

teihong93 3년 전 0

아무리해도 시간초과가 납니다...10%대에서

golang의 sort 가 느린걸까요(내부적으로 보면 최적화가 잘 되어있던데)

아니면 다른 시간초과가 발생하는 요인이 있을까요?

혹시나해서 랜덤피봇 QS를 직접 구현해서도 해봤는데 여전히 시간초과가 뜨네요

혹시 시간초과가 뜰만한 예시가 있을까요 ㅠㅠ..?

package main
import "fmt"
import "sort"

type doubleAry [][]int

func (da doubleAry) pop(index int) doubleAry { return append(da[0:index],da[index+1:len(da)]...) }
func (da doubleAry) Len() int           { return len(da) }
func (da doubleAry) Swap(i, j int)      { da[i], da[j] = da[j], da[i] }
func (da doubleAry) Less(i, j int) bool {
	if da[i][1] < da[j][1] {
		return true
	} else if da[i][1] == da[j][1] && da[i][0] < da[j][0] {
		return true
	}
	return false
}

func (da doubleAry) OverLay(endTime,i int) bool {return da[i][0] < endTime }

func main(){
	var N int
	_,_ = fmt.Scanf("%d",&N)
	var list = make(doubleAry,0,100001)

	for i:=0; i<N; i++ {
		var start,end int
		_,_ = fmt.Scanf("%d %d",&start,&end)
		list = append(list,[]int{start,end})
	}

	sort.Sort(list)
	count := 0
	init_end := 0

	for i := 0; i< len(list); i++ {
		if !list.OverLay(init_end,i) {
			count++
			init_end = list[i][1]
		}
	}
	fmt.Println(count)
}

bupjae 3년 전 2

fmt.Scanf 는 속도가 매우 느립니다.

bufio.Scanner 를 사용하세요.

teihong93 3년 전 0

와 정말 Scanf 문제였네요 ㅜㅜ 몇시간을 고민했는데 감사합니다!

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

문제

문제

출처

ICPC

[golang] 시간초과

teihong93 3년 전 0

bupjae 3년 전 2

teihong93 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말