[BOJ] 10800번 : 컬러볼(Go, Golang)

문제 링크 : 백준 10800번

[문제 접근]

n이 최대 200,000이기 때문에 최적화를 해줘야 한다. 나는 정렬을 이용해 풀었다.
인덱스, 색, 사이즈를 가지고 있는 구조체를 통해 info 슬라이스에 정보를 담았고 sumColor 슬라이스에는 각 색깔 별로 사용한 크기 정보를 갱신해주었다.

1. info 슬라이스를 사이즈 기준 오름차순으로 정렬한다.
2. 현재 사이즈와 전 사이즈를 비교해서 현재가 더 크면 전체 합을 의미하는 totalnum에 추가해주고 해당 색의 크기를 사용했으니까 sumColor에 더해준다.
3. 크기가 같아지면 전체 합에서 사용된 같은 색상 크기를 빼주면 된다.

[소스 코드]

package main

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

type node struct {
	index int
	color int
	size  int
}

var (
	r        = bufio.NewReader(os.Stdin)
	w        = bufio.NewWriter(os.Stdout)
	n        int
	totalnum int
)

func main() {
	defer w.Flush()
	fmt.Fscan(r, &n)
	info := make([]node, n)
	sumColor := make([]int, n+1)
	ans := make([]int, n)

	for i := 0; i < n; i++ {
		info[i].index = i
		fmt.Fscan(r, &info[i].color, &info[i].size)
	}
	// 공 크기가 큰 순으로 정렬
	sort.Slice(info, func(i, j int) bool {
		return info[i].size < info[j].size
	})

	j := 0
	for i := 0; i < n; i++ {
		for ; info[i].size > info[j].size; j++ { // 전꺼와 크기가 같으면 넘어감
			// 자기보다 작은 공들의 크기 합 저장
			totalnum += info[j].size
			sumColor[info[j].color] += info[j].size
		}
		// 같은 색상 제거
		ans[info[i].index] = totalnum - sumColor[info[i].color]
	}

	for _, val := range ans {
		fmt.Fprintln(w, val)
	}
}