프로그래머스 스택 문제를 풀어보았다.
문제
-
문제 설명
초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. -
제한사항
prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
prices의 길이는 2 이상 100,000 이하입니다.
입출력 예
prices return
[1, 2, 3, 2, 3][4, 3, 1, 1, 0]
입출력 예 설명
- 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
- 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
- 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
- 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
- 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.
풀이
#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100002
typedef int element;
typedef struct {
element data[MAX_STACK_SIZE];
int top;
} StackType;
//스택 초기화 함수
void init_stack(StackType *s)
{
s->top = -1;
}
//공백 상태 검출 함수
int is_empty(StackType *s)
{
return (s->top == -1);
}
//삽입
void push(StackType *s,element item)
{
s->data[++(s->top)] = item;
}
//삭제
element pop(StackType *s)
{
return s->data[(s->top)--];
}
int* solution(int prices[], size_t len)
{
int* answer = (int*)malloc(sizeof(int) * len);
StackType st;
init_stack(&st);
for (int i =0 ; i< len; i++)
{
while (!is_empty(&st) && prices[st.data[st.top]] > prices[i])
{
answer[st.data[st.top]] = i - st.data[st.top]; // 현재시간 - 마지막 시간 = 유지시간
pop(&st); //while문 돌때는 top을 빼줘야 현재상태랑 비교할 수 있음
}
push(&st,i); //현재시간을 넣는다. 그런데 현재시간이 위의 조건을 만족하면
//계속 top을 갱신을 해준다. 스택은 가격이 떨어지지 않은 시간들의 모음이다.
}
while (!is_empty(&st))
{
answer[st.data[st.top]] = len -1 - st.data[st.top] ;
pop(&st); //pop을 나중에 해줘야
}
return answer;
}
// int main(void)
// {
// int a[5]= {2,2,4,2,3};
// solution(a,5);
// }
과정
아이디어를 생각해내는 데 상당히 오랜 시간이 걸렸다..ㅎ
이 문제는 스택을 이용하는 카테고리라 어떻게 스택을 이용할 지 고민이 되었다.
어떤 것을 넣고 어떤 조건일 때 빼야 할 지가 핵심이지 않았나 싶다.
typedef int element;
typedef struct {
element data[MAX_STACK_SIZE];
int top;
} StackType;
//스택 초기화 함수
void init_stack(StackType *s)
{
s->top = -1;
}
//공백 상태 검출 함수
int is_empty(StackType *s)
{
return (s->top == -1);
}
//삽입
void push(StackType *s,element item)
{
s->data[++(s->top)] = item;
}
//삭제
element pop(StackType *s)
{
return s->data[(s->top)--];
}여기까지는 기본적인 스택을 만들었다.
이 스택을 어떻게 이용해야할까..
->스택을 시간 개념으로 넣어서 이용해야 겠다는 생각을 했다.
int* solution(int prices[], size_t len)
{
int* answer = (int*)malloc(sizeof(int) * len);
StackType st;
init_stack(&st);answer 배열을 동적할당 해주고 , 스택을 생성하고, 초기화하면서 시작한다.
for (int i =0 ; i< len; i++)
{
while (!is_empty(&st) && prices[st.data[st.top]] > prices[i]) //top의 data와 현재 price를 비교.
{
answer[st.data[st.top]] = i - st.data[st.top]; // 현재시간 - 마지막 시간 = 유지시간
pop(&st); //while문 돌때는 top을 빼줘야(pop해줘야) 현재 상태랑 비교할 수 있음
}
push(&st,i); //현재시간을 넣는다. 그런데 현재시간이 위의 조건을 만족하면
//계속 top을 갱신을 해준다. 스택은 가격이 떨어지지 않은 시간들의 모음이다.
> }
위의 for 문은 스택을 채워넣고 빼는 과정이다. 이 과정에서 떨어진 가격이 있다면 while문을 돌면서 answer에 바로 갱신을 한다. while문이 걸리지 않은 조건이면,즉, 스택은 떨어지지 않으면 push 하기 때문에 while에서 현재와 계속 비교를 돌릴 수 있다.
저 while 조건이 핵심이라고 느낀다.조건 체크하면서 pop하면서 top을 줄이고 비교해서 answer 갱신하고..while문을 빠져나오면 즉 현재가격이 top가격보다 크거나 같다면 떨어지지 않았다는 의미이므로 push한다.
answer배열을 넣어줄 때는 현재시간 - 마지막 시간 = 유지시간이어서 그 값을 넣는다.
while (!is_empty(&st))
{
answer[st.data[st.top]] = len -1 - st.data[st.top] ;
pop(&st); //pop을 나중에 해줘야
}
return answer;
}위의 과정을 거쳐서 모든 경우에 대해서 떨어진 가격에 대해서는 모두 체크를 했다.
(answer에 떨어졌던 상황은 이미 시간을 채워놓았다.)
이제 스택에는 남은 시간개념들만 남아있는 상황이다.
스택이 비게 될 때까지 pop 한다.
answer에 스택 데이터를 뽑아서 채울 때는 전체 길이(기간)에서 top에 대한 스택 data에 -1 을 해줘야한다.
스택은 떨어지지 않은 시간들의 모음이기 때문에 스택 맨 아래에는
맨 처음가격(ex \1)에 대한 데이터(ex 시간: 0)가 들어있는데
그 시간을 계산 할때 5-1-0 처럼 계산. (길이는 5이고, 최종시간은 4초(5-1) 이므로)
느낀점
쉽지 않다. 성장하자. 뭐 그런 느낌ㅋ
