[묘공단] 코테 합격자되기 3주차

---

📌 6장 스택(자료구조)

📌💡 6-1. 스택 개념 : 먼저 들어간 것이 마지막에 나오는 규칙 선입후출 FILO

• push : 스택에 삽입하는 연산
• pop : 스택에서 꺼내는 연산

동작원리 :

0. 빈 스택 ()
1. 1 푸시 (1)
2. 2 푸시 (2 1)
3. 팝 (1)
4. 3 푸시 (3 1)
5. 팝 (1)
6. 팝 ()

📌💡 6-2. 스택의 정의 :

ADT = 추상자료형 : 인터페이스만 있고, 실제로 구현은 되지 않은 자료형

스택의 adt(=자료형의 설계도 정도)

• 스택의 연산

1. void push(ItemType ITEM)
2. ItemType pop()
3. boolean isFull() : 가득 차있을시 True
4. boolean isEmpty() : 데이터가 없을시 True

• 스택의 저장

1. int top : 최근에 푸시한 데이터의 위치를 기록
2. ItemType data(maxsize 설정) : 스택을 관리하는 배열

** push 연산시 :
데이터 삽입 (=push) -> 데이터 차있는지 확인 (=isFull()) -> 가득 안차있다면? -> 1증가 (=top) -> 저장소에 삽입데이터 추가 (=data())

** pop 연산시 :
데이터 빼기 (=pop) -> 데이터 차있는지 확인 (=isEmpty()) -> 데이터가 있다면? -> 1감소 (=top) -> 저장소에 데이터 빼기 (=data())

스택 세부구현(python)

# 파이썬은 스택 메소드를 제공하지는 않지만, 리스트로 사용
stack = [] # 스택 리스트 초기화 -> 이때 top X, 파이썬은 리스트 크기 동적관리

def push(stack, item):
	#스택에 데이터를 추가하는 함수
    stack.append(item) #파이썬은 리스트의 크기 동적으로 관리 - 따라서 isFull 구현 X
    print("데이터가 추가되었습니다.")
    
def pop(stack): 
	#스택에서 아이템을 꺼내는 함수
    if len(stack) == 0: #파이썬은 리스트의 크기 동적으로 관리 - 따라서 isEmpty 구현 X
    	print("스택이 비어 있씁니다.")
        return None
    else: 
    	return stack.pop()

python 메서드

#사실 파이썬은 메서드 구현 돼있음, 예외처리 다함
stack = []

#push
stack.append(1)
stack.append(2)
stack.append(3)

#pop
top_element = stack.pop()
next_element = stack.pop()

#스택 크기 
len(stack)

🌟 문제 데이터 흐름이 스택에 맞는지 확인이 중요!🌟

(ex) 임의 접근이 아닌, 최근에 삽입한 데이터 대상으로 연산시 사용)

📌 6-3. 몸풀기 문제

🩶 문제 8. 괄호 짝 맞추기

주어진 데이터 : String
권장 시간 복잡도 : O(N)

제약조건 :

• 열린 괄호는 자신과 가장 가까운 닫힌 괄호를 만나면 상쇄됩니다 > "가까운" 스택의심
• 상쇄 조건은 열린 괄호가 먼저 와야하고, 열린 괄호와 닫힌 괄호 사이에 아무것도 없어야 합니다. > 아무것도 없으므로 top, pop 사용 가능
• 더 상쇄할 괄호가 없을 때까지 상쇄를 반복합니다.

def solution(s):
  stack = [ ]#짝 맞추면 stack은 항상 비어있음
  for i in s:
    if i == "(": #열린괄호일시
      stack.append(i) #추가하기, 이젠 닫힌괄호를 찾아야 됨
    elif c == ")": #닫힌괄호일시 
      if not stack: #stack 비어있을시, 처음부터 닫힌괄호면 매칭 못함 예외처리
        return False
      else:
        stack.pop( ) #안비어있으면 pop 
  #결과확인
  return len(stack) == 0 if 1 else 0 
    
# TEST 코드 입니다. 주석을 풀고 실행시켜보세요
#print(solution('(())()')) # 반환값 : True
#print(solution('((())()')) # 반환값 : False

🩶 문제 9. 10진수를 2진수로 변환하기

주어진 데이터 : int ex) (())() = True, ((())() = False
권장 시간 복잡도 : O(logN)

제약조건 : X

문제보자마자 스택을 써야하는지 생각은 안나지만,
10진수 2진수 연산과정에서, 나머지값을 "차례대로" 넣고 거꾸로 보여주면 상관없겠다는 생각이 들었는데 이게 stack인것 같다.

def solution(i):
    stack = []
    while i > 0:
        r = i % 2 #나머지 값 추출
        i //= 2 #나누기 값 적용
        stack.append(str(r)) #스트링으로 들어가야지, join문법사용 가능
    return ''.join(stack[::-1]) #순서 뒤집기
    
    
# TEST 코드 입니다. 주석을 풀고 실행시켜보세요
# print(solution(10)) #반환값 :  1010
# print(solution(27)) #반환값 :  11011
# print(solution(12345)) #반환값 : 11000000111001

📌 6-4. 몸풀기 문제

🩶 문제 10. 괄호회전

🩶 문제 11. 짝지어 제거하기

주어진 데이터 : 알파벳 소문자 문자열
권장 시간 복잡도 : O(N)

baabaa -> 'aa'짝제거 -> bbaa ->'bb'짝제거 -> aa ->'aa'짝제거 -> 성공

제약조건 :

• 문자열의 길이 : 1,000,000 이하의 자연수
• 문자열은 모두 소문자로 이루어져있습니다.

데이터를 근처값만 차례대로 검사하기 때문에, '괄호 짝 문제'

• 매칭되면? push안하고 기존에 들어간 최근값 pop = 짝지어제거 가능
• 매칭안되면? push

def solution(s):
  stack = [ ]  
  for i in s:#검사값 추출
  	#짝지어 제거
    if stack and stack[-1] == i:  # 끝에 값 - 검사값 매칭시 + 처음에는 무조건 push
      stack.pop( )   # 끝에값 pop
    #매칭실패시 push
    else:
      stack.append(c)  # 문자 추가
  return int(len(stack) == 0 if 1 else 0) #비어있으면 1, 아니면 0
  
# TEST 코드 입니다. 주석을 풀고 실행시켜보세요
# print(solution('baabaa')) #반환값 :  1
# print(solution('cdcd')) #반환값 : 0
  

🩶 문제 12. 주식 가격

🩶 문제 13. 크레인 인형 뽑기 게임

🩶 문제 14. 표 편집

실력이 없어,, 풀게되면 추후 올릴 예정입니다,,,😂