프로그래머스 택배 상자(스택)

최근 java를 공부하면서 stack, queue, list 등의 개념에 대해 처음 알았는데 마침 누가 봐도 스택을 사용할 것 같은 문제가 보여서 풀어봤다.

문제

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

#define MAX_SIZE 1000000

//스택생성
typedef struct Stack{
    int data[MAX_SIZE];
    int top;
} Stack;

//스택초기화
void initStack(Stack* stack){
    stack->top = -1;
}
    
//push
void push(Stack* stack, int value){
    stack->data[++(stack->top)] = value;
}

//맨위요소
int peek(Stack* stack){
    return stack->data[stack->top];
}

    //맨위요소제거
int pop(Stack* stack){
    return stack->data[(stack->top)--];
}

// order_len은 배열 order의 길이입니다.
int solution(int order[], size_t order_len) {
    Stack stack;
    initStack(&stack);
    int answer = 0;
    int belt = 1;
    
    for(int i = 0; i < order_len; i++){
        if(order[i] == belt){ //벨트와 order[i]가 같으면 answer도 ++ belt도 ++
            answer++;
            belt++;
        }else if(order[i] != belt){
            push(&stack, belt); //스택에 push하기, belt ++
            belt++;
        }else if(order[i] == peek(&stack)){
            pop(&stack); //스택에서 peek 빼기, 벨트는 변함 없음.
            answer++;
        }else if(order[i] != peek(&stack))
            continue; //어떤 값과도 같지 않으면 continue
    }
    
    return answer;
}

처음 작성 한 코드. stack을 사용한 문제를 처음 풀어봐서 주석을 군데 군데 열심히 넣었다.ㅎㅎ;

근데 다른 문제를 풀 때도 주석을 적극 활용해야겠다. 너무편함!

아무튼 이 코드를 사용하니,

처음 사용해 본 개념이니 그럴 수 있다.

while(i < order_len){
	if(order[i] == belt){ //order와 belt가 같을때
		answer++;
		belt++;
		i++;
	}else if(stack.top != -1 && order[i] == peek(&stack)){ //peek와 order가 같을떄
		pop(&stack);    //맨위스택제거
		answer++;
		i++;
	}else{
		push(&stack, belt); //order와 일치하지않으면 벨트에 있던거 스택에넣기
		belt++;
	}
}

for문을 while문으로 바꿨다. 기존의 코드는 belt와 order가 일치하지 않으면 그냥 스택에 넣고 넘어간 탓에 스택과 belt의 값에 오류가 있었다.

이렇게 하니까 코어 덤프 오류가 발생했다. 메모리 문제다.

while문이 무한루프가 되는 것 같다.

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

#define MAX_SIZE 1000000

//스택생성
typedef struct Stack{
    int data[MAX_SIZE];
    int top;
} Stack;

//스택초기화
void initStack(Stack* stack){
    stack->top = -1;
}
    
//push
void push(Stack* stack, int value){
    stack->data[++(stack->top)] = value;
}

//맨위요소
int peek(Stack* stack){
    return stack->data[stack->top];
}

//맨위요소제거
int pop(Stack* stack){
    return stack->data[(stack->top)--];
}

// order_len은 배열 order의 길이입니다.
int solution(int order[], size_t order_len) {
    Stack stack;
    initStack(&stack);
    int answer = 0;
    int belt = 1;       //벨트에 상자번호
    int i = 0;      //벨트길이
    while(i < order_len){
        if(order[i] == belt){ //order와 belt가 같을때
            answer++;
            belt++;
            i++;
        }else if(stack.top != -1 && order[i] == peek(&stack)){ //peek와 order가 같을떄
            pop(&stack);    //맨위스택제거
            answer++;
            i++;
        }else if(belt <= order_len){ //order와 일치하지않으면 벨트에 있던거 스택에넣기
            push(&stack, belt);         //다음 belt값과 현재의order[i]를 비교시작
            belt++;
        }else break;    // 상자번호가 order길이 넘으면 중단(맞는값이없음)
    }
    return answer;
}

order나 belt 둘 다 1부터 1씩 증가하는 자연수라 belt의 상자번호가 order_len을 넘으면 무한루프에 걸렸다.

belt>order_len일 경우 break하도록 하니 해결됐다 ~.~

따봉