[7주차_수요일] 문제 추천 시스템 Version 1

[KodaHye]

• 사이트 : 백준(BOJ)
• 문제: 문제 추천 시스템 Version 1
• 번호: 21939

### 🤔 시간복잡도 고려사항

### 💡 풀이 아이디어

[yeongleej]

🤔 시간복잡도 고려사항

• 문제 수 : P <= 100,000
• 명령 수 : M <= 10,000

1. 정렬 이용하기
   • 시간복잡도 : O(N log N)
   • 정렬은 매 recommend요청 시마다 sorting을 해야 함
   • 즉, O(M * P log P)가 되므로 시간초과!
2. 우선순위 큐 이용하기
   • 시간복잡도 : O(log N)
   • 즉, O(M * log P)가 되므로 가능

💡 풀이 아이디어

• 우선순위 큐를 이용해서 가장 어려운 문제리스트 와 가장 쉬운 문제리스트를 관리
  • hpq : 가장 어려운 문제리스트
  • epq: 가장 쉬운 문제리스트
• 현재 문제 리스트에 있는 문제번호의 난이도를 나타내는 배열 선언
  • srr[num] : 문제번호 num에 해당하는 난이도
  • solved로 문제 해결 => srr[num] = -1
    • 해당 문제의 난이도를 -1로 지정
  • add로 문제 추가 => srr[num] = level
    • 이전에 있던 문제(100번, 난이도 1)가 해결되고 난이도가 다른 문제(100번, 난이도 100)가 추가될 수 있으므로 새로운 난이도로 갱신

처음에는 정렬로 리스트 하나만 생성해서 첫번째와 마지막을 이용하려 했지만,,, 시간초과가 발생했습니다...우선순위큐를 활용하는 방법을 더 공부해야겠어요,,,

[KodaHye]

🤔 시간복잡도 고려사항

• 1 <= 문제의 개수 <= 100_000
• 1 <= 명령의 개수 <= 10_000
• log_2(100_000) = 1660964.xx이므로 문제가 10_000개 이상일 때, 계속하여 문제에 대해 정렬할 시 시간 초과가 발생할 수 있음
  • 100_000 × log_2(100_000) × 10_000
• TreeMap 사용
  • TreeMap.put() 시간복잡도: O(logN)

💡 풀이 아이디어

• Node클래스
  • int num: 번호, int level: 난이도
• TreeMap<Node, Integer> mapToIdx
  • TreeMap의 key를 Node로 설정하여 우선순위대로 정렬될 수 있도록 함
  • value는 문제 번호 값
• TreeMap<Integer, Node> idxToNode
  • 문제 번호를 통해 객체에 접근할 수 있도록 함
  • TreeMap이 아닌 일반적인 HashMap을 사용해도 가능
• recommend(StringTokenizer st)
  • x == 1: mapToIdx.lastKey().num 출력
  • x == -1: mapToIdx.firstKey().num 출력
• add(StringTokenizer st)
  • idxToMap과 mapToIdx에 새로운 객체 넣어주기
• solve(StringTokenizer st)
  • idxToMap과 mapToIdx에 입력된 객체 삭제해주기

시간복잡도를 고려하고, 안된다! 싶으면 다른 방법으로 접근하는 태도를 길러야될 것 같습니다!!

[baexxbin]

🤔 시간복잡도 고려사항

• 문제 수 P <= 100,000 (10^5)
• 명령 수 M <= 10,000 (10^4)
• 우선순위큐(O(logN))가능

💡 풀이 아이디어

• 큰 값, 작은 값 나눠서 관리 → 우선순위큐 2개 사용(순서, 역순)

  처음엔 (같은 번호, 다른 레벨)이 같이 공존하는 줄 알고 해시코드를 사용해야하나 고민했었으나, 같은 번호는 중복되어 주어지지 않기에 사용하지 않음

• Set check: 풀어야할 문제들 관리, 문제 번호만으로 관리

• Map<Integer, Problem> notes: 문제번호, 문제 관리, 문제 객체를 다루기 위해 사용

  • 같은 문제가 공존하지 않기에 번호를 인덱스로 사용
    1. add
  • note에 존재하면(동일한 번호 이전에 존재), 이전 번호 check와 우선순위 큐들에서 삭제
  • 새로운 값 삽입
    2. solved
  • check에서 들어온 번호 삭제
    3. recommend
  • 우선순위 큐 peek 값이 풀어야할 문제(check)에 해당하면 출력
  • 풀어야할 문제에 해당하지 않으면(이미 푼 문제) 우선순위에서 빼기

객체로 이뤄진 값을 하나의 필드값만으로 제어하는 연습을 더 해야하겠다! 다른 분들 코드보다 배로 느려서.. 한번 다른 분들 코드 탐구해보겠습니다!

[Jewan1120]

🤔 시간복잡도 고려사항

• 6 ≤ N, P ≤ 100,000 → 10^5이므로 O(N logN)으로 진행
• Heap

💡 풀이 아이디어

1. 우선순위 큐 2개 (오름차순, 내림차순) + 해시 셋(푼 문제 저장) → 실패...
   • 풀이했던 문제가 다시 들어올 수 있음을 체크 못함
   • 이전에 풀었던 문제 넘버가 새로운 난이도로 들어올 수 있음 -> Set으로 저장하면 해결 불가했음
2. 트리 맵 + 해시 맵 → 성공!
   • 트리 맵을 이용해서 문제 넘버와 난이도를 정렬해서 저장
   • 해시 맵을 이용해서 문제의 넘버와 난이도를 저장해서 풀었는지 안 풀었는 지를 확인
   • recommend: 조건에 맞게 문제를 출력
   • add: 각 맵에 문제 입력
   • solved: 해시 맵에서 해당 문제의 난이도를 가져와서 트리맵에서 지워 줌

     객체 다루기 복잡하네요...

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: TreeMap, TreeSet
• 시간복잡도: 1<=문제수<=100000 1<=명령문<=10000
  • O(n*m) 완전탐색으로 풀이할 경우 10^9 으로 풀이가능

💡 풀이 아이디어

• TreeMap<Integer,TreeSet<Integer>>

  • TreeMap 의 특징인 key 값 정렬을 통해 난이도를 오름차순으로 정렬 동일한 문제 번호라도 난이도가 다를 수 있음 TreeSet 의 특징인 정렬을 통해 문제번호를 오름차순으로 정렬

• recommend

  • 문제 난이도 1 일 경우 TreeMap의 마지막 key의 문제번호가 가장 큰 TreeSet의 마지막 요소 반환
  • 문제 난이도 -1 일 경우 TreeMap의 첫번째 key의 문제번호가 가장 작은 TreeSet의 첫번째 요소 반환

• add

  • TreeMap 에 추가

• solved

  • TreeMap 탐색 후 TreeSet에서 삭제, TreeSet의 요소가 없을 경우 삭제

계속 시간초과가 났는데, 원인이 BufferedReader로 매개변수를 가공할 때 형변환이 많거나 문자열 가공(split)이 많이 발생해서 였네요.. BufferedReader보다 Scanner같이 형변환 없이 바로 매개변수를 사용하는게 더 효율적인걸 알았어요!

[icegosimperson]

🤔 시간복잡도 고려사항

• N, P <= 100,000 / M <= 100,000 -> O(N) 이하 가능
• TreeSet : O(log N)

💡 풀이 아이디어

• 3가지 명령어(recommend, add, solved)에 따라 난이도를 고려하여 문제 번호를 추천하는 시스템
• 3가지 명령어 -> switch문으로 recommend, add, default 경우 명령어 구분
• TreeSet : 난이도, 문제 번호를 저장
  • TreeSet만 사용했을 때 시간 초과 발생하였음!
• HashMap : 문제 번호로 난이도를 빠르게 조회하여 성능 향상
  • solved 문제 삭제 시 O(1) 시간 복잡도로 문제 난이도 빠르게 조회

    우선순위 큐를 떠올린 문제였는데, TreeSet을 사용 해본적이 없어서 TreeSet으로 풀어봤습니다 객체 선언 연습하기..!