본문 바로가기
반응형

스택

 (8)
[백준] 좋은 단어(python) 백준, 좋은 단어 3986번: 좋은 단어 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 www.acmicpc.net TL;DR 스택(Stack) 문제 요약 1. A와 B로 이루어진 문자열에 대해서 A와 B끼리 다른 선과 교차되지 않고 선을 그을 수 있는 좋은 문자의 수를 찾아라. - 다른 선과 교차되지 않고 선을 긋는다는 것은 적어도 A와 B가 하나씩 교차되는 형태가 없어야 한다는 뜻이다. - 스택에 문자를 하나씩 넣어가며 비교하는 방법으로 문제를 해결할 수 있다. 입출력 형태 예시 1 :: ABAB의 경우는 A와 B를 서로 선으로 연결했을 때 두 선이 서로 교차되기 ..
[백준] 막대기(python) 백준, 막대기 TL;DR 스택(Stack) 문제 요약 1. 높이가 서로 다른(같을 수 있음) 막대기를 일렬로 세운 후 오른쪽에서 봤을 때 보이는 막대기의 개수를 알아내는 프로그램을 작성하라. - 일렬로 세운 막대기를 가장 오른쪽에서 봤을 때 보이는 막대기의 수를 반환하면 된다. - 가장 오른쪽에 있는 막대기보다 크기가 작은 막대기들은 보이지 않을 것이고, 큰 막대기들이 보일 것이다. 입출력 형태 - 주어진 예시에서 1번 막대기는 2번 막대기에 가려지고 4, 5번 막대기는 6번 막대기에 의해 가려져서 보이지 않는다. 따라서 보이는 막대기는 2, 3, 6번 막대기가 되어 총 3개가 된다. 풀이 막대기의 길이를 스택에 입력받는다. 가장 마지막에 들어오는 원소가 스택의 최상단에 위치할 것이다. 스택에서 하나씩 ..
[백준] 고무오리 디버깅(python) 백준, 고무오리 디버깅 TL;DR 스택(Stack) 구현(Implementation) 문제 요약 1. 문제를 받은 상태에서 고무오리를 받으면 문제를 해결한다. 2. 문제가 없는 상태에서 고무오리를 받으면 두 문제를 추가한다. 3. 주어진 입력에 대해서 문제를 모두 해결하였으면 '고무오리야 사랑해'를 아니라면 '힝구'를 출력한다. - 문제와 고무오리가 입력으로 주어질 때 문제가 스택에 있고 고무오리를 입력으로 받는다면 스택을 비우는 방식으로 문제를 해결할 수 있을 것이다. - 스택이 비어있을 때 고무오리가 입력으로 들어온다면 두 문제를 스택에 추가해야 한다. 입출력 형태 문제를 모두 해결한 경우와 그렇지 않은 경우의 예시를 가져왔다. - 예제 입력 1에서는 (문제 - 고무오리), (문제, 문제 - 고무오리..
[리트코드] Letter Combinations of a Phone Number(python) 리트코드, Letter Combinations of a Phone Number_핸드폰 글자 조합하기 TL;DR DFS 문제 분석 1. 핸드폰 자판 2-9에는 문자들이 할당되어 있다. 2. 주어진 자판 조합에 대해서 만들 수 있는 모든 문자들을 반환하라. 3. 반환하는 문자의 순서는 상관 없다. - 문제에서 주어진 핸드폰 2 ~ 9에는 a ~ z까지의 문자가 할당되어 있다. - 문제에서 숫자 조합을 주어지면 해당 문자에 할당된 알파벳을 조합할 수 있는 모든 경우의 수를 반환하면 된다. 입출력 형태 - 예시 1 : 자판 23이 주어졌다면 만들 수 있는 조합은 "abc"와 "def"를 활용한 총 9개의 조합이다. - 예시 3 : 하나의 자판이 주어졌다면 만들 수 있는 조합은 할당된 알파벳은 "abc"를 각각 ..
[프로그래머스] 올바른 괄호(python) 프로그래머스, 올바른 괄호 TL;DR 스택(Stack) 문제 분석 1. 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻이다. 2. '(' 또는 ')'로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를, 아니면 false를 반환하라. - 1. 열린 괄호 뒤에 닫힌 괄호가 오는, 하나의 완성된 괄호 문자가 되었을 때를 올바른 괄호라고 문제에서 정의하고 있다. - 2. 문제 조건에 따라 올바른 괄호로 구성되었는지 여부에 따라 True 또는 False를 반환한다. 입출력 형태 - 결과가 True인 예시들은 모두 ()가 쌍을 이룬다. - 결과가 False인 예시들은 () 쌍을 이루지 않는다. 풀이 def solution(s): a..
[리트코드] Implement Stack using Queues(python) 리트코드, Implement Stack using Queues_큐로 스택 구현하기 TL;DR 스택(Stack)의 개념을 이해하고 있는지 문제 분석 1. 두 개의 큐를 사용하여 스택을 구현하여라. 2. 구현된 스택은 push, top, pop, empty 함수를 지원해야 한다. 3. 큐를 사용할 때 push to back, peek/pop from front, size, is empty와 같은 함수만 사용 가능하다. - 큐를 활용하여 스택의 기능인 push, pop, top, empty를 구현하는 문제이다. - 스택은 Last In, First Out(LIFO) 구조를 갖는 자료구조 형이다. - push는 스택의 새로운 원소를 추가하는 동작을 수행한다. - top은 가장 마지막에 추가된 스택의 원소를 반환..
[리트코드] Valid Parentheses(python) 리트코드, Valid Parentheses_유효한 괄호 TL;DR 스택(stack) 문제 분석 1. 주어진 괄호 문자('(', ')', '{', '}', '[', ']')를 포함하고 있는 문자열 s가 유효한지를 판별해야 한다. 2. 열린 괄호는 같은 종류의 닫힌 괄호와 붙어있어야 한다. 3. 열린 괄호와 같은 종류의 닫힌 괄호는 정확한 순서로 되어 있어야 한다. - 1 : 해결해야 하는 문제에 대해서 설명하고 있다. - 2 ~ 3 : 같은 종류의 열린 괄호와 닫힌 괄호로만 이루어져있는 문자열이 올바른 괄호 문자라는 것을 설명하고 있다. 입출력 형태 - 입출력 예시를 통해 문제에서 말하는 유효한 괄호문자의 조건을 확인할 수 있다. - 예시 1과 예시 2는 서로 같은 종류의 괄호들이 올바르게 잘 배치되어 있..
[프로그래머스] 크레인 인형뽑기 게임(python) 2021년 5월 20일 Algorithm, 프로그래머스, 크레인 인형뽑기 게임 2019년 카카오 개발자 겨울 인턴십 출제 문제 TL;DR 스택(Stack)을 활용하여 주어진 문제를 구현할 수 있는지 문제 분석 1. 게임 화면은 "1 x 1" 크기의 칸들로 이루어진 "N x N" 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 모든 인형은 "1 x 1" 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다. 2. 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓이게 되는 데, 이때 바구니의 가장 아래..

티스토리툴바