AtCoder ABC064 D - Insertion

AtCoderに取り組んだ際のメモです。
問題ページはこちらです。

Point: 400
Difficulty: 944

考えたこと

・"("が続く限りは、特に挿入操作は必要なし
・"("が連続した回数を保持してておく
・")"が来た場合は、")"が連続する回数を数える
・直前の連続する"("に対応する")"については、対応が必要なし
　->"("が不足する")"については、文字列の先頭に"("を挿入する

・上記の作業をSの末尾まで繰り返す
・"("が開いたままで残っていれば、末尾に")"を必要分挿入する

提出したコード

提出ページ

package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
)

func main() {
	r := bufio.NewReader(os.Stdin)
	var n int
	var s string
	fmt.Fscan(r, &n)
	fmt.Fscan(r, &s)

	var ans []string
	opCount := 0
	clCount := 0
	i := 0
	for i < n {
		if s[i] == '(' {
			ans = append(ans, "(")
			opCount++
			i++

		} else {
			// )が続く回数を調べる
			clCount++
			i++
			for j := i; j < n; j++ {
				if s[j] != ')' {
					break
				}
				clCount++
				i++
			}

			tmpOpCount := max(0, clCount-opCount)
			for tmpOpCount > 0 {
				ans = append([]string{"("}, ans...)
				tmpOpCount--
			}
			opCount = max(0, opCount-clCount)

			for clCount > 0 {
				ans = append(ans, ")")
				clCount--
			}
		}
	}

	for opCount > 0 {
		ans = append(ans, ")")
		opCount--
	}

	fmt.Println(strings.Join(ans, ""))
}

// Utility
func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

感想など

・当初、スタックを使って個別に "(" と ")" の対応付けをする必要があると考えて、遠回りしてしまった
・よく考えると、"(" の挿入位置は常に文字列の先頭になる
　-> ")" の直前に対応する "(" が存在しない場合は、先頭に挿入すればいいため、")" の連続回数は把握する必要がなかった（再提出コード）

・実装に30分近くかかってしまっていて、本番だと厳しそうな印象