[Algorithm] 2주차 스터디 - 정렬 (백준 2751, 10825, 11582)

문제(2751: 수 정렬하기 2)

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

 첫째 줄에 수의 개수 N이 주어지고, 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이를 오름차순으로 정렬하는 프로그램을 작성하라.

 

풀이

입력할 숫자의 개수인 N을 int(input())으로 입력을 받고, list 변수에 N개만큼의 숫자를 입력받아 저장한 후, sorted 메소드로 정렬을 하여 그 결과값을 출력하고자 하였다. N개의 숫자를 입력받을 때도 int(input()) 함수를 사용하였으나 타임 아웃이 떴다. python에서는 input()으로 입력하는 것보다 sys를 import 받아 std 입출력을 사용하는 것이 시간을 단축할 수 있다는 것을 알게 되었다.

 

정렬은 이중 for문을 사용하여 버블 정렬을 이용할 수도 있었으나, python에서는 sort와 sorted가 미리 정의되어 있기 때문에 코드 길이의 단축과 편의를 위하여 sorted 메소드를 이용하여 리스트 변수를 정렬하였다.

 

문제(10825: 국영수)

https://www.acmicpc.net/problem/10825

10825번: 국영수

첫째 줄에 도현이네 반의 학생의 수가 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 이때, 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 작성하시오.

1. 국어 점수가 감소하는 순서
2. 국어 점수가 같으면 영어 점수가 증가하는 순서로
3. 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로
4. 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키코드에서 대문자는 소문자보다 작으므로 사전 순으로 앞에 옴)

풀이

같은 코드라면 짧은 것이 유용할 것이라고 생각하여 학생들의 이름, 국어, 영어, 수학을 리스트에 바로 입력을 받아보고 싶었다.

std입출력을 이용하되 split()을 사용하여 띄어쓰기 기준으로 리스트에 입력하였고, for _ in range(N)을 통해 해당 과정을 N번 반복하였다.

 

정렬을 위해서는 sort 메소드를 사용하였는데, 이때 lambda 함수를 이용하여 첫번째 정렬 기준은 1번 인덱스(국어 점수)를 내림차순 기준(-)으로, 해당 기준으로 구분이 불가능할 경우(값이 같을 경우) 사용할 두 번째 기준은 2번 인덱스(영어 점수)를 오름차순 기준으로, 세 번째 기준은 3번 인덱스(수학 점수)를 내림차순 기준(-)으로, 마지막 네 번째 기준은 0번 인덱스(이름)를 오름차순 기준으로 설정하였다.

 

문제(11582: 치킨 TOP N)

https://www.acmicpc.net/problem/11582

11582번: 치킨 TOP N

치킨집이 N개 있다고 가정을 하자. N개의 치킨의 수치를 무작위로 놓은 뒤 N/2명의 C.T.P 회원이 차례대로 2개의 치킨집을 선택해  정렬을 한다. 그 뒤 N/4명이 차례대로 바로 전 단계의 사람이 정렬한 두 개의 그룹을 차례대로 선택하여 치킨집을 정렬을 한다. 계속해서 N/8명, N/16명이 정렬을 진행하다가 마지막 사람이 두 개의 정렬된 그룹을 합병하여 작업을 완료한다. 현재 단계에서 k명의 회원이 정렬을 진행할 때 정렬을 마친 뒤 결과를 출력해라.

 

풀이

python을 이용하여 알고리즘 문제를 풀고 싶었으나, 계속 에러가 떠서 c++로 작성을 하였다. 위 문제를 본 순간 merge sort를 이용하는 것이라는 생각이 들었다. 하지만 merge sort의 중간 결과값을 출력한다는 말이 한참을 고민하게 만들었던 것 같다. left list와 right list로 나뉜 후 left list부터 정렬을 시작하기 때문에, 인원 조건을 만족하였을 때 출력을 바로 시키면 left 부분은 정렬이 된 상태로 출력이 되었으나 right 부분은 정렬이 되지 않은 상태로 출력되는 것이 초반의 내 코드에서 발생한 가장 큰 문제였다.

 

해결 방법은 현재 정렬중인 리스트의 크기를 기준으로 생각하는 것이었다. 왼쪽 리스트의 pivot과 오른쪽 리스트의 pivot의 차이 (e-s)가 현재 정렬 중인 리스트의 크기이기 때문에 리스트의 크기가 전체 리스트의 크기 (n)에서 현재 정렬중인 사람(limit)의 수로 나눈 수 보다 커지면 return으로 정렬을 종료하고 결과를 출력하게 하는 것이다.