글 읽기 - 질문에 있는 모든 반례들을 넣어도 성립하는데 자꾸 틀렸습니다가 뜹니다

yoodori5 3년 전 0

질문검색에서 반례를 모두 찾아 입력해 보았는데도 계속 틀렸습니다가 뜹니다ㅠㅠ

onlinegdb.com이라는 사이트에서 코딩을 하는데 예제나 반례가 무리없이 모두 돌아가고 출력 값도 똑같이 나옵니다.

뭐가 문제인지 모르겠어서 미칠 것 같습니다. 도와주세요ㅠㅠ

기본원리는 3 5 2 7이라는 수가 들어오면 역순으로 출력문을 계산하고 그 값을 배열에 저장했다가 다시 출력하는 방식입니다.

우선 스택에 마지막 수인 7을 넣습니다. 출력값은 -1이 됩니다.(스택크기1)

그 전 값인 2는 7보다 작으므로 스택에 넣고 사이즈를 증가시킵니다. 출력값은 7이 됩니다.(스택크기2)

5는 2보다 크고 7보다 작으므로 스택에 저장된 2의 값을 5로 바꿔줍니다. 출력값은 7이됩니다.(스택크기2)

마지막으로 3은 5보다 작으므로 스택에 넣고 사이즈를 증가시킵니다. 출력값은 5가 됩니다.(스택크기3)

이제 저장된 출력값을 앞에서부터 출력합니다(5,7,7,-1)

이런 방식으로 풀었습니다.

#include <stdio.h>

//최대 수와 스택의 크기 1000000
int nums[1000001];
int stack[1000001];
int printnums[1000001];
int location=0;

//현재 몇번째 수를 계산하는지(now)와 어떤값인지(a)를 전달
void nge(int now,int a){
	
	for(int i=location-1;i>=0;i--){
		if(stack[i]>a){
			if(i==location-1){
                //스택에 저장된 어떤 값보다 작을 때 스택에 추가
				printnums[now]=stack[location-1];
				stack[location]=a;
				location++;
			}
			else{
                //스택에 저장된 값들 사이에 있을 때 스택값을 변경
				printnums[now]=stack[i];
				stack[i+1]=a;
			}
			break;
		}
		else{
			if(i==0){
                //스택의 어떤 수보다 클 때, -1을 넣은 뒤 스택의 마지막에 저장된 값을 a로 바꿈
				printnums[now]=-1;
				stack[i]=a;
			}
		}
	}
	
    //입력값이 없는경우 채워주기
	if(location==0){
		printnums[now]=-1;
		stack[0]=a;
		location++;
	}
	
}

int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&nums[i]);
	}
	
    //입력 끝
    
	for(int i=n-1;i>=0;i--){
		nge(i,nums[i]);
	}
    
    //n개의 수의 출력값 계산끝
	
	for(int i=0;i<n;i++){
		printf("%d ",printnums[i]);
	}
    
    //계산된 출력값 출력
}

julysky 3년 전 0

스택 구현이 이상하네요.

반례

4
3 7 5 6

정답 : 7 -1 6 -1

오답 : 5 -1 6 -1

yoodori5 3년 전 0

julysky님 감사합니다ㅠㅠ

최댓값이 오면 스택을 비운 후 최댓값만 넣고 위치를 1로 설정해야 하네요ㅠㅠ

진짜 감사드립니다!

댓글을 작성하려면 로그인해야 합니다.