글 읽기 - golang) 어느부분이 시간초과일까요?

kwkimg3100 2년 전 0

시간초과로 실패하는데

제 생각에는 32번라인 중복 검사하는부분이지않을까싶어요

맞나요?

package main

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

type num []int

func (o num) Len() int      { return len(o) }
func (o num) Swap(i, j int) { o[i], o[j] = o[j], o[i] }
func (o num) Less(i, j int) bool {
	return o[i] < o[j]
}

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

	var a int
	fmt.Fscan(r, &a)
	s1 := []int{}
	s2 := make([]int, a)
	for i := 0; i < a; i++ {
		var b int
		var c bool = false
		fmt.Fscan(r, &b)
		s2[i] = b
		for _, value := range s1 {
			if b == value {
				c = true
				break
			}
		}
		if !c {
			s1 = append(s1, b)
		}
	}
	sort.Stable(num(s1))
	for _, value := range s2 {
		fmt.Fprintf(w, "%d ", binarySearch(s1, value))
	}
}

func binarySearch(a []int, search int) (result int) {
	mid := len(a) / 2
	switch {
	case len(a) == 0:
		result = -1
	case a[mid] > search:
		result = binarySearch(a[:mid], search)
	case a[mid] < search:
		result = binarySearch(a[mid+1:], search)
		if result >= 0 {
			result += mid + 1
		}
	default:
		result = mid
	}
	return
}

bupjae 2년 전 1

32~37번쨰 줄과 같이 중복 검사를 하면 중복 검사하는 데만 시간복잡도 O(n) 이 되며

결국 프로그램 전체의 시간복잡도는 O(n^2) 이 됩니다.

중복 검사를 좀 더 효율적인 방법으로 해야 합니다.

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

문제

문제

출처

ICPC

golang) 어느부분이 시간초과일까요?

kwkimg3100 2년 전 0

bupjae 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말