[MEETING] [golang] 시간초과 오류

  • bupjae
    bupjae

    MEETING 문제를 풀기 위해 다음과 같은 go 코드를 작성하였습니다:

    package main

import "fmt"
import "sort"

func main() {
    var t int
    fmt.Scan(&t)
    for i := 0; i < t; i++ {
        var n int
        fmt.Scan(&n)
        m := make([]int, n)
        w := make([]int, n)
        for j := 0; j < n; j++ {
            fmt.Scan(&m[j])
        }
        for j := 0; j < n; j++ {
            fmt.Scan(&w[j])
        }
        sort.Ints(m)
        sort.Ints(w)
        r := 0
        for j := 0; j < n; j++ {
            rr := m[j] - w[j]
            if rr < 0 {
                rr *= -1
            }
            r += rr
        }
        fmt.Println(r)
    }
}

    제출을 했더니 "시간초과" 오류를 받았습니다.

    라이브러리에서 제공된 sort 알고리즘에 문제가 있나 라고 생각해서 sort를 직접 구현해서 다시 제출했습니다:

    package main

import "fmt"

func sort(a []int) []int {
    if len(a) < 2 {
        return a
    }
    r := make([]int, 0, len(a))
    b := sort(a[:len(a)/2])
    c := sort(a[len(a)/2:])
    for len(b) > 0 && len(c) > 0 {
        if b[0] < c[0] {
            r = append(r, b[0])
            b = b[1:]
        } else {
            r = append(r, c[0])
            c = c[1:]
        }
    }
    r = append(r, b...)
    return append(r, c...)
}

func main() {
    var t int
    fmt.Scan(&t)
    for i := 0; i < t; i++ {
        var n int
        fmt.Scan(&n)
        m := make([]int, n)
        w := make([]int, n)
        for j := 0; j < n; j++ {
            fmt.Scan(&m[j])
        }
        for j := 0; j < n; j++ {
            fmt.Scan(&w[j])
        }
        sort(m)
        sort(w)
        r := 0
        for j := 0; j < n; j++ {
            rr := m[j] - w[j]
            if rr < 0 {
                rr *= -1
            }
            r += rr
        }
        fmt.Println(r)
    }
}

    하지만 이 프로그램도 시간초과에 걸렸습니다.

    이 결과를 도저히 받아들일 수 없어서, 이 프로그램을 그대로 C++로 옮겨서 구현했습니다:

    #include <cstdio>
#include <cstdlib>
using namespace std;

int intcomp(const void *v1, const void *v2) {
    return *((const int*)v1) - *((const int*)v2);
}

int main() {
    int t;
    scanf("%d", &t);
    for(int i=0; i<t; i++) {
        int n;
        scanf("%d", &n);
        int *m = new int[n];
        int *w = new int[n];
        for(int j=0; j<n; j++) {
            scanf("%d", &m[j]);
        }
        for(int j=0; j<n; j++) {
            scanf("%d", &w[j]);
        }
        qsort(m, n, sizeof(int), intcomp);
        qsort(w, n, sizeof(int), intcomp);
        int r = 0;
        for(int j=0; j<n; j++) {
            int rr=m[j]-w[j];
            if(rr<0) rr*=-1;
            r+=rr;
        }
        printf("%d\n", r);
        delete[] m;
        delete[] w;
    }
}

    75ms만에 정답을 받았습니다.

    go 언어를 배우면서 이 사이트에 올려진 문제를 풀려고 하고 있습니다만, 이 정도 문제에서조차 시간초과 오류를 받아버리면 아무래도 go 언어로 문제를 푸는 것 자체가 어렵지 않을까 생각되어 문제제기를 해 봅니다.

    *** 수정: 입력 방식에 따른 속도 차이를 고려, 좀 더 빠른 방식인 bufio.Scanner 로 다시 구현해봤습니다:

    package main

import "bufio"
import "fmt"
import "os"
import "sort"
import "strconv"

type MyScanner struct {
    in *bufio.Scanner
}

var in = MyScanner{bufio.NewScanner(os.Stdin)}

func ScanInts(data []byte, atEOF bool) (advance int, token []byte, err error) {
    advance, token, err = bufio.ScanWords(data, atEOF)
    if err == nil && token != nil {
        _, err = strconv.Atoi(string(token))
    }
    return
}

func (m *MyScanner) innerNext(f bufio.SplitFunc) bool {
    m.in.Split(f)
    return m.in.Scan()
}

func (m *MyScanner) NextInt() (int, error) {
    if !m.innerNext(ScanInts) {
        return 0, m.in.Err()
    }
    r, _ := strconv.Atoi(m.in.Text())
    return r, nil
}

func main() {
    t, _ := in.NextInt()
    for i := 1; i <= t; i++ {
        main2(i)
    }
}

func main2(caseCount int) {
    n, _ := in.NextInt()
    m := make([]int, n)
    w := make([]int, n)
    for j := 0; j < n; j++ {
        m[j], _ = in.NextInt()
    }
    for j := 0; j < n; j++ {
        w[j], _ = in.NextInt()
    }
    sort.Ints(m)
    sort.Ints(w)
    r := 0
    for j := 0; j < n; j++ {
        rr := m[j] - w[j]
        if rr < 0 {
            rr *= -1
        }
        r += rr
    }
    fmt.Println(r)
}

    208ms 만에 정답을 받았습니다.
    물론 C++에 비해 다소 느리긴 하지만, 이 정도 차이는 충분히 납득 가능합니다.


    10년 전
7개의 댓글이 있습니다.
  • Being
    Being

    게시판을 검색해 보시면 Go 뿐만이 아니라 다른 언어에서도 마찬가지의 문제가 발생하고 있습니다. 그러나 언어별로 다른 시간 제한을 적용할 계획은 현재로는 없습니다. 단순히 특정 언어엔 몇 배의 시간을 더 주는 식으로 해결할 수 있는 문제가 아니라고 보고 있습니다. 반대로 공평하게 모든 언어에 같은 시간을 적용하게 되면 C++로 시간복잡도가 느리게 작성된 알고리즘이 다른 언어로 최대한 빠르게 작성한 답안보다 빠른 경우가 빈번해서 문제가 됩니다. 다른 좋은 의견 있으시면 참고하겠습니다.


    10년 전 link
  • bupjae
    bupjae

    startup 또는 input/output 등에서 발생할 수 있는 시간 차이의 여지를 완전히 사전 차단하는 TopCoder 방식의 채점 시스템을 도입하면 문제가 해결될 거라는 (헛된) 기대를 합니다만, 이 곳에 적용하기에는 사실상 불가능할 것 같기에 그냥 잡설로만 남깁니다.

    go 로 짠 코드를 c++ 로 옮기는 거야 쉽게 할 수 있습니다만, 가슴 아픈 건 제 프로필에 억울하게 남는 실패 횟수/역사...... :(


    10년 전 link
  • Being
    Being

    입출력이 많은 경우 가장 큰 이슈죠.. 아무래도 다른 언어로 푸는 분들이 많지는 않다보니 문제별로 검토하기엔 샘플을 모으기도 어려운 부분이 있습니다.


    10년 전 link
  • bupjae
    bupjae

    COINS도 go로 풀었을 때 시간초과가 났길래 더 좋은 알고리즘 찾다가 안되서 포기하고 있었는데
    이번 사태를 계기로 기존에 작성한 go 프로그램을 그대로 c++로 옮겨서 넣었더니 아니나 다를까 정답 뜨네요.

    오답 기록이 아프긴 하지만, 남들보다 2배로 배워간다고 생각하겠습니다 :)


    10년 전 link
  • 일루
    일루

    입출력과 실제 실행 중 어느쪽이 bottleneck인지 알면 좋을 것 같습니다. 확인해보고 알려드릴께요.


    10년 전 link
  • heekyu
    heekyu

    시간재는 코드가 어떤 식으로 구현되어 있는지 모르겠는데요,
    만약 프로그램 실행부터 끝날 때까지 시간을 재는 방식이라면
    입출력, 실제 실행 이외에도 요소들에 의해 수행시간에서 패널티가 존재할 것 같습니다.
    저는 주로 java로 짜는데요
    java는 실행할 때 JVM system library들도 뜨고 bytecode 컴파일도 런타임에 이루어집니다.
    입출력도 미미하고 실제로 하는 일도 별로 없는 코드를 돌려도 기본적으로 100ms~200ms는 먹고 들어갑니다.

    https://algospot.com/judge/submission/detail/212001
    이건 루프 8번 돌고 끝나는데 시간초과(1000ms)가 납니다.

    다른 언어들은 상황을 자세히 모르지만 비슷한 문제들을 가지고 있지 않을까 예상해 봅니다.

    물론 이건 실제 채점 모듈이 어떻게 되어 있는지 모르는 상태에서 한 추측이므로 사실과 다를 수 있습니다만,
    확인해 본다고 하셨으니 이런 부분도 같이 고려해 보시면 좋을 것 같습니다.


    10년 전 link
  • wookayin
    wookayin

    개인적으로는, 언어별로 제한시간 버퍼를 좀 두는게 좋을거 같다는 의견에는 동의하는 편입니다.


    10년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.