[Go] 1874번 스택 수열

굉장히 오랜만에 알고리즘 문제를 풀어본다.

 

책너두에 이어서 무지성 알고리즘 챌린지다.. 이건 꾸준히 할 수 있을진 모르겠지만 도전해본다..

 

이번에 오픈 소스 컨트리뷰션에 참여하게 되면서 golang 연습이 필요해서 golang 으로 알고리즘을 풀어본다..

 

문법에서 막혀서 쉽지 않지만.............

 

---

문제 링크

https://www.acmicpc.net/problem/1874

정답 코드

package main

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

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	n, _ := strconv.Atoi(scanner.Text())

	stack := &Stack{}
	s := make([]string, 0)
	next := 1

	for i := 0; i < n; i++ {
		scanner.Scan()
		inputNum, _ := strconv.Atoi(scanner.Text())

		for inputNum >= next {
			stack.Push(next)
			next++
			s = append(s, "+")
		}

		if stack.Top() == inputNum {
			stack.Pop()
			s = append(s, "-")
		} else if stack.Top() > inputNum {
			fmt.Println("NO")
			return
		}
	}

	if !stack.IsEmpty() {
		fmt.Println("NO")
		return
	}

	fmt.Println(strings.Join(s, "\n"))
}

// slice stack
type Stack struct {
	items []int
}

func (s *Stack) Push(v int) {
	s.items = append(s.items, v)
}

func (s *Stack) Pop() int {
	l := len(s.items)
	item := s.items[l-1]
	s.items = s.items[:l-1]
	return item
}

func (s *Stack) Top() int {
	l := len(s.items)
	if l == 0 {
		return -1
	}
	return s.items[l-1]
}

func (s *Stack) IsEmpty() bool {
	return len(s.items) == 0
}

📕 참고

1. 'bufio' 사용하는 이유

• fmt.Scan -> 버퍼를 사용하지 않고 직접 입출력 수행 -> os 수준에서 상당히 많은 오버헤드 발생 -> bufio 를 사용하면 버퍼링을 통해 표준 입출력 호출 횟수를 줄이고 성능 향상

2. bufio 사용법

• bufio.NewScanner(os.Stdin) -> os.Stdin 표준 입력 스트림을 읽을 스캐너를 생성 
• scanner.Scan() -> 입력 스트림의 토큰을 읽음 (줄단위)
• strconv.Atoi(scanner.Text()) -> 스캐너가 가장 최근에 읽은 토큰을 문자열 형태로 반환 후 정수로 변환
  • 에러 반환 값은 _ 로 무시