728x90

stack 5

[Python] 프로그래머스 - 대중소 괄호 짝 맞추기

문제 설명 여섯 가지 괄호 '(', ')', '{', '}', '[', ']'로 이루어진 문자열이 바르게 닫힌 문자열인지 체크. 바르게 닫힌 문자열이란 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로, '[' 문자로 열렸으면 ']' 문자로, '{' 문자로 열렸으면 '}' 문자로 닫히는 문자열을 의미함. - 제대로 닫히지 않은 문자열 예시: ((]], ([)] - 제대로 닫힌 문자열 예시: [[(())]]{} 문자열 s가 주어졌을 때, 문자열 s가 바르게 닫힌 문자열일 경우 True를 그렇지 않으면 False를 리턴하는 코드를 작성할 것. 단, 문자열 s의 길이는 1 이상 40이하이며 문자열 s는 위의 6개 괄호 문자로만 이루어짐. 문제 접근 전형적인 스택 풀이 문제이다. 문자열 s를 처음부터 훑으면..

[python] 프로그래머스 - 올바른 괄호

https://programmers.co.kr/learn/courses/30/lessons/12909 스택을 이용해서 풀이 가능한 전형적인 문제이다. 나는 직접 스택을 구현해서 풀이했지만, 프로그래머스 스터디 리더님께서는 스택을 직접 구현하지 않고 변수를 활용해서 풀이하셨다. 어쨌든 스택의 원리를 이용한다는 점에선 풀이 접근에 변함이 없다. 직접 구현하면서도 이렇게 푸는 것보다 더 나은 방법이 있겠다 싶었지만...나는 직접 구현하는 게 좀 더 직관적이라 매번 그렇게 푸는 것 같다. pop, push 연산을 수행하는 것보단 변수만으로 구현하는 게 효율성 면에서 낫다. 특히, 공간 복잡도 면에서 더욱 그럴 것이다. def solution(s): answer = True c = 0 for char in s: ..

[python] leetcode 739. Daily Temperatures

https://leetcode.com/problems/daily-temperatures/ 문제 설명 매일의 화씨 온도 리스트 T를 입력받아서, 더 따뜻한 날씨가 될 때까지 며칠을 더 기다려야 하는지 리스트로 리턴하라. 문제 접근 및 풀이 [1st Try] - 투 포인터 1) 현재를 가리키는 포인터를 left, 미래를 가리키는 포인터를 right으로 설정. 2) 미래의 기온이 현재의 기온보다 높지 않다면 right 포인터를 한 칸 옮긴다. 3) 미래의 온도가 현재의 온도보다 높다면 결과가 되는 리스트에 right과 left의 차이를 append하고, left 포인터를 한 칸 이동, right 포인터를 left의 바로 다음 칸으로 이동시킨다. 4) left가 마지막에서 두번째 원소를 가리킬 때까지 반복한다...

[python] leetcode 20. Valid Parentheses

https://leetcode.com/problems/valid-parentheses 문제 설명 괄호로 된 입력값이 올바른지 판별 (기본기 점검으로 좋은 문제) 문제 풀이 접근 1) 각 여는 괄호는 짝이 맞는 닫는 괄호가 있다 2) 닫는 괄호의 순서는 여는 괄호의 순서와 반대로 이루어져야 한다. 가장 마지막에 오는 여는 괄호는 가장 처음에 오는 닫는 괄호와 만나게 되고, 이런 패턴이 계속 반복된다. → 스택으로 접근 (LIFO) → 여는 괄호는 스택에 넣고, 닫는 괄호를 만나면 pop해서 짝이 맞는지 대조하는 방식 → 짝이 맞는지 대조하는 데에 편리한 자료구조는 딕셔너리 문제 풀이 class Solution: def isValid(self, s: str) -> bool: parentheses = { "(..

[파이썬(python) 자료구조] 스택(Stack), 큐(Queue)

스택(Stack) 스택은 후입선출(LIFO)로 처리되는 자료구조이다. 즉, 스택에 가장 마지막에 들어간 요소가 가장 처음으로 꺼내진다. Stack은 무엇인가가 쌓여있는 걸 지칭한다는 점을 생각해보면 가장 마지막에 쌓여진 것이 가장 처음으로 꺼내진다는 것의 개념은 쉽게 이해될 것이다. 스택은 흔히 연결리스트로 구현된다. 이 경우에 스택 선언을 위해 메모리 내의 연속된 공간을 할당할 필요가 없어지며, 실제로 스택 내의 요소 간 순서가 메모리 내의 물리적 순서와는 무관하게 될 것이다. 그러나 파이썬에서는 리스트가 스택으로 충분히 기능할 수 있기 때문에 연결리스트로 스택을 구현하지 않아도 된다. 스택의 주 연산은 삽입(push)와 제거(pop)이다. 삽입은 스택의 가장 마지막 자리에 요소가 추가되는 것이고, 제..

728x90