안녕하세요. Softeer 운영 담당자 입니다.

지난 12월 6일에 Softeer 5회 정기 인증평가가 실시되었습니다.

이번 역량 진단에도 많은 분들께서 관심을 가지고 참여하여 주셨습니다.

인증을 받으신 분들께는 축하의 말씀을 전하고, 아깝게 떨어지신 분들께는 안타까운 마음을 전합니다.

금번 평가문제는 연습문제를 통해 확인하실 수 있으며, 문제 해설과 풀이 방법을 공유하오니 역량을 키우시는 데 조금이나마 도움이 되셨으면 좋겠습니다.

향후 정기 인증평가 문제도 연습문제와 문제해설을 업로드 할 계획이니, 많은 관심을 가지고 인증평가에 참여해주시면 감사하겠습니다.

1번 문제

성적 평가

풀이 권장 시간: 70분

문제의 설명대로 참가자들의 각 3개의 대회 별 등수와 최종 등수들을 출력하면 됩니다.

[1] 각 대회 별 참가자들의 등수 계산

대회는 총 3번 진행됩니다. 각 대회의 결과들을 잠시 저장하는 임시 배열 temp[]를 만들어 입력값들을 받아 줍니다.

입력값들을 받아줄 때 참가자들의 등수를 간편하게 출력하기 위해서는, 참가자들의 점수와 참가자 번호를 동시에 저장할 수 있게 

pair 자료구조를 사용하거나 객체를 직접 만들어 받아 줍니다. Pair<score, index>

이를 점수 순으로 정렬한 뒤 등수를 구해 줍시다. 직전 사람보다 점수가 낮으면 직전 사람의 등수에 1을 더한 것이 다음 사람의 등수입니다.

단, 동점자를 잘 고려해야 됩니다. 직전 사람과 점수가 같으면 같은 등수를 부여합니다.

최대 20만명이 참여할 수 있으므로, 시간 복잡도를 고려해야 됩니다. 효과적인 정렬 알고리즘이나 라이브러리를 사용하여 구현하면

총 O(NlogN)의 시간복잡도로 문제를 해결할 수 있습니다.

[2] 최종 등수 계산

[1]에서 입력을 받아 등수를 3번 계산하는 동안, 최종 결과를 저장하는 다른 배열 result[]을 따로 만들어 입력된 값들을 동시에 더해 줍니다.

마지막으로, 3번의 대회 결과를 모두 더한 결과 result[]을 정렬하여 등수를 구하면 문제를 해결할 수 있습니다.

2번 문제

업무 처리

풀이 권장 시간: 70분

말단 직원들의 업무 번호가 주어졌을 때, R일이 지난 후 부서장까지 최종 처리된 일들의 번호 합을 구하는 문제입니다.

완전 이진트리 라는 업무 조직의 특징을 잘 파악해야 됩니다.

[1] 트리 설계

업무 조직은 완전 이진트리 모양입니다. 높이가 H일 경우 문제의 모든 직원 수는 2H+1-1, 말단 직원들 수는 2H명입니다.

업무는 받은 순서대로 진행되므로 Queue 자료구조를 사용하면 됩니다.

트리 구조를 설계할 때는, 홀수 / 짝수 날짜를 고려해야 됨을 주의해야 됩니다.

말단 직원들은 홀수 / 짝수 관계없이 일을 처리해서 상사한테 올리기 때문에 Queue_tail[2H]를 만들어 입력값을 저장 합니다.

말단 이외의 직원들은 홀수 / 짝수 날짜마다 처리해야 되는 일들이 달라지기 때문에 

Queue[2H][2]을 만들어 놓습니다. (인덱스 범위 1 ~ 2^H) (0: 짝수, 1: 홀수 날짜)

이렇게 배열을 만들었을 때, 완전 이진트리에서 루트 노드를 제외한 노드의 index / 2가 부모 노드의 index라는 정보를 잘 활용하면 됩니다. 

[2] R일만큼 업무 진행

"업무를 올리는 것은 모두 동시에 진행되고, 그날 올린 업무를 상사가 처리하는 것은 그 다음날에야 가능하다" 라는 문제 설명에서

일일 업무는 top - down 방식으로 계산하면 편리하다는 것을 알 수 있습니다.

일일 업무는 다음 순서대로 구현하면 됩니다.

1. 날짜가 홀수인지 짝수인지 체크 - check

2. 부서장의 업무 처리

 - 홀수 / 짝수 날짜에 맞는 업무를 처리할 수 있을 경우, Queue[1][check]에서 업무를 하나 꺼내 result에 더해 줍니다.

3. 중간 급 직원들의 업무

 - 홀수 / 짝수 날짜에 맞는 업무를 처리할 수 있을 경우, 높은 순부터 차례대로 Queue[index][check]에서 업무를 하나 꺼냅니다.

   이를 index / 2인 부모 노드에 왼쪽, 오른쪽 직원을 고려하여 추가해 줍니다.

4. 말단 급 직원들의 업무

 - 처리해야 되는 업무가 남아 있을 경우, Queue_tail[index]에서 업무를 하나 꺼내 부모 노드에 추가해 줍시다.

일일 업무를 R번 반복하면 정답을 구할 수 있습니다.