14600. [Pro] 성적 데이터베이스

학생과 팀과 시험점수가 있다.

 

학생은 mID , mTeam , m

학생은 10만명

팀은 5팀

시험점수는 1~5까지

API 는 다음과 같다.

- 학생을 넣고  ( 최대 10만회 호출)

- 학생을 뺴고  ( 최대 10만회 호출)

- 학생의 점수를 업데이트하고  ( 최대 10만회 호출)

- 특정팀의 모든 학생 점수를 업데이트하고 ( 최대 10만회 호출)

- 특정팀의 1등 점수 ( 동일점수라면 id 값으로 비교)를 구하는 api 가 있다. ( 해당 API 는 최대 100회 호출)

 

학생을 넣거나 빼거나 특정학생의 점수를 업데이트하는것은 쉬우므로 나중에 생각하자.

특정팀의 1등 점수구하는것은 100회 호출이므로 그냥 전수조사 해도 된다.

특정 팀의 모든 학생 점수를 업데이트 하는것을 생각해야한다. 

 

이때 우리가 사용하지 않은 조건인 팀의 갯수와 시험점수를 보자

이렇게 작은 것은 인덱스로 사용해볼 수 있을것이다.

 

우리는 각팀별+각 점수별 학생들을 리스트화 할것이다.

 

이때 어떤 자료구조를 사용할까? 

 

우리가 생각해봐야 하는 특정 팀의 점수를 업데이트 하는것이 있다. 5점이 넘으면 모두 n번쨰 팀의 5점으로 합쳐져야 한다.

1점 아래도 마찬가지.  이말은 리스트들을 합치기에 빠른 자료구조를 찾아야한다.

링크드 리스트는 딱 이경우에만 좋은 자료구조이다. ( 다른 경우에는 최악의 자료구조 vector와 배열에 비해서 )

 

 

학생접근을 빠르게 하기위해서

학생 배열 ( mID를 인덱스로 하는)을 만들것이다.

이 학생하나하나는 링크드 리스트의 노드가 될 것이므로 prev,next 도 들어갈 것이다.

노드에는 erase() 함수를 만들어서 좌우 노드를 연결함으로써 삭제되는 기능을 만들 것이다.

 

그리고 학생노드들이 모여있는 Team[5개팀][5개점수] 변수도 만들 것이다. 

 

 

struct Node{

 int mID;

 team mTeam;

 Node* prev;

 Node* next;

 auto erase(){

   prev.next = next

   next.prev = prev

 }

}

std::array<Node,MAX> nodes;

std::array<std::array<LinkedList,5>,5>> teams;

Class LinkedList{

 Node head,tail; // 보통 head와 tail 을 만들어서 시작한다.

 public:

  LinkedList () = dafault;

  init() {

   head.next = &tail;

   tail.prev =  &head;

  }

  isEmpty(){

    return head.next == &tail

  }

  add(Node node){

    tail.prev.next = node;

    node.next = &tail;

    node.prev= tail.prev;

    tail.prev= &node;

  }

  pop(mID){

    nodes[mID].erase();

  }

  teamUpdate(mTeam, mScore){

 

  }

 

}