글 읽기 - 시간 초과 질문

madpota 3년 전 0

3% 쯤에서 멈춰있다가

7%가고 나서 시간 초과가 뜹니다.

bfs 큐에 쓸데없는 노드를 너무 많이 넣는건가 했지만

다른 분 코드 보니 별다른 차이는 못느끼겠더군요.

출력 만드는 부분이 병목인 것 같아서

writer에 바로 쓰지 않고 string buffer에다 넣는 방식으로 바꿔도

달라지는 건 없네요

제가 놓치고 있는 부분이 어디일까요?

package main
import (
    "bufio"
    "os"
    "strconv"
    "strings"
)
var sc = bufio.NewScanner(os.Stdin)
var w = bufio.NewWriter(os.Stdout)
var sb strings.Builder

func scanInt() int {
    sc.Scan()
    n,_ := strconv.Atoi(sc.Text())
    return n
}

type Status struct {
    op byte
    oldV int
    currentV int
}

func d(x int) int {
    t := 2*x
    if t > 9999 {
        t %= 10000
    }
    return t
}

func s(x int) int {
    t := x-1
    if t < 0 {
        t = 9999
    }
    return t
}

func l(x int) int {
    a := x/1000
    b := x%1000
    return b*10 + a
}

func r(x int) int {
    a := x/10
    b := x%10
    return  b*1000 + a
}

func dslr() {
    n := scanInt()
    k := scanInt()
    q := make([]*Status, 0)
    q = append(q, &Status{currentV:n})
    trace := make(map[int]*Status)
    trace[n] = q[0]

    for {
        x := q[0]
        q = q[1:]
        if x.currentV == k {
            break
        }

        t := d(x.currentV)
        if _, ok := trace[t]; !ok {
            status := &Status{op:'D', currentV: t, oldV: x.currentV}
            trace[t] = status
            q = append(q, status)
        }
        t = s(x.currentV)
        if _, ok := trace[t]; !ok {
            status := &Status{op:'S', currentV: t, oldV: x.currentV}
            trace[t] = status
            q = append(q, status)
        }
        t = l(x.currentV)
        if _, ok := trace[t]; !ok {
            status := &Status{op:'L', currentV: t, oldV: x.currentV}
            trace[t] = status
            q = append(q, status)
        }
        t = r(x.currentV)
        if _, ok := trace[t]; !ok {
            status := &Status{op:'R', currentV: t, oldV: x.currentV}
            trace[t] = status
            q = append(q, status)
        }
    }

    reverse := make([]byte, 0)
    for i:=k;trace[i].op != byte(0);i=trace[i].oldV {
        reverse = append(reverse, trace[i].op)
    }
    for i:=len(reverse)-1;i>=0;i-- {
        sb.WriteByte(reverse[i])
    }
    sb.WriteByte('\n')
}

func main() {
    sc.Split(bufio.ScanWords)
    t := scanInt()
    for t > 0 {
        dslr()
        t--
    }
    w.WriteString(sb.String())
    w.Flush()
}

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

문제

문제

출처

ICPC

시간 초과 질문

madpota 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말