[8주차_목요일] 대표 선수

[baexxbin]

• 사이트 : 백준(BOJ)
• 문제: 대표 선수
• 번호: 2461

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

### 💡 풀이 아이디어

[Jewan1120]

🤔 시간복잡도 고려사항

• 1 ≤ N, M ≤ 1,000 → N x M = 10^6이므로 O(N logN)으로 풀이
• 우선순위 큐 사용

💡 풀이 아이디어

• ArrayList<PriorityQueue<Integer>> arr = new ArrayList<>();으로 각 학급을 조회할 수 있도록 자료구조 선택
• 능력치를 오름차순, 내림차순으로 저장하는 우선순위 큐
  • int[] {능력치, 학급}을 저장
• 오름차순으로 저장한 우선순위 큐에서 하나씩 꺼내며 최솟값을 갱신
  • 최솟값 능력치를 가진 학생의 학급에서 다음 학생을 큐에 집어넣음
• 내림차순으로 저장한 우선순위 큐는 제어를 하지 않아도 됨
• 한 학급의 정보를 다 사용하면 종료

풀고 보니 투포인터,,?

[yeongleej]

🤔 시간복잡도 고려사항

• 학급 수 N ≤ 1,000
• 각 반의 학생 수 M ≤ 1,000

=> O(N * M)까지 생각해보기

💡 풀이 아이디어

• 투포인터로 해결
  1. 각 반의 학생들을 정렬 함
  2. 각 반의 학생을 가리키는 포인터 배열 생성
     • 초기값은 모두 0으로 첫번째 학생을 가리키게 함
  3. 각 반을 반복하며, 현재 가리키고 있는 학생들 중의 최소값과 최대값을 찾음
     • 이때, 다음 최소값을 찾기 위해 최소값을 가진 반을 기억해서 해당 반의 포인터를 증가시킴

[icegosimperson]

🤔 시간복잡도 고려사항

N, M <= 1,000 -> O(NM) = 10^6 이하로 생각

💡 풀이 아이디어

• 대표로 선발된 모든 학생들 능력치의 최댓값과 최솟값 차이가 최소가 되는 경우의 값을 출력 -> 투포인터
• 이차원 배열 선언해서 행 기준으로 각 반의 능력치 정렬
• 학생들 인덱스를 저장할 배열을 선언후 0으로 초기화 -> 첫번째 학생
• 최솟값, 최댓값 찾으면서 차이가 기존 최소 차이(min)보다 작을 경우 갱신

[baexxbin]

🤔 시간복잡도 고려사항

• 1 ≤ N, M ≤ 1,000
• NM까지 가능`O(NM)` : 모든 학생을 담은 배열 만들기
  • 여기서 *N만큼 추가 탐색 불가

💡 풀이 아이디어

• (능력치, 반)으로 객체를 만들고 하나의 리스트에 넣어, 정렬 후 슬라이딩 윈도우 진행
• 슬라이딩 윈도우
  • 반 학생 수 추가해 나가기 (right++)
    • 이때 모든 반 선수가 뽑혔으면 능력치 차 구하기 후 왼쪽 선수 제거 (left++)
• 능력치 차 구하기 (candi[right].ab-candi[left].ab)
  • left와 right 는 슬라이딩 윈도우의 성질로 서로 다른 값인게 보장 됨
  • 따라서 현재 서로의 차로 최소값과 최대값의 차 구하기

투포인터를 생각했으면 여기서 완전탐색으로 가지말고 슬라이딩윈도우 개념으로 향하기!!

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: PriorityQueue
• 시간복잡도: 1 ≤ N, M ≤ 1,000 투포인터로 풀 경우 O(N * M) + M개의 요소 정렬 O(M log M)

💡 풀이 아이디어

• int[][] students
  • 각 반의 학생들의 능력치 기준으로 오름차순 정렬해서 초기화
• PriorityQueue<Student>
  • 각 반의 학생들의 한명 씩 추가 (각 반에서 능력치가 작은 학생부터 추가됨)
• Math.min(result, max- student.power)
  • PriorityQueue 의 특징으로 능력치가 가장 작은 학생을 꺼내고
  • 최소 값을 찾기 위해 가장 높은 능력치 - 가장 작은 능력치 차 계산
• ++idxTable[student.index]
  • 능력치가 가장 작은 학생의 인덱스 테이블을 +1 하여 포인터 갱신

기존에 알고 있던 투포인터 문제(1차원 배열에서 특정값을 찾기)와 달랐어서 투포인터로 접근해야 하는지 전혀 몰랐어요! 투포인터로 문제를 풀진 않았지만, 결국에는 각 반을 1차원 배열로 봤을 때 포인터를 옮긴다는 부분에서 투포인터로 접근할 수 있는걸 알게 됐어요

연속적인 구간에서 최소/최대 값을 효율적으로 찾아야 할 때 투포인터 사용!

[KodaHye]

🤔 시간복잡도 고려사항

• 1 <= 학급의 수 <= 1,000
• 1 <= 학생의 수 <= 1,000
• 반복문을 통한 문제 풀이: 1,000 × 1,000 × 1,000 → 시간 초과
• 우선순위 큐를 사용한 문제 풀이 방법: log(1,000) × 1,000 × 1,000 < 2억

💡 풀이 아이디어

• int[][] arr: 각 학급마다의 학생들의 능력치 저장
• PriorityQueue<Node> pq: 능력치를 기준으로 정렬
• Node: 학생의 능력치와 arr에서의 행, 열 위치를 저장
• arr를 행마다 정렬한 뒤, 우선순위큐를 통해 최댓값과 최솟값의 차이의 최소 구하기
  • 시작: 0번째 열
  • 최댓값 구하기
  • pq에 Node 추가하기
  • 최솟값이 있는 값의 열 idx가 맨 끝까지 갈 때까지 반복
  • pq.poll()
    • 최댓값과 최솟값의 차이 구하기
    • 최댓값 갱신해주기