My Tech Blog (스택)

스택(Stack)개요"스택"은 데이터를 쌓아서 사용하는 자료구조로, "후입선출(LIFO, Last In First Out)" 방식으로 작동한다. 즉, 나중에 들어간 데이터가 먼저 나오는 구조이다. 스택은 주로 함수 호출, 계산기 프로그램에서 수식 계산, 또는 브라우저의 뒤로 가기 기능 등에서 사용된다.* 이와 반대의 "선입선출(FIFO, First In First Out)" 구조의 자료구조를 '큐'라고 한다.   스택을 활용한 코딩테스트 문제는 유형이 정해져 있다. 문제를 잘 읽어보고 데이터를 쌓아 올린다든지, 나중에 쌓은 데이터를 먼저 처리하는 방식이면 스택을 활용하면 된다.  스택을 사용하는 문제 유형 ✅ 괄호 유효성 검사주어진 문자열에서 괄호의 짝이 맞는지 확인하는 문제스택을 사용해 여는 괄호는 스..

📑 1. 문제설명💡 2. 풀이 과정문제 예시처럼 5*5 격자가 있다고 가정 해 보면 격자의 가장 아래 칸부터 인형이 차곡차곡 쌓여 있고, 가장 위에 있는 인형을 집어 올릴 수 있다. 이 문제에서 "집어 올린 인형은 바구니에 쌓이는데 바구니의 가장 아래 칸부터 인형이 순서대로 쌓인다."라는 부분을 보면 스택 문제인 걸 바로 알 수 있다. 게임화면이나 바구니를 스택이라고 생각하면 된다. 문제는 board 배열을 스택으로 변환시키는 것이 어렵다. 만약에 값이 0이 들어오면 빈 칸이기 때문에 스택에 넣지 않는다. 그리고 크레인이 인형을 꺼내는 것은 stack.pop()으로 구현할 수 있다. 인형뽑기 게임 로직 1. 바구니가 빈 경우 -> 무조건 푸시2. 바구니가 비지 않은 경우  2-1. 바구니의 가장 위에..

📑 1. 문제설명10진수를 입력받아 2진수로 변환해 반환하는 solution() 함수를 구현하세요 제약조건decimal은 1이상 10억 미만의 자연수입출력 예decimalreturn10101027110111234511000000111001 💡 2. 풀이 과정10진수를 2진수로 표현하는 과정은 이미 수학적으로 증명된 것이기 때문에 간단하게 적는다.10진수 N을 2로 나눈 나머지, 즉 %2 연산을 한 값을 저장하고, N은 다시 2로 나눈다.몫이 0이 아니라면 나머지를 버리고 다시 1을 수행한다모든 과정이 끝나고 1에서 저장한 수를 뒤부터 순서대로 가져와 붙인다.  예를 들어 십진수 13을 위 과정대로 2진수로 변환하는 모습은 위 그림과 같다. 13을 2로 나누어가면서 나눈 나머지를 순서대로 저장한 후, ..

🤖 1. 문제설명문제 설명이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.  이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요. 제한사항operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.operations의 원소는 큐가 수행할 연산을 나타냅니다.원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.   입출력 예 설명 입출력 예 #116과 -..

📑 1. 문제설명 입출력 예 설명 1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12] 2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13가진 음식의 스코빌 지수 = [13, 9, 10, 12] 모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.💡 2. 접근방식항상 정렬이 되어 있어서 낮은 순위부터 꺼낼 수 있는 우선순위 큐 사용Priority Queue(우선순위큐)배열을 우선순위 큐에 넣는다큐 안에서 가장 낮은 숫자가 k..

📑 1. 문제설명💡 2. 접근방식이중for문현재 인덱스에 있는 요소과 이후 모든 값을 비교하면서 현재 요소가 비교하고 있는 요소보다 커지면 break;를 걸어준다.그 전까지는 answer[i]++을 해 준다. 현재 요소가 더 크다는 말은 이후에 가격이 떨어졌다는 것을 의미하기 때문이다. 현재 요소가 비교하는 값과 같거나 더 적다면 가격이 유지되거나 오른 것이다.스택(Stack)근데 이게 스택/큐 문제라는데 스택으로는 어떻게 풀지? 오잉그래서 다른 사람들은 어떻게 푸는 지 좀 찾아 봤다. 그냥 이중포문으로 푸는게 더 간단한 것 같다. prices의 인덱스를 스택에 넣어 주면서 현재 가격과 스택의 가장 위 가격을 비교해준다. 스택이 비어있지 않고, 현재 가격이 스택의 가장 위 가격보다 작으면 바로 가격이..

1. 문제설명2. 접근방식1) 스택을 사용하지 않고 풀기문자열을 순회하며 닫힌 괄호와 열린 괄호의 갯수를 변수에 저장하고 개수가 같으면 true, 틀리면 false 를 반환하는 방법 2) 스택을 사용하여 괄호의 짝을 맞추는 방법단순히 생각해서 괄호가 열린 경우 스택에 넣고, 닫힌 괄호가 나오면 스택에서 꺼내는 방식 3. 문제풀이3-1. 스택 사용하지 않고 풀기프로그래머스에서는 큐/스택 카테고리에 있는 문제이지만 굳이 스택을 사용하지 않아도 깔끔하게 풀 수 있는 문제이다. 처음에는 열린 괄호를 openCnt, 닫힌 괄호를 closeCnt 에 저장해서 그 갯수가 일치하면 true를 반환하는 방식으로 코드를 짰다. class Solution {    boolean solution(String s) {     ..

1. 문제설명프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다. 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요. 제한 사항작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.작업 진도는 100 미만의 자연수입니다.작업 속도는 100 이하의 자연수..