ohjtgood- Tutorial: STL Sort 1 > 문제은행 : 정보올림피아드&알고리즘



4523 : Tutorial: STL Sort 1

제한시간
1000 ms   
메모리제한
256 MB   
해결횟수
59 회   
시도횟수
97 회   

문제

우리는 지금까지 여러가지 정렬법을 배워왔다.

정렬법에는 선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬, 합병 정렬 등이 있다.

하지만 배열을 정렬할 필요가 생길 때마다 위의 방법을 손으로 구현하는 것은 지루한 작업일 뿐더러, 실수할 확률도 높아진다.

 

여러분들의 코딩능력 향상을 위해 지금까지는 숨겨왔지만,

사실 C++에는 크기 비교가 가능한 형식으로 선언된 배열을 정렬해주는 친절한 함수가 존재한다. 바로 sort()함수이다.

 

여기에서 크기 비교가 가능한 형식은 int나 double처럼 부등호를 사용하여 대소판별이 가능한 자료형을 뜻한다.

간단하게 예를 들자면, 3<5는 1(참) 이라는 결과값이 명확하게 나오므로, int형식은 대소판별이 가능한 자료형이다.

 

이 문제에서는 간단하게 sort()함수의 사용법을 알아보도록 하자.

 

사용방법 예시 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
#include <algorithm>  // ⓐ
using namespace std// ⓐ
 
int main()
{
    int i;
    int arr[8= {1,9,9,4,1,1,0,8};
 
    sort(arr+0,arr+8); // ⓑ
 
    for(i = 0 ; i < 8 ; i++) {
        printf("%d ", arr[i]);
    }
 
    return 0;
}
 
cs

실행결과

0 1 1 1 4 8 9 9

 

예시 코드에서

ⓐ로 표시된 두 문장은 sort() 함수를 쓰기 위해 필요한 헤더파일 선언이다. <stdio.h>를 처음 배울 때 처럼, "아 그렇구나" 하면 되는 부분이다.

ⓑ로 표시된 sort()함수를 잘 보면 생소한 형식으로 써 있다는걸 알 수 있다. 사용법은 구체적으로 다음과 같다. 

 

 sort(배열이름 + 시작위치, 배열이름 + 끝위치);​

 

여기에서 시작위치(arr[0])에는 자료가 저장되어 있지만,

끝위치(arr[8])에는 자료가 없다는 것에 주의하라. 

즉, sort 함수의 가동범위는 인덱스 0부터 7까지가 된다.

 

정리하자면, 이 경우에 sort 함수는 arr이라는 배열의 0번부터 7번까지의 원소를 오름차순으로 정렬한다.

(당연하겠지만, arr+0의 경우 +0을 생략하고, arr만 써도 상관 없다: sort(arr,arr+8); )

 

이제 아래 문제를 읽고 풀어보자

 

크기가 N인 배열을 입력받아서

 

1. 특정 구간을 정렬한 후, 출력하고, 

2. 다시 전체를 정렬한 후 출력하는 프로그램을 작성하시오.

 


입력형식

첫째 줄에 배열의 크기인 N이 주어진다.

둘째 줄에 배열의 원소들인 a0, a1, ... aN-1이 공백을 사이에 두고 주어진다. 

셋째 줄에 s e가 주어진다. 이는 첫 번째 정렬에서는 배열의 원소 중 인덱스가 s이상 e이하인 원소들만 정렬하라는 뜻이다. (e미만이 아님에 주의한다.)

즉 as, as+1,...ae-1,ae만을 정렬한다.

 

제약사항

 

3≤​N≤100,000 , 0≤​s≤​e<N, 0≤​ai≤​109


출력형식

첫째 줄엔 인덱스가 s이상 e이하인 원소들만 오름차순으로 정렬한 결과를 출력한다.

둘째 줄에 배열 전체를 오름차순 정렬한 결과를 출력한다.

 

반드시 방금 배운 sort()함수를 사용하도록 한다.


입력 예

8
1 9 9 4 1 1 0 8
3 6

출력 예

1 9 9 0 1 1 4 8
0 1 1 1 4 8 9 9

출처

ohjtgood

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP