2024 - 08- 12 C++ 코딩테스트 10주완성 D+31

백준 17298 문제 - 오큰수

 

크기가 N인 수열 A = A(1), A(2), ..., A(N)이 있다.

 

수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다.

 

A(i)의 오큰수는 오른쪽에 있으면서 A(i)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다.

 

그러한 수가 없는 경우에 오큰수는 -1이다.

 

예를 들어,

 

A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다.

 

A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

 

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.
둘째 줄에 수열 A의 원소 A(1), A(2), ..., A(N) (1 ≤ A(i) ≤ 1,000,000)이 주어진다.

 

출력

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

 

실습코드

 

#include <bits/stdc++.h>

using namespace std;

//1.변수 목록
//입력받을 정수형 배열 a[1000004]
//입력받을 정수형 수열의 크기 n
//오큰수를 저장할 정수형 배열 nge[1000004]
int a[1000004],nge[1000004];
int n;

int main()
{
	//2. 알고리즘
	//2-1 수열의 크기 n을 입력받는다.
	//2-2 수열의 크기만큼 반복문
	//2-2-1 값을 입력받아 a에 저장한다.
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	//2-1 반복문종료
	//2-3 반복문 0 ~ n 만큼 반복
	//2-3-1 반복문 i 부터 n까지 반복
	//2-3-1-1 만약 a[i] < a[j] 이면
	//2-3-1-1-1 nge[i] 안에 a[j]를 넣고
	//2-3-1-1-2 반복문을 멈춘다.
	for (int i = 0; i < n; i++)
	{
		for (int j = i; j < n; j++)
		{
			if (a[i] < a[j])
			{
				nge[i] = a[j];
				break;
			}
			else
				nge[i] = -1;
		}
	}
	//2-3 반복문 종료
	//2-4 반복문 0~n 만큼 반복
	//2-4-1 nge[i] 의 값을 출력하고 " " 공백공간도 출력
	for (int i = 0; i < n; i++)
	{
		cout << nge[i] << " ";
	}
}

 

문제 자체는 생각보다 쉽다.

 

배열의 크기를 입력받고, 그 크기만큼 배열의 값을 입력받고 난 다음

 

반복문 0 부터 n 까지 돌려서 그 안에 또 다른 반복문을 선언하여 배열의 위치 i 마다 i 부터 ~ n 까지 반복문을 돌려

 

a[i] < a[j] 가 크면 nge[i] 안에 값을 넣어주면 된다.

 

하지만 크나큰 문제가 하나 있다....

 

바로 n의 조건 n은 1,000,000 까지 받을 수 있는데 이 알고리즘으로 최댓값을 받을 시

 

시간복잡도는 1,000,000 x 1,000,000 으로 1,000,000,000,000 이 되게 된다..

 

엄청난 시간복잡도떄문에 시간초과가 뜨게 되어 효율적인 코드로 재구성해야하지만..!! 생각이 나질 않는다..

 

강의 코드를 보자.. ㅠ

 

강의실습코드

 

#include <bits/stdc++.h>
using namespace std;
int n, a[1000004], ret[1000004];
stack<int> s;
int main() {
	cin >> n;
	memset(ret, -1, sizeof(ret));
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		while (s.size() && a[s.top()] < a[i]) {
			ret[s.top()] = a[i]; s.pop();
		}
		s.push(i);
	}
	for (int i = 0; i < n; i++) cout << ret[i] << " ";
}

 

상대적 박탈감이 심하게 느껴지는 코드이다.. ㅠㅠ

 

너무 간단명료하게 잘 짰잖아... 

 

a[i] 를 입력받을 때마다 그 전 인덱스에 있는 수(s.top()) 와 비교하여 a[i] 가 더 클 경우 ret[s.top()] 안에 a[i] 를 대입하고,

 

s.top 위치에 해당하는 인덱스는 오큰수값을 만족했기떄문에 스택에서 pop 시켜준다.

 

이렇게 하면 반복문을 한번 더 돌릴 필요없고,

 

또 한번 반복문이 돌때마다 여러개의 인덱스에 값을 대입하는 경우도 생겨

 

시간복잡도가 현저히 줄어들게 된다..!!

 

짝짓기의 경우에는 스택.. 머리에 기억을 철저히 해두어야 겠다

 

---

 

완전 탐색 

 

brute force, exhaustive key search 라고도 하며, 모든 경우의 수를 탐색하는 알고리즘입니다.
이때 경우의 수라는 것은 순열 또는 조합을 의미하며 여기에다가 어떤 로직을 추가하는 것입니다.

 

로직이라는 것은 각 경우에 따라 반복문, 재귀함수 등을 활용할때가 있는데

먼저 반복문을 활용한 완전탐색부터 실습해보겠습니다

 

 

반복문을 활용한 완전 탐색

 

실습문제

 

트위치 랄로는 "2400" 이라는 숫자를 좋아한다.
그래서 파카는 2400이라는 숫자를 포함한 숫자들을 순서대로 읽고 싶어한다.
2400을 포함한 숫자를 파카수라고 하는데,
이때 n 이라는 정수형 변수가 주어지고 입력받아서, n번째 파카수를 구하여라

실습코드

 

#include <bits/stdc++.h>

using namespace std;

int n,cnt;
const int INF = 1000000;

int main()
{
	cin >> n;

	for (int i = 2400; i < INF; i++)
	{
		string a = to_string(i);
		if (a.find("2400") != string::npos)
		{
			cnt++;
			if (cnt == n)
			{
				cout << a;
				break;
			}			
		}
	}
}

 

먼저 n번째 수를 구하기 위해 정수형 변수 n을 입력받은 다음

 

2400 부터 순차적으로 반복문을 돌려 2400이 포함된 문자열일 경우 cnt를 매겨주어

 

cnt 와 n이 똑같을 경우 n번째 파카수이기때문에 출력시켜줍니다.

 

---

 

 

재귀함수를 활용한 완전 탐색

 

보통은 반복문을 이용한 완전탐색이 재귀함수를 호출하는 비용에 비해 훨씬 더 적게 들어가므로

 

반복문을 이용하는 것을 권장합니다.

 

하지만 반복문으로 안 될 거같다?

 

너무 복잡하거나 어떠한 행위는 반복하는데 매개변수만 수정해서 넘기면 될 거 같다?

 

라고 생각이 들면 재귀함수로 하는게 좋습니다.

 

실습문제

 

사용자가 입력하는 배열이 주어지고 이 배열안에서 원소끼리 더하여서 소수가 나오는 경우의 수의 개수를 구하여라

 

입력

첫번째 줄에 배열의 개수를 입력받는다.
두번째 줄에 각각 배열의 값을 입력받는다.

 

출력

 

소수가 나오는 경우의 수의 개수를 출력

 

실습코드

 

#include<bits/stdc++.h>
using namespace std; 
int n, temp;
vector<int> v;  
bool check(int n) { 
    if(n <= 1) return 0;
    if(n == 2) return 1; 
    if(n % 2 == 0) return 0;
    for (int i = 3; i * i <= n; i++) {
        if (n % i == 0) return 0;
    }
    return 1;
}
int go(int idx, int sum){
	if(idx == n){
		//cout << "SUM " << sum << "\n";
		return check(sum); 
	}
	return go(idx + 1, sum + v[idx]) + go(idx + 1, sum);
}
int main() {
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> temp;
		v.push_back(temp);
	}
	cout << go(0, 0) << "\n"; 
	return 0; 
}

 

재귀함수 go에서 bool형 함수 check 를 이용하여 소수인지 아닌지 판별을 해주고, 

 

재호출하는 재귀함수의 매개변수 sum의 값을 차별을 두어 idx 번호가 0일때, 나머지 값들의 총합과

 

나머지 idx 번호별로 순차적으로 총합을 구해서 비교할 수 있다.