congcoding

1. 문제 링크

www.acmicpc.net/problem/2751

2. 문제 설명

N개의 수를 입력받은 후, 오름차순으로 정렬하여 출력하는 문제입니다.

3. 소스코드

BOJ 2751번 수 정렬하기 2 C++ 풀이입니다.

#include <iostream>
#include <algorithm>
using namespace std;

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N;
	int arr[1000000];
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> arr[i];

	sort(arr, arr + N);
	for (int i = 0; i < N; i++)
		cout << arr[i] << '\n';

	return 0;
}

sort함수를 이용한 풀이입니다.

sort함수를 사용하기 위해서는 <algorithm> 헤더 파일을 include 해줘야 합니다.

sort함수의 사용법은 sort(시작 지점, 끝 지점) 입니다.

시작 지점을 포함하고, 끝 지점을 포함하지 않는 범위까지 오름차순으로 정렬을 해줍니다.

#include <iostream>
#include <algorithm>
using namespace std;

void quick_sort(int *arr, int start, int end)
{
	int pivot = arr[start];
	int left = start + 1;
	int right = end;

	if (start >= end)
		return;
	while (true) {
		while (left <= right && arr[left] <= pivot)
			left++;
		while (left <= right && arr[right] >= pivot)
			right--;
		if (left > right)
			break;
		swap(arr[left], arr[right]);
	}
	swap(arr[start], arr[right]);
	quick_sort(arr, start, right - 1);
	quick_sort(arr, right + 1, end);
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N;
	int arr[1000000];
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> arr[i];

	random_shuffle(arr, arr + N);
	quick_sort(arr, 0, N - 1);
	for (int i = 0; i < N; i++)
		cout << arr[i] << '\n';

	return 0;
}

퀵 정렬을 이용한 풀이입니다.

퀵 정렬의 시간 복잡도는 평균적으로 O(nlogn)이지만, 최악의 경우 O(n^2)입니다.

이 문제의 경우 O(nlogn)으로만 풀 수 있기 때문에 38번 라인을 주석 처리하면 시간 초과가 납니다.

퀵 정렬의 최악의 경우는 순서대로 정렬되어있거나, 거꾸로 정렬되어 있는 경우이므로

38번 라인에서 random_shuffle(arr, arr + N); 을 사용하여 랜덤으로 섞어서 이러한 경우를 방지했습니다.

STL의 sort함수의 경우 퀵 정렬, 힙 정렬, 삽입 정렬을 혼합해서 사용하는 인트로 정렬로 구현되어 있어 최악의 경우에도 O(nlogn) 입니다.

1. 문제 링크

www.acmicpc.net/problem/2750

2. 문제 설명

N개의 수를 입력받은 후, 오름차순으로 정렬하여 출력하는 문제입니다.

3. 소스코드

BOJ 2750번 수 정렬하기 C++ 풀이입니다.

#include <iostream>
#include <algorithm>
using namespace std;

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N;
	int arr[1000];
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> arr[i];

	sort(arr, arr + N);
	for (int i = 0; i < N; i++)
		cout << arr[i] << '\n';

	return 0;
}

sort함수를 이용한 풀이입니다.

sort함수를 사용하기 위해서는 <algorithm> 헤더 파일을 include 해줘야 합니다.

sort함수의 사용법은 sort(시작 지점, 끝 지점) 입니다.

시작 지점을 포함하고, 끝 지점을 포함하지 않는 범위까지 오름차순으로 정렬을 해줍니다.

#include <iostream>
using namespace std;

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N;
	int arr[1000];
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> arr[i];

	for (int i = 1; i < N; i++) {
		int temp = arr[i];
		int j;
		for (j = i - 1; j >= 0; j--) {
			if (arr[j] > temp)
				arr[j + 1] = arr[j];
			else
				break;
		}
		arr[j + 1] = temp;
	}
	for (int i = 0; i < N; i++)
		cout << arr[i] << '\n';

	return 0;
}

삽입 정렬을 이용한 풀이입니다.

1. var란?

2018년 3월에 출시된 Java 10부터 var를 지원합니다.

var i = 1; // int로 추론
var str = "Java"; // String으로 추론
var list = new ArrayList<String>(); // ArrayList<String>으로 추론

var는 지역변수를 선언할 때 초깃값을 통하여 데이터 타입을 추론합니다.

int var = 1; // 식별자로 사용 가능

var는 예약된 타입 이름으로 키워드가 아니기 때문에 식별자로 사용할 수 있습니다.

예제만으로는 이해하기 힘들 것 같아서 아래에 JEP 286: Local-Variable Type Inference에서 가져온 관련 내용을 덧붙입니다.

The identifier var is not a keyword; instead it is a reserved type name. This means that code that uses var as a variable, method, or package name will not be affected; code that uses var as a class or interface name will be affected (but these names are rare in practice, since they violate usual naming conventions).

2. 사용 예제

// 기존 코드
Map<String, List<String>> countryToCity = new HashMap<>();
// ...
for (Map.Entry<String, List<String>> citiesInCountry : countryToCity.entrySet()) {
  List<String> cities = citiesInCountry.getValue();
  // ...
}

// var를 사용한 코드
var countryToCity = new HashMap<String, List<String>>();
// ...
for (var citiesInCountry : countryToCity.entrySet()) { // for each문에서 사용 가능
  var cities = citiesInCountry.getValue();
  // ...
}

var를 사용하면 위와 같이 코드 양을 줄일 수 있습니다.

var는 for each문에서도 사용할 수 있으며, C++의 auto와 비슷하게 사용 가능합니다.

Object productInfo = new Object() {
        String name = "Apple";
        int total = 30;
};
System.out.println("name = " + productInfo.name + ", total = " + productInfo.total);

익명 클래스를 만드는 경우 필드를 추가할 수 있지만, 다른 곳에서 해당 필드를 참조할 수 없으므로, 위의 코드는 5번 라인에서 에러를 발생시킵니다.

하지만, 위의 코드에서 맨 처음 Object를 var로 바꾸면 익명 클래스에 선언된 필드를 사용할 수 있으므로 에러가 나지 않습니다.

3. 주의해야 할 점

public class VarDemo {
    // var a = 1; // var는 지역변수에서만 사용 가능
    public static void main(String[] args) {
        // var x = 1, y = 2; // ,와 함께 사용 불가능

        // var str = null; // null은 String에서만 사용할 수 있는 것이 아니므로 타입 추론 불가능

        // var err; // var를 사용할 때는 초기화를 바로 해야 함 (타입 추론이 불가능하므로)
        // err = 1;
        
        // var l = () -> {} // 람다식에서 사용 불가능
    }
    // void test(var x) {} // 메소드의 인수타입은 지역변수여도 var 사용 불가
}

위 예제에서 사용한 var는 모두 해당 라인 주석의 이유로 에러를 발생시킵니다.

4. 참고한 사이트