[백준 / BOJ] 1083 소트

문제

출처 : www.acmicpc.net/problem/1083

1083번: 소트

N크기의 정수배열과 S가 주어졌을때, 정수들의 순서를 최대 S번 바꿔서 사전순으로 가장 뒤에있는 것을 출력하는 문제다.

 

예를들어, 

5

10 20 30 40 50

5

는 

50 20 10 30 40 이 출력되어야한다.

 

풀이

그리디로 풀리는 문제였다.

 

사전순으로 가장 뒤에있는단어는 

1. 앞에있는 단어가 뒤에있는 단어보다 클수록 사전순으로 앞선다.

이런 조건이있다.

따라서, 현재 위치에서 S번 뒤로 갔을때 가장 큰 단어를 찾아서 현재위치로 이동시켜주고 나머지 단어들을 뒤로 밀어주면된다.

 

1. 현재위치에서 S번째 뒤에있는 단어까지 보면서 가장 큰 단어를 찾는다.

2. 가장 큰 단어를 현재위치에 집어넣고 (뒤에있는 단어들을 전부 밀어넣는다.)

 

구조체로 링크드 리스트로 구현해서 바로 집어넣을려다가 그냥 매 탐색마다 temp배열 선언, 초기화 하면서 주 배열(deq) 업데이트 해줘도 시간초과 안날거 같아서 걍짯음

 

시간복잡도

O(N^3)

링크드리스트 구현해서 사용시

최악의 경우 : 51 * 25

 

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1038%20%EC%86%8C%ED%8A%B8/main.cpp

devxb/JJUNalgo