L.O.K

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ◎ 문제풀이 재료들이 배열에 차례대로 저장되어 있다. 햄버거를 만드는 패턴과 일치하는 케이스를 카운트 하면 된다. 배열에 저장되어 있는 재료들을 가장 왼쪽부터 차례대로 자료구조에 담으면서, 빵-야채-고기-빵 차례로 데이터가 나열되는지를 체크하면 된다. 자료구조는 리스트를 사용하였고 리스트에서 만들어진 햄버거 재료를 제거할 때, size가 가변적으로 변하니 인덱스 사용에 주의해야 한다. ◎ 코드 import java.util.*; class Solution { public int solution(int[] in..

2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net ◎ 문제해결 스택을 이용하면 쉽게 풀리는 문제이다. 스택을 처음에 발상했지만 시간복잡도에 걸릴 것이라 판단했었다. 그런데 다시 생각해보니 그렇지 않았다. 6 9 5 7 4 왼쪽부터 하나씩 포인터를 이동하면서 Stack의 Top과 비교한다. Top이 작으면 POP한다. 스택에 더이상 값이 없으면 0을 출력하고 Top에 자신보다 크거나 같은 수가 있으면 출력한다. 그리고 자신의 인덱스를 스택에 PUSH 한다. 스택에는 포인터 이전의 수가 모두 들어가 있지 않고 P..

https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net ◎문제풀이 우선순위와 STACK의 연관성을 이해하면 쉽게 풀리는 문제이다. A,B,C,D는 우선순위가 없이 순서대로 출력하면 된다. 반면 연산자는 우선순위가 있다. 우선순위대로 출력되어야 한다. *,/ 는 우선순위가 높다. +,-는 우선순위가 낮다. 우선순위가 높은 연산자가 먼저 출력되어야 한다. STACK은 LIFO이다. 그러므로 우선순위가 높은 연산자가 위에 있어야 한다. 그래야 먼저 PO..

17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net ◎ 문제풀이 단순 반복문으로 풀면 시간초과가 난다. 자료구조로 시간복잡도를 줄일 수 있는 능력을 보는 문제이다. [CodingTest] BOJ1046 에디터 ( 자료구조 ) with Python ◎ 문제 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 lordofkangs.tistory.com ( 위 문제도 자료구조로 시간복잡도를..

10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net ◎ 문제풀이 문제에 제시된 단어 하나하나를 모두 자료구조로 만들 필요는 없다. (완벽주의 조심!) 문제의 목적에 달성하기 위한 수단만 필요할 뿐이다. 즉, 레이저, 막대가 나왔다고 레이저, 막대를 자료구조로 만들 필요가 없다는 의미이다. 레이저가 막대기를 자르면 막대의 개수는 레이저 개수 + 1개 이다. "()"가 레이저이므로 레이저가 나올때까지 막대를 기억해야 한다고 생각해서 STACK을 떠올렸다. ")"는 두가지 경우가 있다. 1. 레이저인 경우 레이저가 등장하면 STA..

◎ 문제 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net ◎ 문제플이 큐 자료구조를 활용하면 쉽게 풀리는 문제이다. 1) 1부터 N까지 큐에 PUSH한다. 2) K번째 수를 찾으면 POP한다. 3) K번째 수가 아니면 POP하고 다시 PUSH한다. ◎ 코드 Python from collections import deque import sys input = sys.stdin.readline n,k = map(int,input().split()) q = deque([ x for x in range(1,n+1)]) result = [] count = 1 while q : if count == k : # K..

◎ 문제 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net ◎ 문제풀이 자료구조의 힘을 알 수 있는 문제이다. 적절한 자료구조는 시간복잡도를 현격히 줄일 수 있다. 내가 처음 구현했던 코드는 시간초과가 발생했다. 처음 구현한 코드 import sys input = sys.stdin.readline data = list(input().strip("\n")) cursor = len(data) n = int(input()) def editor(data,op) : global cursor if op[0] == "P" :..

@문제 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net @문제풀이 STACK의 구조를 이해하는 문제이다. 두 가지 포인터가 필요하다. current : STACK에 PUSH 되었던 가장 큰 수 top : STACK에서 가장 먼저 POP되는 값 STACK에 오름차순으로 PUSH 되므로 입력값이 current보다 커야 PUSH를 할 수 있다. POP은 입력값과 top이 같아야 한다. 만약 top과 입력값이 다르면 STACK으로 구현..

1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 1. 문제 추상화 1부터 n까지 수로 이루어진 수열 A가 주어진다. 오름차순으로 스택에 push하여 수열A를 구현할 수 있는지 판별하시오. 구현이 불가능하면 NO를 출력하고 구현이 가능하면 어떤 과정을 통해 구현되는지 출력하시오. (push : '+' 출력, pop '-'출력' ) 2. 알고리즘 조건은 두 가지이다. 1. 스택을 사용하라. 2. 오름차순으로 push해라. 스택은 L..

9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 1. 문제 추상화 '(' 와 ')' 만으로 이루어진 문자열을 PS라 부른다. 그리고 괄호가 열리고 온전히 닫히는 PS를 VPS라 부른다. 주어진 PS 중 VPS를 구분하라. 2. 알고리즘 조금 고민했다. 그리고 한 가지 개념이 스쳐지나갔다. 바로 '스택(Stack)'이다. VPS는 두 가지 특성이 있다. 1. 나중에 열린 괄호가 먼저 닫혀야 한다. 2. 모든 열린 괄호는 닫혀야 한다. 1번은 LIFO의 특징이다. 그러므로 스택과 알..