[Go] 2346 풍선 터뜨리기

---

Description

---

Code

package main

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

type Deque struct {
	head *DequeNode
	tail *DequeNode
	size int
}

type DequeNode struct {
	data int 
	next *DequeNode
	prev *DequeNode
}

var (
	deq *Deque = new(Deque)
)

func push_front(x int) {
	newNode := new(DequeNode)
	newNode.data = x
	if deq.size == 0 {
		deq.head = newNode
		deq.tail = newNode
	} else {
		newNode.next = deq.head
		deq.head.prev = newNode
		deq.head = newNode
	}
	deq.size++
}

func push_back(x int) {
	newNode := new(DequeNode)
	newNode.data = x
	if deq.size == 0 {
		deq.head = newNode
		deq.tail = newNode
	} else {
		newNode.prev = deq.tail
		deq.tail.next = newNode
		deq.tail = newNode
	}
	deq.size++
}

func pop_front() int {
	if deq.size == 0 {
		return -1
	}
	ret := deq.head.data
	deq.head = deq.head.next
	deq.size--
	return ret
}

func pop_back() int {
	if deq.size == 0 {
		return -1
	}
	ret := deq.tail.data
	deq.tail = deq.tail.prev
	deq.size--
	return ret
}

// 5: 덱에 들어있는 정수 개수 출력
func size() int {
	return deq.size
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	wr := bufio.NewWriter(os.Stdout)

	defer wr.Flush() 

	var N int
	if sc.Scan() {
		N, _ = strconv.Atoi(sc.Text())
		for i := 1; i <= N; i++ {
			push_back(i)
		}
	}


	var stack []int
	if sc.Scan() {
		tmp := strings.Fields(sc.Text())
		for i := 0; i < len(tmp); i++ {
			x, _ := strconv.Atoi(tmp[i])
			stack = append(stack, x)
		}
	}

	for i := 0; i < N; i++ {
		repeat := pop_front()
		wr.WriteString(strconv.Itoa(repeat) + " ")

		// 양수
		if stack[repeat - 1] > 0 {
			for j := 1; j < stack[repeat - 1]; j++ {
				push_back(pop_front())
			}
		// 음수
		} else if stack[repeat - 1] < 0 {
			for j := 1; j <= -stack[repeat - 1]; j++ {
				push_front(pop_back())
			}
		}

	}
	return
}

/*
# 문자열 공백 포함 입력 받기
if sc.Scan() {
	tmp := sc.Text()
	wr.WriteString(tmp)
}
*/

push_front, push_back, pop_front, pop_back와 같은 연산을 사용해 O(1)의 시간복잡도로 삽입과 삭제를 수행

1. 덱 초기화 및 입력
   • 1부터 N까지의 숫자를 덱에 순서대로 삽입합니다. 이 덱은 번호의 현재 순서를 유지하며, 순차적으로 이동과 삭제를 수행하는 역할을 합니다.
   • 별도의 스택 배열에는 각 번호의 이동 규칙(양수/음수 값)을 저장합니다.
2. 출력 순서 결정
   • 덱에서 가장 앞에 있는 번호를 꺼내 출력하고, 해당 번호의 이동 규칙을 스택에서 가져옵니다.
   • 규칙에 따라 덱을 회전시키는데:
     • 양수일 경우, 번호를 앞에서 꺼내 뒤로 보냅니다.
     • 음수일 경우, 번호를 뒤에서 꺼내 앞으로 보냅니다.
3. 반복 처리
   • 덱이 비워질 때까지 위 과정을 반복하며, 각 번호를 순서대로 출력합니다.