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

~~~ 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를 직접 구현해서 다시 제출했습니다:

~~~ go
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++로 옮겨서 구현했습니다:

~~~ c++
#include
#include
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 int n;
scanf("%d", &n);
int *m = new int[n];
int *w = new int[n];
for(int j=0; j scanf("%d", &m[j]);
}
for(int j=0; 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 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 로 다시 구현해봤습니다:

~~~ go
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++에 비해 다소 느리긴 하지만, 이 정도 차이는 충분히 납득 가능합니다.