[Programmers/Level2] 뒤에 있는 큰 수 찾기 (C언어)

• 뒤에 있는 큰 수 찾기

문제 설명

정수로 이루어진 배열 numbers가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다.
정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.

---

제한사항

• 4 ≤ numbers의 길이 ≤ 1,000,000
  • 1 ≤ numbers[i] ≤ 1,000,000

---

입출력 예numbersresult

[2, 3, 3, 5]	[3, 5, 5, -1]
[9, 1, 5, 3, 6, 2]	[-1, 5, 6, 6, -1, -1]

---

입출력 예 설명

입출력 예 #1
2의 뒷 큰수는 3입니다. 첫 번째 3의 뒷 큰수는 5입니다. 두 번째 3 또한 마찬가지입니다. 5는 뒷 큰수가 없으므로 -1입니다. 위 수들을 차례대로 배열에 담으면 [3, 5, 5, -1]이 됩니다.

입출력 예 #2
9는 뒷 큰수가 없으므로 -1입니다. 1의 뒷 큰수는 5이며, 5와 3의 뒷 큰수는 6입니다. 6과 2는 뒷 큰수가 없으므로 -1입니다. 위 수들을 차례대로 배열에 담으면 [-1, 5, 6, 6, -1, -1]이 됩니다.

 

* 첫번째 제출

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

// numbers_len은 배열 numbers의 길이입니다.
int* solution(int numbers[], size_t numbers_len) {
    // return 값은 malloc 등 동적 할당을 사용해주세요. 할당 길이는 상황에 맞게 변경해주세요.
    int* answer = (int*)malloc(numbers_len);
    
    for (int i = 0; i < numbers_len; i++) {
        if(i != (numbers_len-1)){
            int for_j = i + 1;
            for (int j = for_j; j < numbers_len; j++) {
                if (numbers[i] < numbers[j]) {
                    answer[i] = numbers[j];
                    break;
                }
                if (j == (numbers_len-1)) {
                    answer[i] = -1;
                }
            }
        }
        else {
            answer[i] = -1;
        }

    }
    return answer;
}

채점 결과

정확성: 17.4

합계: 17.4 / 100.0

- 실패 (signal: aborted (core dumped))

- 실패 (signal: segmentation fault (core dumped))

이 에러들은 메모리 할당이나 포인터 접근이 잘못되서 발생하는 에러로 알고있어서, answer를 선언해준 부분이 잘못된거 같아서 제한사항을 다시 확인했다.

- 제한사항

• 4 ≤ numbers의 길이 ≤ 1,000,000
  • 1 ≤ numbers[i] ≤ 1,000,000

 

 

* 두번째 제출

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

// numbers_len은 배열 numbers의 길이입니다.
int* solution(int numbers[], size_t numbers_len) {
    // return 값은 malloc 등 동적 할당을 사용해주세요. 할당 길이는 상황에 맞게 변경해주세요.
    int* answer = (int*)malloc(1000000);
    
    for (int i = 0; i < numbers_len; i++) {
        if(i != (numbers_len-1)){
            int for_j = i + 1;
            for (int j = for_j; j < numbers_len; j++) {
                if (numbers[i] < numbers[j]) {
                    answer[i] = numbers[j];
                    break;
                }
                if (j == (numbers_len-1)) {
                    answer[i] = -1;
                }
            }
        }
        else {
            answer[i] = -1;
        }

    }
    return answer;
}

채점 결과

정확성: 60.9

합계: 60.9 / 100.0

- 실패 (signal: segmentation fault (core dumped))

* 세번째 제출

이번엔 분명 메모리 때문일거 같아서 천천히 뭘 잘못했나 생각해봤다.

int* answer = (int*)malloc(1000000);

이걸보고 한 30초 뒤 아차싶었다...

int 값인 값을 넣어줄건데 바보같이 크기를 1000000 만큼만 할당한 것이여따...

아래와 같이 고쳤더니 이제 signal: segmentation fault (core dumped) 에러는 없어졌고, 시간 초과 에러만 남았다ㅜㅜ

int* answer = (int*)malloc(sizeof(int) * 1000000);

 

채점 결과

정확성: 82.6

합계: 82.6 / 100.0