본문 바로가기
학습 노트/알고리즘 (Python)

Stack #2

걔랑계란 2022. 6. 23. 02:45

서론

이전에 정리했던 Stack의 구조와 동작 방식을 이해하고,
문제를 풀며 이를 응용해 본다.

 

본론

Q1

스택에 push 되는 값들이 오름차 수열이 되는지를 판단해,
불가하면 'NO'를 가능하다면 작업의 순서를 push는 '+'로 pop은 '-'로 출력하도록 하면 된다.

Q1_Python

Stack

class Stack2():
  class Empty(Exception):
    pass
  def __init__(self):
    self.stk = []

  def is_empty(self) -> bool:
    return not self.stk

  def push(self, val):
    self.stk.append(val)

  def pop(self):
    if self.is_empty():
      raise Stack2.Empty

    return (self.stk.pop())

  def top(self):
    if self.is_empty():
      raise Stack2.Empty
    return self.stk[-1]

  def size(self):
    return len(self.stk)

  #for this ans only
  def gutout(self):
    for val in self.stk:
      print(val)

  def clean(self):
    self.stk = None

Solve

checker = 1
amount = int(input())
q3Stk = Stack2()
ans = Stack2()
exceptable = True

for _ in range(amount):
  val = int(input())
  while checker <= val:
      q3Stk.push(checker)
      ans.push('+')
      checker += 1
  if q3Stk.top() == val:
    q3Stk.pop()
    ans.push('-')
  else:
    exceptable = False


print("ans=====================")
ans.gutout()
if exceptable:
  ans.gutout()
else:
  print('NO')
결과

5
1
2
5
3
4
ans=====================
NO

Stack 클래스는 함께 공부하는 사람들의 이해를 위해 따로 선언했다.
실제로는 해당하는 메서드나 메커니즘으로 대체해도 문제없다.

  • checker 변수를 통해 이전에 입력된 값을 확인
  • 새로 입력된 val과 같아질 때까지 checker를 1씩 증가하며 스택에 push, ans에 '+' 저장
  • 스택에 마지막으로 push 된 값이 val과 같다면 스택에서 pop, ans에 '-' 저장
  • 스택에 마지막으로 push된 값이 val과 같지 않다면 exceptable을 'False'로 전환
  • excetable의 true 여부에 따라 ans 스택의 값을 index 순으로 출력, 혹은 NO를 출력

Q1_Swift

Solve

//
//  main.swift
//  Stack
//
//  Created by Martin.Q on 2022/07/13.
//

import Foundation

var stack: [Int] = []
var ans: [Character] = []
var exceptable: Bool = true
var checker = 1

guard let N = Int(readLine()!) else {
	fatalError("input must Int")
}

for _ in 1...N {
	guard let val = Int(readLine()!) else {
		fatalError("input must Int")
	}
	while checker <= val {
		stack.append(checker)
		ans.append("+")
		checker += 1
	}
	
	if stack.last == val {
		stack.removeLast()
		ans.append("-")
	} else {
		exceptable = false
	}
}

if exceptable {
	for val in ans {
		print(val)
	}
} else {
	print("NO")
}
결과

8
4
3
6
8
7
5
2
1
+
+
+
+
-
-
+
+
-
+
+
-
-
-
-
-

 

Q2

스택을 십분 활용할 수 있는 대표적인 문제다.

10진법의 2진법 변환은 위와 같다.
몫이 1이 될 때까지 2로 계속 나누고,
이렇게 나온 몫과 나머지를 위의 그림같이 배열하면 2진법이 된다.

Q2_Python

Stack

class Stack3():
  class Empty(Exception):
    pass
  def __init__(self):
    self.stk = []

  def is_empty(self) -> bool:
    return not self.stk

  def push(self, val):
    self.stk.append(val)

  def pop(self):
    if self.is_empty():
      raise Stack3.Empty

    return (self.stk.pop())

  def top(self):
    if self.is_empty():
      raise Stack3.Empty
    return self.stk[-1]

  def size(self):
    return len(self.stk)

  def unExcept(self):
    for x in self.stk:
      if x == 'NO':
        return False
      else:
        print(x)
    return True

  def gutout(self):
    ans = ''
    for _ in range(self.size()):
      ans += str(self.pop())
    return ans

  def clean(self):
    self.stk = []

Solve

ans = Stack3()
target = int(input())

while target >= 1:
  ans.push(int(target % 2))
  target /= 2

ans.gutout()
결과

108
'1101100'

몫이 1이 될 때 까지 나눠 나머지를 Stack에 저장하고,
Stack이 빌 때 까지 pop을 진행한다.

Q2_Swift

Solve

//
//  main.swift
//  Stack
//
//  Created by Martin.Q on 2022/07/13.
//

import Foundation

var stack: [Int] = []

guard var target = Int(readLine()!) else {
	fatalError("Input must Int")
}

while target >= 1 {
	stack.append(target % 2)
	target /= 2
}

stack.reverse()
for val in stack {
	print(val, terminator: "")
}
print("")
결과

108
1101100
Program ended with exit code: 0

 

Q3

입력과 출력을 확인해 보면 항상 좌우가 쌍을 이뤄야 TRUE로 판단한다.
따라서 이에 대한 조건을 Stack의 특성에 접목시키면 이를 쉽게 해결할 수 있다.

Q3_Python

ans = Stack3()
input_val = ['((()))', '((()', '(()()())', '()', '(()())))']
define = True

for target in input_val:
  target = list(target)
  for val in target:
    if val == '(':
      ans.push(val)
    elif val == ')':
      try:
        ans.pop()
      except:
        define = False

  if ans.is_empty() and define == True:
    print('TRUE')
  else:
    print('FALSE')

  ans.clean()
결과

TRUE
FALSE
TRUE
TRUE
FALSE

사용한 Stack3 클래스는 이전에 사용한 클래스와 동일하다.

간단히 순차적으로 탐색을 진행하고,
'('일 때 push를, ')'일 때 pop을 진행해 쌍을 이루는지 판단한다.
또한, 빈 Stack에서 ')'로 인해 pop을 진행하는 경우, 탐색이 끝난 뒤 Stack이 비지 않은 경우
불완전한 것으로 판단해 FALSE를 출력한다.

Q3_Swift

Solve

//
//  main.swift
//  Stack
//
//  Created by Martin.Q on 2022/07/13.
//

import Foundation

let inputValue = ["((()))", "((()", "(()()())", "()", "(()())))"]

for val in inputValue {
	var stack: [Character] = []
	var define = true
	
	val.forEach { (char) in
		switch char {
		case "(":
			stack.append(char)
		case ")":
			let target = stack.popLast()
			
			if target == nil {
				define = false
			}
		default:
			break
		}
	}
	
	if (stack.count <= 0) && define == true {
		print("TRUE")
	} else {
		print("FALSE")
	}
}
결과

TRUE
FALSE
TRUE
TRUE
FALSE

 

Q4

Stack에 저장된 값 중 최솟값을 찾아내는 복잡도가 log(0)를 만족하도록 구현하는 문제다.

Q4_Python

Stack

class Min(object):
  def __init__(self, val = None, min = None):
    self.val = val
    self.min = min

class Stack4():
  class Empty(Exception):
    pass
  def __init__(self):
    self.stk = []
    self.min = None

  def is_empty(self) -> bool:
    return not self.stk

  def push(self, val):
    if self.is_empty() or val <= self.min:
      self.min = val
    self.stk.append(Min(val, self.min))

  def pop(self):
    if self.is_empty():
      print('Empty')
    else:
      target = self.stk.pop()
      if target.val == self.min:
        self.min = self.stk[-1].min
        return target.val

  def top(self):
    if self.is_empty():
      raise Stack4.Empty
    return self.stk[-1]

  def top_min(self):
    return self.stk[-1].min

  def size(self):
    return len(self.stk)

  def gutout(self):
    ans = ''
    for _ in range(self.size()):
      ans += str(self.pop())
    return ans

  def clean(self):
    self.stk = []

Solve

ans = Stack4()
amount = int(input())

for _ in range(amount):
  val = input('push : 1, pop : 2\n')
  if val == '1':
    push_val = int(input('push\n'))
    ans.push(push_val)
  if val == '2':
    ans.pop()
결과

4
push : 1, pop : 2
1
push
4
push : 1, pop : 2
1
push
3
push : 1, pop : 2
1
push
6
push : 1, pop : 2
1
push
5

Validation

print('peek val is {} min val is {}'.format(ans.top().val,ans.top().min))
ans.pop()
print('peek val is {} min val is {}'.format(ans.top().val,ans.top().min))
결과

peek val is 5 min val is 3
peek val is 6 min val is 3

이전 문제들에서 Stack에 정수나 문자 등 간단한 자료형을 저장했던 것과 다르게
클래스를 사용한 인스턴스를 저장했다는 점이 특별하다.

Stack에 push, pop 될 때마다 Stack의 최솟값을 min에 저장하며,
이를 위해 Stack에 저장되는 인스턴스에도 해당 데이터가 저장되는 시점의 최솟값이 함께 저장된다.
Stack의 현재 최솟값을 위해서 Stack을 순회할 필요 없이 min값만 호출하기 때문에 조건도 만족한다.

 

Q5

괄호와 연산자들의 우선순위에 주의해야 하는 문제다.

 3 + 4

중위 표기법은 일반적으로 생각하는 수식의 형태로 연산자가 피연산자 사이에 오는 방식이다.

+34

전위 표기법은 연산자가 피연산자의 앞에 오는 방식이다.

34+

후회 표기법은 연산자가 피연산자의 뒤에 오는 방식이다.

후위 표기법을 실제로 다룰 경우는 그리 많지 않지만,
컴퓨터 내부적으로는 후위 표기법으로 수식을 이해하고, 연산을 수행한다.

Q5_Python

stk = []
ans = ''
input_val = ['3 + 4','(9 - ( 4 / 2 + 1)) * ( 5 * 2 - 2)']
dic = {'+' : 0,
       '-' : 0,
       '*' : 1,
       '/' : 1 }
for target in input_val:
  target = list(target.replace(' ', ''))
  for val in target:
    if val.isdecimal():
        ans+= val
    elif val=='(':
        stk.append(val)
    elif val==')':
      while stk and stk[-1]!= '(':
        ans += stk.pop()
      stk.pop()
    else: 
      while stk and stk[-1]!='(' and dic[val]<=dic[stk[-1]]:
        ans+=stk.pop()
      stk.append(val)

  while stk:
    ans += stk.pop()
  print(ans)
  ans = ''
결과

34+
942/1+-52*2-*

해당 문제는 Rabbit과 Whale과 함께 진행했다.
처음엔 조건문의 중첩으로 연산자, 괄호의 우선순위를 표현했지만,
구현중 복잡도가 올라감에 따라 dictionary로 우선순위를 미리 지정하는 방식으로 구현했다.

메커니즘은 간단하다.

  • 피연산자는 바로 문자열에 추가한다.
  • '('는 스택에 push 한다.
  • ')'는 '('가 나올 때까지 스택에서 pop 해 문자열에 추가한다.
  • 연산자는 스택에서 자신보다 우선순위가 낮은 연산자가 나올 때 까지 pop해 문자열에 추가하고,
    '('를 만나거나 우선순위가 낮은 연산자를 만나면 스택에 push 한다.
  • 스택에 남은 연산자들을 모두 pop 해 문자열에 추가한다.

조건문의 중첩이 아닌 dictionary로 연산자들의 우선순위를 구분하기 때문에,
'^'등의 기타 연산자가 추가돼도 유지보수가 용이하다는 장점이 있다.

Log

2022.07.14.
각 문제에 대한 Swift 코드 추가

저작자표시 비영리 변경금지

'학습 노트 > 알고리즘 (Python)' 카테고리의 다른 글

99클럽 - 기능개발, 대충 만든 자판  (0) 2024.04.12
99클럽 - 이진 변환 반복하기  (0) 2024.04.11
Stack #1  (0) 2022.06.04
선형 데이터 구조와 탐색  (0) 2022.05.03
Q1. 방 배정 하기  (0) 2022.04.22

'학습 노트/알고리즘 (Python)' Related Articles

티스토리툴바