글 읽기 - golang 시간초과...

kwak2418 2년 전 1

c++ python 모두 같은 구조로 통과했습니다..

왜 안될 까요

package main

import (
	"fmt"
)

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	const LMIT = 100001
	const MAX = 1000000000
	var dis [LMIT]int
	var grd [LMIT]int
	mincost := MAX
	N := 0
	result := 0
	mindex := 0
	L := 0
	fmt.Scan(&N)
	for i := 1; i < N; i++ { //거리 입력 받기
		fmt.Scan(&dis[i])
		L += dis[i]
	}
	for i := 1; i < N; i++ { //cost 입력 받기
		fmt.Scan(&grd[i])
		if grd[i] < mincost { //가장 적은 비용및 해당 도시 인덱스 얻음
			mincost = grd[i]
			mindex = i
		}
	}
	if mindex == 1 { //만약 해당 인덱스가 1이면 출발지점에서 모두 넣으면됨
		result = grd[1] * L
	} else { //아닐 경우
		mincost = grd[1]
		result += mincost * dis[1]
		L -= dis[1]
        // 출발지에서 다음 도시로 건넌 후 
		for i := 2; i < mindex; i++ { // 최소 도시까지 반복문 돌림 
			if mincost < grd[i] { //만약 과거의 비용이 더 싸면 과거 비용으로 결제
				result += mincost * dis[i]
				L -= dis[i]
			} else { //아니면 비용 업데이트 후 결제
				mincost = grd[i]
				result += mincost * dis[i]
				L -= dis[i]
			}
		} 
		result += grd[mindex] * L //마지막으로 최소 도시에서 나머지 거리 결제 
	}
	fmt.Print(result) //출력 

}

bupjae 2년 전 1

golang 의 fmt.Scan 은 속도가 너무 느립니다. os.Stdin 을 bufio.Reader 또는 bufio.Scanner 로 감싸서 사용하세요.

kwak2418 2년 전 0

fmt.Fscan(reader,&변수) 쓰라는 말씀이신가요 ..? 지금 까지 bufio는 NewReader 인스턴스 만든후 Fscan에 넣어 사용했거든요.. 다르게 사용할 방법이 있나요?

kwak2418 2년 전 0

이런 식으로 변경해 봤는데 시간초과가 아닌 틀렸습니다 나옵니다.. 예제는 정확히 잘 나왔는데요.. 출력 또 writer 써서 flush 해주는게 나을 까요 ??

golang은 입출력이 조금 속도 올리려면 어려운 것 같습니다.. 시간초과 해결할려고 빠른 입출력 쓰면 틀렸습니다가 많이 나오더라구요.. 왜그런걸 까요?

package main

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

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	const LMIT = 100001
	const MAX = 1000000000
	var dis [LMIT]int
	var grd [LMIT]int
	reader := bufio.NewReader(os.Stderr)
	mincost := MAX
	N := 0
	result := 0
	mindex := 0
	L := 0
	fmt.Fscan(reader, &N)
	for i := 1; i < N; i++ { //거리 입력 받기
		fmt.Fscan(reader, &dis[i])
		L += dis[i]
	}
	for i := 1; i < N; i++ { //cost 입력 받기
		fmt.Fscan(reader, &grd[i])
		if grd[i] < mincost { //가장 적은 비용및 해당 도시 인덱스 얻음
			mincost = grd[i]
			mindex = i
		}
	}
	if mindex == 1 { //만약 해당 인덱스가 1이면 출발지점에서 모두 넣으면됨
		result = grd[1] * L
	} else { //아닐 경우
		mincost = grd[1]
		result += mincost * dis[1]
		L -= dis[1]
		// 출발지에서 다음 도시로 건넌 후
		for i := 2; i < mindex; i++ { // 최소 도시까지 반복문 돌림
			if mincost < grd[i] { //만약 과거의 비용이 더 싸면 과거 비용으로 결제
				result += mincost * dis[i]
				L -= dis[i]
			} else { //아니면 비용 업데이트 후 결제
				mincost = grd[i]
				result += mincost * dis[i]
				L -= dis[i]
			}
		}
		result += grd[mindex] * L //마지막으로 최소 도시에서 나머지 거리 결제
	}
	fmt.Print(result) //출력

}

kwak2418 2년 전 0

어 그렇네요.. 정답 나왔습니다... Fscan 이렇게 쓰면 될까요? 빠른입력을 위한?

bamgoesn 2년 전 3

지금 사용하신 것처럼 Fscan 사용하시면 어지간하면 문제 없습니다. 어차피 백준에선 Go에 추가 시간으로 2초를 더 주기 때문에, 알고리즘만 적절히 짰다면 시간 초과는 거의 나지 않습니다.

하지만 괜히 실행 시간을 단축시키고 싶다거나, Fscan이 불편하다면 text, _ := reader.ReadString('\n') ; text = strings.TrimSpace(text) 와 같이 한 줄을 읽어들이거나, scanner.Split(bufio.ScanWords) ; scanner.Scan() ; text := scanner.Text() 와 같이 토큰을 하나 가져와서 a, _ := strconv.Atoi(text) 와 같이 직접 파싱하면 충분히 빠릅니다.

개인적으로 전자는 한 줄에 배열의 정보가 전부 들어올 때 strings.Fields()를 같이 활용해서 입력받을 때 편하고, 후자는 데이터를 한 단어 한 단어 가져올 때 편합니다. 다만 당연히 둘 다 같이 쓸 수는 없으니 혼용이 필요할 땐 적절히 타협을 봐야 합니다.

-------

한편 출력양도 많은 문제의 경우는 os.Stdout을 bufio.Writer로 감싸서 하는 것이 좋습니다. 경험상 이 때엔 fmt.Fprintln도 충분히 빠릅니다만, 부족하다 싶으면 writer.WriteString 등을 사용하면 됩니다.

또한 bufio.Writer를 사용할 경우엔 defer writer.Flush() 와 같이 defer를 사용해 flush를 해주면 코드가 깔끔해집니다.

-------

아래 코드는 문제를 풀 때 제가 개인적으로 사용하는 코드 스니펫입니다.

다른 분들 제출을 보면 더 빠른 IO 구현도 있는 것 같은데 경험상 이정도면 충분히 빠르고, 무엇보다 코드가 짧아서 코딩할 때 편합니다.

한편 bufio를 사용하면 인풋을 파일로 받기 쉽다는 점도 매우 편리합니다. 아래 그림의 22~25행이 이를 위한 것입니다.

물론 제출할 땐 25행의 주석을 코드로 바꾸고 22, 23행은 지워야 합니다.

package main

import (
	"bufio"
	"os"
	"strconv"
)

//------
// Main
//------

func main() {
	sc.Split(bufio.ScanWords)
	defer wr.Flush()
        
    // Main code comes here!
}

//---------
// Fast IO
//---------

var fp, _ = os.Open("input.txt")
var sc = bufio.NewScanner(fp)

// var sc = bufio.NewScanner(os.Stdin)
var wr = bufio.NewWriter(os.Stdout)

func nextInt() (res int) {
	sc.Scan()
	text := sc.Text()
	v, _ := strconv.Atoi(text)
	return v
}

func nextInt64() (res int64) {
	sc.Scan()
	text := sc.Text()
	v, _ := strconv.ParseInt(text, 10, 64)
	return v
}

kwak2418 2년 전 1

알아듣기 쉬운 설명과 친절한 예제까지 ... go린이 오늘도 감동합니다 정말 감사합니다..

알고리즘을 3언어로 풀고있는데 항상 입력 방식이 다양할 때마다 golang으로 할때 머리가 조금씩 복작해지더라구요 ㅋㅋ 정말 감사드립니다 (- - (_ _ (- -

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

문제

문제

출처

ICPC

golang 시간초과...

kwak2418 2년 전 1

bupjae 2년 전 1

kwak2418 2년 전 0

kwak2418 2년 전 0

bupjae 2년 전 1

kwak2418 2년 전 0

bamgoesn 2년 전 3

kwak2418 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말