링크

코드트리 채점기

난이도

  • 플래티넘5
    • 우선순위큐와 해쉬셋, 해쉬맵을 어떻게 구성할지가 중요한 포인트
    • 매우 어려움
    • 어떻게 자료구조를 정리하는지가 중요하다.

문제요약

  • 전체 5개의 함수를 구현해야 한다.
    • 채점기 준비
      • 대기큐에 시간0,우선순위1, url을 추가
    • 채점 요청
      • 대기큐로 문제(시간,우선순위,url)를 추가
      • 조건
        • 대기큐에 url이 같은게 있으면 넘기기
    • 채점 시도
      • 대기큐에서 우선순위 제일 높은 문제를 채점 시작
      • 조건
        • 우선순위는 문제의 작은 우선순우, 먼저온 시간 순
          • 우선순위가 높더라도 같은 도메인이 채점중이면 넘기기
          • 우선순위가 높더라도 채점했던 도메인의 start+3*gap보다 요청 시간이 작으면 넘기기
        • 쉬는 채점기 없으면 넘기기
        • 조건에 맞는 문제가 없으면 넘기기
    • 채점 종료
      • 채점기가 채점중인 문제를 종료시킨다.
    • 채점 대기 큐 조회
      • 대기큐에 있는 채점의 수 출력

접근

  • 가장 중요한것은 어떤 자료구조를 만들지이다.
  • 무엇을 만들어야 할지 정리하자.
    • 문제, 대기큐, 채점기, 채점내역
  • 문제
    • 기본 시간, url, 우선순위
    • url에서 도메인, 채점시작시간, 채점종료시간
  • 대기큐
    • 우선순위별로 정렬
      • 우선순위,시간순
    • 대기중인 문제들의 url을 검색 가능
    • 현재 대기중인 갯수확인
  • 채점기
    • 쉬는 채점기 확인
    • 채점중인 도메인
    • 채점중인지 확인
  • 채점내역
    • 도메인별로 시작시간, gap시간을 저장

간단 알고리즘

  • 먼저 각 자료구조를 만든다.
  • 문제는 class로 만들어서 정보들을 다 가지고 시작
    • 이 문제는 대기큐에 입장부터 시작해, 채점내역때까지 사용한다.
  • 대기큐
    • hashmap[도메인명,우선순위큐] 형태로 만든다. - 이게 제일 핵심
    • 대기중인 문제 확인용 hashset[url] 하나 만든다.
    • 대기중인 갯수용 int를 하나 만든다.
  • 채점기
    • 쉬는 채점기 바로 확인하게 우선순위큐를 하나 선언해서 관리
    • 채점중인 도메인 확인용 hashset[도메인명] 만든다.
    • 채점기는 배열 형태로 관리한다.
      • 채점여부boolean과 채점중인 문제를 가진 class로 배열을 만들기
  • 채점내역
    • hashmap[도메인명,문제]로 채점내역관리
  • 함수:채점기 준비 (N채점기갯수,url)
    • 위에서 만든 자료구조 초기화
    • 시간0, 우선순위1, 받은 url을 채점요청함수를 이용해 대기큐에 넣는다.
  • 함수:채점요청 (t요청시간,p우선순위p,url)
    • url을 대기중인 문제 확인용 hashset으로 확인, 있으면 넘기기
    • t,p,url로 문제class를 만들기
    • 대기hashmap에서[도메인]으로 찾은 우선순위큐에 문제를 넣는다
    • 대기중인 갯수+1해준다.
  • 함수:채점 시도(t채점시작시간)
    • 먼저 쉬고있는 채점기 확인
      • 채점우선순위큐가 비어있으면 넘기기
    • 채점해야하는 문제를 찾는다.
      • 대기hashmap의 key인 도메인들을 전부 탐색
        • 채점중인도메인 확인 hashset에 있으면 넘기기
        • 채점내역hashset에서 도메인 검색후, 시작시간과 종료 시간확인후 조건에 안맞으면 넘기기
        • 위의 조건들을 넘긴 도메인의 우선순위큐의 앞을peek해서 확인
          • 제일 우선순위 높은 문제class를 찾는다.
    • 전체 도메인 탐색 후 찾은 문제 class 확인
      • 문제가 없으면 채점 시도 종료
      • 대기hashmap에서 이 문제의 도메인으로 검색한 우선순위큐에서 poll을 진행
    • 채점우선순위큐에서 poll하여 채점기 번호 발급
    • 채점확인 hashet에 추가
    • 채점기에 채점번호에 채점중 표시, 문제를 시작시간 추가해서 넣는다.
    • 대기중인 갯수-1
  • 함수: 채점 종료(t 종료시간,jid채점기번호)
    • 해당 채점기 채점중이 아니면 종료
    • 채점기에 채점중 표시false, 문제에 종료 시작 추가
    • 해당 문제 채점내역 hashmap에 갱신한다.
  • 함수: 대기큐 출력
    • 대기중인 갯수를 출력

유의해야하는 조건! - 대기큐

  • 문제를 풀다가 틀리거나, 시간초과가 나면 이부분을 확인하자.
  • 문제를 그냥 읽으면 대기큐라 되어있어서 우선순위큐 하나로 만든다.
  • 시간 초과가 나게 되는데 이유는 쓸모없는 poll이 많아진다는것이다.
    • 전체 대기큐를 조회하면서 조건에 안맞으면 poll하고 또다른 큐에 저장
    • 조건에 맞는 문제가 나오거나 모든 문제를 확인하면, 저장한 큐에서 다시 대기큐로 넣기
  • 조건(채점중X,최근진행X)들을 전부 확인하면서 우선순위큐를 poll해야 한다.
    • 이건 제공되는 문제들 만큼 반복할것이며 시간초과의 이유다.
  • 여기서 해당 조건을 판별하는데 도메인을 기준으로 하고있다는점이다.
  • 그렇다면 대기중인것들에서 조건에 맞는 도메인만 우선순위큐로 뽑는 자료구조가 필요한것이다.
  • 여기서 [도메인, 우선순위큐] 형태의 hashmap이 필요하게 된다.
  • 각 도메인별로 조건에 만족한 우선순위큐에서 앞에 것만 확인하기만 하면된다.
    • 이는 서로다른 도메인만큼의 시간이 걸린다!

유의 해야하는 조건! - url과 도메인

  • 문제가 가독성이 구린것중에 url과 도메인이 나온다.
  • url은 처음 채점요청에서 나오고 더이상 안나오며, 이후로는 도메인을 사용한다.
  • 제일 중요한것을 url은 대기큐에서 조회할때만 사용한다.
  • url에서 /를 기준으로 분리해서 도메인을 뽑아 관리하자.

후기

  • 삼성 기출에서 2번에 해당하며 B형(pro) 형태로 문제가 출시된다.
    • 입력부분은 전부 제공
    • 실제 문제로 나오는 함수의 이름과 parameter까지 함수 껍데기가 제공된다.
    • 해당 함수를 채우는 형식
  • 코드트리는 그런 형태를 제공하지 않고 일반 코딩테스트처럼 나왔다.
    • 직접 해당 입력되는 형태를 만들어야 해서 귀찮다.
    • 이런 템플릿은 어느정도 만들어놓고 재활용하는게 좋다.
  • 자료구조를 어떻게 만들지만 빠르게 파악해야 하는 문제였다.
  • 이것을 설계단계에서 빠르게 인지하고 설계할 수 있어야 할듯하다.