[3주차_수요일] 13335_트럭

[Jewan1120]

• 사이트: 백준
• 문제: 트럭
• 번호: 13335번

[yeongleej]

🤔 시간복잡도 고려사항

• 다리의 길이 w ≤ 100
• 트럭의 수 n ≤ 1,000
• 100 * 1000 == 100,000 이므로 선형탐색 가능

💡 풀이 아이디어

• bridges : 다리에 있는 트럭들 크기 리스트
• trucks: 대기중인 트럭들 리스트
• total: 현재 다리 위의 트럭들 무게
• 초기에 bridges를 다리 길이(w)만큼 0으로 채우는 것은 => 다리에 크기가 0인 트럭들을 w개 올리는 것
  • 이는 다리에 있는 트럭을 하나씩 뺴거나 추가하면서 다리 상태를 관리할 수 있음
• 매 시간마다, 다리에 있는 트럭을 하나 뺴고, 새로운 것을 추가하기
• 이때, 트럭이 현재 다리에 올라갈 수 있으면(truck.peek()+total <= L) 추가
• 올라갈 수 없다면 크기가 0인 임시 트럭 추가

[Jewan1120]

🤔 시간복잡도 고려사항

• 1 ≤ n ≤ 1,000, 1 ≤ w ≤ 100 → 10^5이므로 O(nlogn)이하의 탐색

💡 풀이 아이디어

• 선입선출 자료구조인 큐를 이용
• 다리의 길이를 구현하기 위해 트럭과 트럭 사이에 빈 공간을 삽입
  • 큐의 초기 상태에도 다리의 길이만큼 빈 공간 삽입
• 단위 시간으로 진행하면서 트럭의 움직임을 구현
  1. 맨 앞 트럭이 다리에서 나감
  2. 새로운 트럭이 다리에 들어옴
  3. 트럭이 들어올 수 없다면 빈 공간 삽입

[baexxbin]

🤔 시간복잡도 고려사항

• n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100)
• O(NlogN)이내로 풀기

💡 풀이 아이디어

• 큐 이용
• 다리에서 트럭 탈출하기
  • 현재 시간 - 트럭이 다리에 진입한 시간
• 다리에 트럭 올리기
  • 무게, 길이 조건이 가능할 경우
  • que.add(트럭 무게,다리 진입 시점)으로 삽입

복잡하게 생각하지 말기

[icegosimperson]

🤔 시간복잡도 고려사항

• 시간 복잡도 : n, L <= 1,000, 단순 구현인줄알고 고려하지 않았었는데,
• 여러분 commit을 보고 다시 생각해보니 O(N logN) 이하 사용해야한다는 것을 알았습니다.
• 큐 연산 O(n* m) 사용 가능

💡 풀이 아이디어

• 사용할 자료구조 : 큐 (먼저온 트럭이 먼저 나감)
• 반복문 작성에 대한 고민
  1. 다리 큐가 빌 때까지 반복
  2. 트럭이 다리에서 내릴 때 (현재 다리 무게) - (다리 위 트럭 무게) weightBridge -= bridge.poll();
  3. 실행 조건 : (현재 트럭 무게) + (현재 다리 무게) <= (다리 하중)
  4. 트럭이 다리 위에 있는 것 표현 : weightBridge += trucks.peek();
  5. 트럭 무게를 다리에 추가 bridge.add(trucks.poll());
  6. L(다리 하중)보다 클 경우 트럭을 추가 하지않음 bridge.add(0);

시간 복잡도 대충 생각하지 말기 Queue 2개(트럭, 다리) 사용 생각을 못했습니다 Queue 원소 추가 시 고정 관념에 사로 잡히지 말기 bridge.add(trucks.poll());

[KodaHye]

🤔 시간복잡도 고려사항

• 다리의 길이: 1<= w <= 100
• 트럭의 수: 1<= n <= 1,000
• 다리의 길이 × 트럭의 수 <= 100,000 이므로 문제에 주어진 대로 구현해도 시간이 충분하다고 생각
  

💡 풀이 아이디어

• Truck 클래스: 트럭의 무게, 위치 저장
• Queue: 다리에 지나가는 트럭 순서대로 무게 저장
• LinkedList<Truck> tunnel: 현재 다리에 있는 트럭들의 정보 저장
• int tunnelWeight: 터널에 있는 트럭들의 총 무게
• while(true)
  • 끝나는 조건: tunnel.isEmpty() == true
    1. 터널에서 제일 왼쪽에 있는 트럭이 끝에 도달했는지 확인
       • tunnel.get(0).트럭의 위치
    2. 다리에 들어올 수 있는 트럭이 있는지 확인
    3. 다리에 있는 트럭의 위치 한 칸씩 옮겨주기

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: Queue
• 시간복잡도: 1 ≤ n ≤ 1,000 개의 범위의 트럭이 다리를 건너야함. O(n^3)까지 가능

💡 풀이 아이디어 한번의 반복을 했을 때 일어날 수 있는 모든 과정을 순서에 맞게 잘 작성 해야함 각 트럭별로 다리의 길이 만큼 이동하는 배열 생성 (ex. 트럭4개, 다리길이 2 -> [2,2,2,2])

1. 다리에 있는 모든 트럭은 한칸씩 전진한다
2. 한칸씩 전진 했을 때 "가장 앞에 있는 트럭"이 다리의 길이까지 왔다면 다리에서 탈출한다
3. 다리 최대하중 이하일때만 트럭이 다리에 올라올 수 있다
4. 한번의 반복이 시간 +1초

동시에 다리에서 트럭이 내려가고 올라가는 순간이나, 여러 트럭이 동시에 다리에 있을 때 시간초 계산하는 부분이 어려워서 과정을 정리하는게 너무 어려웠어요...😭