스택 - 자신보다 큰 원소 찾기

카테고리 Python, DataStructure, Stack

문제

참조: https://www.geeksforgeeks.org/next-greater-element/

음이 아닌 정수 배열이 주어졌을 때, 각 원소의 오른쪽에 있는 원소 중에서 현재 원소보다 큰 값을 출력하되, 가장 근접한 원소를 출력하라. 현재 원소보다 큰 값이 없으면 -1을 출력하라.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
예시 1

입력: [4, 5, 2, 25]
출력:
4 --> 5
5 --> 25
2 --> 25
25 --> -1
예시 2

입력: [13, 7, 6, 12]
출력:
13 --> -1
7 --> 12
6 --> 12
12 --> -1

풀이

이중반복문

1
2
3
4
5
6
7
8
9
def solution(int_arr):
    for i in range(len(int_arr)):
        int = int_arr[i]
        result = -1
        for j in range(i,len(int_arr)):
            if int < int_arr[j]:
                result = int_arr[j]
                break
        print(f"{int} --> {result}")

스택

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def solution*by_stack(int_arr):
    n = len(int_arr)
    s = []
    res = [-1 for * in range(len(int_arr))]

    for i in range(n-1,-1,-1):
        while s:
            if s[-1] > int_arr[i]:
                res[i] = s[-1]
                break
            else:
                s.pop()
        s.append(int_arr[i])

    for i in range(n):
        print(f"{int_arr[i]} --> {res[i]}")
  • 현재 원소와 오른쪽 원소를 비교하므로, 오른쪽에서 왼쪽으로 이동하면서 비교하면 수월하다.
  • 문제에서 요구하는 것은 현재 원소의 오른쪽 값 중 가장 가까운 값이므로, 오른쪽 부터 왼쪽으로 가면서 원소를 저장했다면 꺼낼 때는 역순으로 꺼내서 비교한다.
  1. stack을 빈 상태로 초기화
  2. res 배열을 -1로 배열 길이 만큼 초기화
  3. 역순으로 순회를 하면서 stack이 비어있으면, 원소를 추가한다.
  4. 만약 stack에 값이 있다면, 스택의 값들과 현재 원소를 비교한다.
  5. 스택의 값이 크다면 해당 원소의 index에 위치하는 res 배열에 스택의 값을 할당하고 해당 원소를 stack 저장
  6. 다음 순회
  7. 만약 스택의 값이 작다면 stack에 마지막 값을 pop한다.

댓글 공유

스택 - 후위 표기법2

카테고리 Python, DataStructure, Stack

후위 표기법 2

소괄호를 포함한 후위 표기법 바꾸기

소괄호()는 *보다 우선순위가 높다.

후위 표기법은 우선순위가 높은 것을 먼저 출력하므로, 열린 소괄호가 나오면 스택에 넣는다.

이후 닫힌 소괄호가 나오면 스택에 열린 소괄호 나올 때 까지 pop하여 연산자를 결과값에 추가한다.

  • 괄호는 변수에 추가하면 안되므로 스택에서 pop하여 제거한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def solution(str):
    priority = {'+':2,'-':2,'*':1,'/':1}
    result = ''
    s = []

    for x in str:
        if x.isnumeric():
            result += x
        elif x == '(':
            s.append(x)
        elif x == ')':
            while s[-1] != "(":
                result += s.pop()
            s.pop()
        elif x in priority:
            if s and s[-1] != '(' and priority[s[-1]] < priority[x]:
                result += s.pop()
            s.append(x)

    while s:
        result += s.pop()

    return result
  • 코딩테스트를 본다고 생각하고 리스트를 활용하여 위 문제를 풀어보았다.
  • isnumeric() 함수는 문자열이 숫자인지 판단하는 메서드이다.
  • stack의 top을 의미하는 s[-1] 슬라이싱을 활용하였다.
  • 빈 리스트는 논리값이 False라는 점을 활용하여 while 반복문을 실행했다.

후위 표기법 계산하기

  1. 문자열을 순회하면서 해당 문자가 숫자면 정수형으로 변환하여 스택에 push
  2. 연산자이면 스택에서 두 수를 pop하여 계산
  3. 스택은 후입선출이므로, 처음 pop한 수를 n2, 두번째 pop한 수를 n1으로 두고 (n1 연산자 n2)로 계산한다.
  4. 계산결과를 스택에 push
  5. 스택에 마지막에 저장된 값이 결과값이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def eval_postfix(expression):
    s = []
    for exp in expression:
        if exp.isnumeric():
            s.append(int(exp))
        elif exp != " ":
            n2 = s.pop()
            n1 = s.pop()
            if exp == '+':
                res = n1 + n2
            elif exp == '-':
                res = n1 - n2
            elif exp == '*':
                res = n1 * n2
            else:
                res = n1 / n2
            s.append(res)
    return s[0]

댓글 공유

스택 - 후위 표기법

카테고리 Python, DataStructure, Stack

후위표기법 1

연산자를 피연산자 뒤에 쓰는 연산기법

예를 들어, 3+5x2 를 중위 표기법이라 하고,

352x+를 후위 표기법이라고 한다.

계산 방법

3+5x2를 후위 표기법으로 적으면, 352x+이다.

352x+를 계산하기 위해서 다음과정을 따른다.

  1. 피연산자(숫자)는 스택에 담는다. [3,5,2]
  2. 연산자를 만나면, 스택에서 피연산자 2개를 꺼내 계산한다.
  3. 결과값을 다시 스택에 넣는다. [3,10]
  4. 다음 연산자는 +이므로 3+10을 계산한다.
  • 컴퓨터 입장에서는 후위 표기법이 연산의 우선순위가 명확하다는 장점이 있다.

중위 표기법을 후위 표기법으로 변환

3+5x2를 후위 표기법으로 바꾸는 과정을 알아보자.

  1. 피연산자 3을 결과값에 추가
    • 연산자 스택에 push
  3. 피연산자 5 결과값에 추가
  4. x 연산자와 스택의 마지막 값인 + 우선순위 비교
  5. x 연산자가 우선순위 높으므로 스택에 push
  6. 피연산자 2 결과값에 추가
  7. 스택이 빌 때까지 pop하여 결과값에 추가

3x5+2를 후위 표기법으로 바꿔보자.

  1. 피연산자 3을 결과값에 추가
  2. x 연산자 스택에 push
  3. 피연산자 5 결과값에 추가
    • 연산자와 스택의 마지막 값인 x 우선순위 비교
  5. 스택의 마지막 값인 x 연산자가 높으니 pop하여 결과값에 추가
    • 연산자는 스택에 push
  7. 피연산자 2을 결과값에 추가
  8. 스택이 빌 때까지 pop하여 결과값에 추가

문제 풀이

Stack 클래스를 이용한 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def solution(str):
    priority = {'+':2,'-':2,'*':1,'/':1}
    s = Stack()

    result = ''
    for x in str:
        if x not in priority.keys():
            result += x
        else:
            if s.top == None:
                s.push(x)
            else:
                if priority[s.top.data] < priority[x]:
                    s_pop = s.pop()
                    result += s_pop
                s.push(x)

    while not s.is_empty():
        s_pop = s.pop()
        result += s_pop

    return result

아래는 if 문으 조금 줄여보았다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def solution(str):
    priority = {'+':2,'-':2,'*':1,'/':1}
    s = Stack()

    result = ''
    for x in str:
        if x not in priority.keys():
            result += x
        else:
            if not s.is_empty() and priority[s.top.data] < priority[x]:
                s_pop = s.pop()
                result += s_pop
            s.push(x)

    while not s.is_empty():
        s_pop = s.pop()
        result += s_pop

    return result

댓글 공유

스택 - 연습문제

카테고리 Python, DataStructure, Stack

문제 1. 괄호 짝 검사

괄호의 짝이 바르면 True, 바르지 않으면 False를 반환하는 함수를 작성하라.

예를 들어 ((a*(b+c))-d) / e는 괄호의 짝이 올바르지만, (((a*(b+c))-d) / e 는 괄호의 짝이 맞지 않는다.

괄호는 소괄호(())만 사용한다.

풀이

1
2
3
4
5
6
7
8
9
10
def solution(str):
    stack = Stack()

    for x in str:
        if x == '(':
            stack.push(x)
        elif x == ')':
            if not stack.pop():
                return False
    return stack.is_empty()
  • 여는 괄호가 나오면 stack에 Push
  • 닫는 괄호가 나오면 stack을 pop
    • 이 때, stack에서 아무것도 pop되지 않는다면, 제대로 된 괄호가 구성되지 않은 것이다.

문제 2. 소,중,대괄호 짝 검사

소괄호, 중괄호, 대괄호 짝이 맞는지 검사

1
2
3
"[{a * (b + c)} - d] / e" # True

"[{a * (b + c)] - d] / e" # False

풀이

1
2
3
4
5
6
7
8
9
10
11
12
def solution(str):
    brackets = {")":"(", "}":"{", "]":"["}
    stack = Stack()

    for x in str:
        if x in brackets.values():
            stack.push(x)
        elif x in brackets:
            popped = stack.pop()
            if not popped or brackets[x] != popped:
                return False
    return stack.is_empty()
  • brackets을 관리하는 딕셔너리를 만든다.
  • 여는 괄호면 stack에 push한다.
  • 닫는 괄호면, 해당 닫는 괄호와 짝을 이루는 여는 괄호가 stack.pop()한 요소와 같은지 비교
    • 만약 다르거나 pop한 요소가 None이라면 False

문제 3. 짝지어 제거하기

같은 알파벳 2개가 붙어 있는 짝을 찾습니다.

그 다음 그 둘을 제거한 뒤 앞뒤로 문자열을 이어 붙입니다.

이 과정을 반복하여 문자열이 모두 제거된다면 1을 반환하고 그렇지 않으면 0을 반환합니다.

풀이

1
2
3
4
5
6
7
8
9
def solution(str):
    stack = []

    for ch in str:
        if stack and ch == stack[-1]:
            stack.pop()
        else:
            stack.append(ch)
    return 0 if stack else 1
  • stack 클래스 대신 배열을 사용했다.
  • stack의 push(): append()
  • stack의 pop(): pop()
  • stack의 peek(): [-1]로 인덱싱
  • is_empty(): 빈 리스트 논리값은 False 임을 이용

댓글 공유

스택 - 파이썬으로 스택(stack) 구현하기

카테고리 Python, DataStructure, Stack

파이썬으로 Stack(스택) 구현하기

stack

  • 스택은 서류나 책 위에 다른 서류나 책을 쌓아 올리는 형태이다.
  • 자료를 꺼낼 때에는 맨 위부터 꺼내야한다. 후입선출(Last In First Out, LIFO)

stack2

  • 90도 눕혀서 보게 되면 연결리스트와 비슷한 구조를 지닌다.
  • 연결리스트의 head를 스택에서는 top이라고 부른다.

Stack 메서드

  • push(data): data를 넣는 작업, 연결리스트의 appendLeft와 같다.
  • pop(): 자료를 꺼내는 작업, 연결리스트의 popLeft와 같다.
  • peek(): 마지막에 넣은 자료 확인, pop과 비슷하지만 값을 제거하지는 않는다.
  • is_empty(): 빈 스택인지 확인

Stack 클래스 만들기

  • 단일 연결리스트를 활용하여 Stack 클래스에서는 top 속성을 넣고 length 속성은 뺀다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Node:
  def __init__(self,data):
    self.data = data
    self.next = None

class Stack:
  def __init__(self):
    self.top = None

  def push(self,data):
    node = Node(data)
    if self.top == None:
      self.top = node
    else:
      node.next = self.top
      self.top = node

  def pop(self):
    if self.top == None:
      return None

    node = self.top
    self.top = node.next
    return node.data

  def peek(self):
    if self.top == None:
      return None
    return self.top.data

  def is_empty(self):
    return self.top == None

댓글 공유

  • page 1 of 1

loco9939

author.bio


author.job