[버블정렬 & 벡터] 10818번 문제

이 문제를 첨 보고 파악한 것은

• 동적 배열을 써야 할 것 같다
• 오름차순으로 정리해서 첫번째 요소, 마지막 요소를 출력하면 되겠다

그래서 코드를 비주얼스튜디오에서 짜봤는데, 돌아가지만 백준에서는 시간 초과를 했다. 💀

흠냐리...

그럼 어떻게 바꿔야지? GPT 말로는 벡터를 쓰랬다.

그래서 일단 벡터를 간단히 찾아봤다. 많이 들어봤지만 내가 많이 써보지 않았던 그 벡터..

 

벡터 간단 설명

• 배열과 유사하지만 크기가 동적인 시퀀스 컨테이너
• 즉, 런타임 중 크기가 커지거나 줄어들 수 있음
• STL(표준템플릿라이프러리)의 일부
• 임의 액세스, 자동크기 조정, 효율적인 삽입과 삭제 기능 제공
• #include <vector>

 

벡터 선언 방법

std::vector<int> vec;

 

 

벡터 요소 추가 방법

vec.push_back(10); // 마지막에 10 추가

vec.push_back(20); // 더 마지막에 20 추가

 

벡터 요소 반복문 돌리기

for(auto elem : vec)

{

   std::cout << elem << " ";

}

 

그래서 이렇게 수정해봤다. 그런데도 !! 시간 초과해서 실패했다

#include<iostream>
#include<vector>

void bubbleSort(std::vector<int>&vec);
int main()
{
	int N;
	std::cin >> N;

	std::vector<int>vec;
	for (int i = 0; i < N; i++)
	{
		int num;
		std::cin >> num;

		vec.push_back(num);
	}
	
	bubbleSort(vec);

	std::cout << vec.front() << ' ' << vec.back();

	return 0;
}
void bubbleSort(std::vector<int>& vec)
{
	for (int i = 0; i < (vec.size() - 1); i++)
	{
		for (int j = 0; j < (vec.size() - 1 - i); j++)
		{
			if (vec[j] > vec[j + 1])
			{
				int temp = vec[j];
				vec[j] = vec[j + 1];
				vec[j + 1] = temp;
			}
		}
	}
	
}

 

그래도 시간 초과를 했다...

버블정렬 말고 다른 정렬을 찾아봐야하는건가 싶어서 ...퀵정렬을 공부하고 낼 마저 풀겠다..

---

퀵정렬, 버블정렬 안 쓰고 구글 힌트를 받아서 결국 이렇게 풀었다.

어제 너무 어렵게 생각했었나보다..😂