이 문제에서는 배열이 제공됩니다. 우리의 임무는 배열의 현재 요소보다 앞서는 가장 큰 요소를 반환하는 것입니다. 그렇지 않으면 -1을 인쇄합니다.
문제를 이해하기 위해 예를 들어보겠습니다.
Input: {6, 2, 7, 1, 5, 3} Output: -1, 6, -1, 7, 7, 7
이 문제를 해결하려면 배열의 앞부분에서 더 큰 요소를 확인하는 중첩 루프를 사용하는 것이 쉽고 분명한 솔루션입니다.
솔루션 구현을 보여주는 프로그램
예시
#include <iostream> using namespace std; void preceddingGreatestElement(int arr[], int n){ cout << "-1\t"; int i, j; for (i = 1; i < n; i++) { for (j = i-1; j >= 0; j--) { if (arr[i]<arr[j]) { cout<<arr[j]<< "\t"; break; } } if (j == -1) cout << "-1\t"; } } int main() { int arr[] = { 6, 2, 7, 1, 12, 5 }; int n = sizeof(arr) / sizeof(arr[0]); preceddingGreatestElement(arr, n); return 0; }
출력
-1 6 -1 7 -1 12
우리의 문제를 해결하는 더 효과적인 솔루션은 스택 데이터 구조를 사용하는 것입니다. 그리고 스택의 맨 위에 있는 앞의 더 큰 숫자를 유지합니다.
이 솔루션의 구현을 보여주는 프로그램
예시
#include <bits/stdc++.h> using namespace std; void preceddingGreatestElement(int arr[], int n) { stack<int> elements; elements.push(arr[0]); cout << "-1\t"; for (int i = 1; i < n; i++) { while (elements.empty() == false && elements.top() < arr[i]) elements.pop(); if(elements.empty()) cout<<"-1\t"; else cout<<elements.top()<<"\t"; elements.push(arr[i]); } } int main() { int arr[] = { 6, 2, 7, 1, 12, 5 }; int n = sizeof(arr) / sizeof(arr[0]); preceddingGreatestElement(arr, n); return 0; }
출력
-1 6 -1 7 -1 12