알고리즘 5일, 6일차

(2021.06.18 - 19)

22번 - 스택

스택을 구현하는 문제였다. 내장함수를 이용하는 버전과 클래스와 함수를 만들어서 푸는 두가지 버전으로 해결해 보았다.

포인트

• input()을 사용하면 시간초과 뜬다.
• stdin.readline() 사용

내장함수 ver.

리스트와 내장 함수를 이용해서 스택의 효과를 내는 방법이다.

풀이

• 먼저 스택이라는 빈 리스트를 설정해준다.

• 입력값의 0번째 명령어에 따라 조건에 맞는 행동값을 준다.

클래스 & 함수 ver.

알고리즘 강의에서 처럼 노드클래스와 스택클래스를 만들고 해당 함수들을 만들어 스택을 구현하는 방식이다.

풀이

• 리스트가 아닌 노드(노드와 포인터가 존재)로 데이터를 저장하는 방식을 사용한다.

• 스택 클래스는 stack = Stack() 으로 인스턴스를 실행해주고 인스턴스를 통해 각각의 메서드를 호출하는 방식으로 구현한다.

• 인스턴스를 실행하면 처음 생성자 메서드가 자동 호출되면서 초기 세팅값이 실행되고 이후 메서드를 통해 해당 동작을 수행한다.

from sys import stdin


class Node():  # 데이터 저장, 포인트 지정 클래스
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack():  # 데이터 입출력 방식 지정 클래스
    def __init__(self):  # 처음에 스택 불리면 헤드가 디폴트 none인 상태로 존재, 생성됨
        self.head = None
        self.len = 0

    def push(self, data):
        new_head = Node(data)  # 제일 마지막, 최신에 들어온 값을 새로운 헤드로 저장하기 전 임시저장해둔다
        new_head.next = self.head  # 최신 데이터의 다음 데이터는 지금의 헤드로 지정됨
        self.head = new_head  # 최신 데이터가 헤드가 됨
        self.len += 1  # 추가하면 길이 1증가
        return

    def pop(self):
        if self.is_empty():  
            return -1

        pop_data = self.head
        self.head = self.head.next
        self.len -= 1  # 데이터 출력돼서 빠지면 길이 -1 
        return pop_data.data

    def top(self):
        if self.is_empty():
            return -1
        return self.head.data

    def size(self):
        return self.len

    def empty(self):
        if self.is_empty():
            return 1
        return 0

    def is_empty(self):
        return self.head is None

n = int(input())
stack = Stack()

for _ in range(n):  # 여기서 언더바는 인덱스가 딱히 의미가없어서 생략하고 범위만큼 계속하라는 뜻
    cmd = stdin.readline().rstrip().split()  # readlines 아니고 readline 해야 정상적으로 실행됨
    order = cmd[0]
    if order == 'push':
        stack.push(cmd[1])
    elif order == 'pop':
        print(stack.pop())
    elif order == 'size':
        print(stack.size())
    elif order == 'empty':
        print(stack.empty())
    elif order == 'top':
        print(stack.top())

class 참고 자료 링크

class 개념, 용어

특수 메서드

• 특수 메서드 ex) 더블언더스코어(던더) _ init _

23번 - 제로

입력값이 0이면 pop, 0이 아니면 append 하는 문제

포인트

• 단순한 반복문일때, for _ in 형식으로 사용
  언더바 사용법

24번 - 괄호

괄호가 짝을 이루고 있으면 yes, 아니면 no를 출력하는 문제

풀이

• 여는 괄호가 나오면 스택에 append, 닫는 괄호가 나오면 pop을 해서 조건에 맞게 결과를 출력해준다.

• 스택이 0일때 닫는 괄호가 나오는 경우, 입력값을 다 돌았는데도 스택이 남아 있는 경우 짝이 맞지 않다는 뜻이므로 False를 반환한다.

25번 - 최소공배수

최소공배수를 구하는 문제이다.

풀이

• 사실 내장함수(최소공배수 lcm, 최대공약수 gcd) 이용하면 간단한다.

• 유클리드 호제법16번 참고

26번 - 이항계수

자연수 n, k가 주어졌을 때 이항 계수를 구하는 문제

풀이

• 이항 정리란 (a + b)**n, 두 항의 합에 관한 거듭제곱식을 정리한 개념이라고 볼 수 있다.
  

• 이때 변수의 계수를 이항 계수라고 하며, 일반항은 다음과 같다.
  

출처 링크 : 이항정리, 이항계수

• 해당 정리에 따라 이항 계수를 구하기 위해서는 팩토리얼을 구하는 함수를 만들어야 한다.

• 이후 K 가 0이면, 1을 반환하고 (0! = 1 이므로)

• 0이 아니면 n! / k!(n-k)! 을 구한다.

27번 - 다리놓기

중복이 없고 순서가 있는 우측 m개 중 n개를 뽑는 조합 문제이다.
(오른쪽 다리에서 n개 만큼 뽑으면 순서대로 다리가 결정되기 때문)

풀이

이 문제도 팩토리얼을 구하는 함수를 만든 후 조합 공식으로 푼다.

참고 링크

1. 경우의 수 공식
2. 조합

28번 - 균형잡힌 세상

24번 문제와 같이 괄호를 푸는 문제이다. 처음에는 공백까지도 처리를 해줘야한다고 생각해서 엄청 고민하고 시간을 썼지만 단순히 괄호 처리를 () 뿐만 아니라 [] 에 대해서도 해주는 방식으로 처리하면 되는 문제였다.

풀이

• 큰 골자는 24번과 동일하며 조건이 좀 더 붙는 차이가 있다.

from sys import stdin

while True:

    str_list = stdin.readline()
    if str_list[0] == '.':  # . 입력받으면 종료
        break

    stack = []
    answer = True  # no 조건에 걸리면 반환해줄 변수

    for i in str_list:  # 여는 괄호 시작되면 
        if i == '(' or i == '[':
            stack.append(i)  # 스택에 저장

        elif i == ')':  # 닫는 괄호 나오면
            if len(stack) == 0:  # 스택 비어있으면 여는 괄호 없었다는 거니까
                answer = False  # no 조건
                break
            if stack[-1] == '(':  # 스택 마지막에 저장된 값이 여는 괄호면
                stack.pop()  # 마지막 저장된 값 빼냄
            else:
                answer = False  # 위 조건 이외는 모두 no조건 오답처리
                break
        
        elif i == ']':  # 같은 내용
            if len(stack) == 0:
                answer = False
                break
            if stack[-1] == '[':
                stack.pop()
            else:
                answer = False
                break

    if answer and not stack:  # answer가 True 이면서 stack 이 비었을 때. (true 가 아닌게( = false)일때 true 인 상태)
        print('yes')  
    else:
        print('no')

포인트

• 조건이 [] 하나 더 생긴만큼 코드를 작성해서 answer 체크 변수가 참이고 스택이 참이 아닌 상태(빈 상태)일 때가 참을 만족하면 yes를 반환하게 작성했다.

29번 - 스택 수열

주어진 숫자의 배열을 만들기 위한 push(+)와 pop(-) 연산 과정을 출력하는 문제이다.

풀이

• 우선 값을 담을 빈 리스트 3개를 설정해 주었다.

  1. stack : push, pop 조건에 따라 값을 변경할 공간
  2. new_list : stack에서 빠져나온 값을 저장할 공간
  3. result : +, - 값을 반환할 공간

• 규칙을 살펴보면 n 만큼의 정렬된 수열(숫자 열)이 입력값과 같은 순서의 수열이 되기 위해서는 총 2n 만큼을 반복해야 한다.

• 총 2n번을 반복하면서 입력받은 수열과 비교하면서 샘플리스트의 숫자가 작거나 같으면 stack 리스트에 append 하고, 크다면 pop을 한다.

• 이때 샘플리스트가 마지막까지 갔다면 (샘플리스트의 인덱스가 n과 같아졌을 때), 스택에 저장된 값을 차례로 pop 해준다.

• 그 전까지는 위 조건에 맞게 push(append)와 pop을 반복한다.

• 반복이 끝나면 새로 만들어진 리스트와 입력 받은 수열을 비교해서 같으면 + - 순서를 출력하고

• 다르면 NO를 출력한다.

• while 문을 탈출하는 조건은 new_list가 n개 일 때다.

from sys import stdin

n = int(stdin.readline())
num_list = [int(stdin.readline().rstrip()) for _ in range(n)]  # [4, 3, 6, 8, 7, 5, 2, 1]
sample = list(range(1,n + 1))  # [1, 2, 3, 4, 5, 6, 7, 8]
                                # 0  1  2  3  4  5  6  7

stack = []
new_list = []
result = []
while len(new_list) != n:
    num_i = 0
    sample_i = 0
    for _ in range(2 * n):
        if sample_i == n:
            new_list.append(stack[-1])
            stack.pop()
            result.append('-')
            num_i += 1

        if sample_i < n:
            if sample[sample_i] <= num_list[num_i]:  # 8 < 8
                stack.append(sample[sample_i])
                sample_i += 1  # 7
                result.append('+')

            else:
                new_list.append(stack[-1])
                stack.pop()
                result.append('-')
                num_i += 1  # 3 >> 8

if new_list == num_list:
    for sign in result:
        print(sign)
else:
    print('NO')

소감

• 스택과 클래스에 관해 개념을 잡을 수 있었던 문제들이었다. 좀더 자세한 공부와 개념정리가 필요하다고 느낀다.
• 아직까지 클래스, 메서드, 인스턴스를 자유롭게 활용하는 것이 낯설고 모듈에 관한 개념도 적립해야할 필요를 느끼고 있다.
• 노드를 더 자유자재로 사용할 수 있으면 좋겠다.

더 공부할 개념

스택, 클래스, 메서드, 인스턴스, 모듈, 노드, 경우의 수