[HackerRank] Stacks > Maximum Element

https://www.hackerrank.com/challenges/maximum-element/problem

스택 구현

1 x : x를 스택에 삽입

2 : top을 삭제

3 : 스택 중 max 값 출력

 

각 변수의 범위에 주의했다. 

1 <= n <= 10^5

1 <= x <= 10^9

int stack[100000] = {0};
int top = -1;
int max=0, max_idx=0;

void push(int data){
    stack[++top] = data;
    if(top==0){
        max=stack[top];
        max_idx=top;
    }
    else{
        if(max<stack[top]){
            max=stack[top];
            max_idx=top;
        }
    }
}

void pop(){
    flag = 0;
    if(top == max_idx){
        max=stack[0];
        max_idx=0;
        for(int i=0; i<top; i++){
            if(max < stack[i]){
                max = stack[i];
                max_idx = i;
            }
        }
    }
    stack[top--] = 0;
}

int* getMax(int operations_count, char** operations, int* result_count) {
    int idx = 0, check = 0;
    for(int i=0; i<operations_count; i++){
        if(operations[i][0] == '3') check++;
    }
    *result_count = check;
    int *arr = (int*)malloc(sizeof(int)*check);
    for(int i=0; i<operations_count; i++){
        if(operations[i][0] == '1'){
            //push x
            char s[11] = {0};
            for(int j=2; operations[i][j]!='\0'; j++){
                s[j-2] = operations[i][j];
            }
            push(atoi(s));
        }else if(operations[i][0] == '2'){
            //delete top
            pop();
        }else{
            // print max
            arr[idx++] = max;
        }
    }
    return arr;
}

10^5 범위의 스택을 만들고 max를 저장할 변수를 전역변수로 선언했다. 

 

getMax()

operations[n][0] 부분에 1 2 3 선택지가 들어오기 때문에 if문으로 각 선택지일 때를 나눠줬다.

1에서는 push함수를 이용해 값을 삽입하는데, 이 문자열의 뒷부분을 숫자로 바꾸는 데 고민을 좀 했다. 최대 10자리 숫자까지 들어갈 수 있으므로 11짜리 문자열을 생성해 숫자부분 문자열만 저장해, atoi함수로 정수화시켰다. (atoi함수가 첫번째 토큰만 정수로 변환할 수 있는 것 같아 이 방법을 사용했다. 다른 방법이 있는지 찾아볼 것.)

그리고 문자열을 매번 초기화해줘야 되는데 for문을 돌리는 게 또 시간초과에 기여할 거 같아 그냥 매번 선언해주는 걸로 했다. 이것도 문제가 될 수 있는데 다른 방법을 모색해보자.

 

2에서는 pop함수를 사용해 top에 있는 값을 빼줬다.

 

3에서는 이 max값을 저장할 arr배열에 전역변수인 max를 저장하고 있다. 

여기서 getMax함수의 윗부분을 보면 for문이 있는데, 이것은 arr의 배열 크기를 정하기 위해 사용했다. arr의 배열 크기를 operations_count로 정하니까 빈 자리의 0이 다 출력돼 정확히 선택지 3만 들어간 경우를 세줘야 했다. 좀 비효율적이지만 for문을 한바퀴 돌려 3의 개수를 세주고 그 값을 count변수에 저장해 arr의 배열 크기를 정해줬다. idx는 arr의 인덱스다. if문에서 3이 들어올 때마다 하나씩 증가시켰다.

 

push()

n범위가 100000인데 max값을 찾기위해 매번 for문을 돌리는 게 역시나 시간초과가 나서 어떻게 하면 max값을 간단하게 구할 수 있을까 고민했다. 그래서 우선 처음 들어온 값은 max로 두고, 새로운 값이 들어올 때마다 max값과 비교해 max값을 정해줬다. 이 부분은 친구의 도움을 좀 받았다.

 

pop()

들어올 때 뿐만 아니라 max값이 삭제될 때도 생각해줘야 한다. max_idx에 max의 인덱스값을 저장해 삭제되는 부분이 max_idx면 남아 있는 값들로 for문을 돌려 max를 정한다. 그 다음에 stack[top]을 삭제한다. 

지금 생각해보니까 max값이 같은 경우는 없나 보다. push 함수의 (max < stack[top]) 비교하는 부분에서 등호를 안넣기 때문에 max값이 같으면 새로운 인덱스로 안바뀌는데, max값이 여러개가 아니라면 max_idx가 굳이 없어도 될 것 같다. max값과 비교하면 되니까.

 

 

 

---

고민과정

 

int stack[100000] = {0};	//크기 주의
int top = -1;
int max=0, max_idx=0;	//max_idx로 시간초과 해결방안 모색함
void push(int data){
    stack[++top] = data;
}
void pop(){
    stack[top--] = 0;
}
int print(){	//끝까지 도는 게 비효율적
    if(top<=2){	//굳이 2까지 돌릴 필요?
        for(int i=0; i<=top; i++){
            if(max < stack[i]){
                max = stack[i];
                max_idx = i;
            }
        }
    }else{	//max가 남아 있을 경우 새로 들어온 값과 max값 비교
        if(max_idx <= top){
            for(int i=max_idx; i<=top; i++){
                if(max < stack[i]){
                    max = stack[i];
                }
            }
        }else{	//max가 삭제 됐을 경우 다시 max값을 찾음
            for(int i=0; i<=top; i++){
                if(max < stack[i]){
                    max = stack[i];
                }
            }
        }
    }
    return max;
}

int* getMax(int operations_count, char** operations, int* result_count) {
    int idx = 0, check = 0;
    //char s[11] = {0};
    for(int i=0; i<operations_count; i++){
        if(operations[i][0] == '3') check++;
    }
    *result_count = check;
    int *arr = (int*)malloc(sizeof(int)*check);
    for(int i=0; i<operations_count; i++){
        if(operations[i][0] == '1'){
            //push x
            char s[11] = {0};	//매번 초기화해주는 방법이 이것밖에 없었음 [0]초기화가 안통해서
            for(int j=2; operations[i][j]!='\0'; j++){	//조건 주의
                s[j-2] = operations[i][j];
            }
            push(atoi(s));	//문자열 숫자로 변환
        }else if(operations[i][0] == '2'){
            //delete top
            pop();
        }else{
            // print max
            arr[idx++] = max;	
            //printf("%d %d\n", arr[0], arr[1]);
        }
    }
    return arr;	
}

처음에는 print함수로 max값을 구했기 때문에 여기서 max값을 다 해결하려다 보니 오히려 비효율적이게 됐는데, push함수와 pop함수로 바로바로 max값을 가리는 게 더 효율적이었다. 만약에 print문을 썼다면 push함수와 pop함수가 사용될 때 같이 불러서 max값을 구해야 했을 것이다. 그리고 for문와 while문 조건을 항상 헷갈리는데 주의하자.