99 Club 2기 | Java | Beginner
🥪 1700. Number of Students Unable to Eat Lunch
🏷 관련 주제 : Array Stack Queue Simulation
Easy
✔ Solution with Queue
import java.util.LinkedList;
import java.util.Queue;
import java.util.Arrays;
import java.util.stream.Collectors;
class Solution {
public int countStudents(int[] students, int[] sandwiches) {
Queue<Integer> q = new LinkedList<>(Arrays.stream(students).boxed().collect(Collectors.toList()));
for (int j = 0; j < sandwiches.length; j++) {
int sandwich = sandwiches[j];
for (int i = 0; i < q.size(); i++) {
int cur = q.poll();
if (cur == sandwich) {
break;
} else if (i == q.size()) {
return sandwiches.length - j;
} else {
q.offer(cur);
}
}
}
return 0;
}
}채점 결과
✔ Solution with List
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.stream.Collectors;
class Solution {
public int countStudents(int[] students, int[] sandwiches) {
List<Integer> stli = Arrays.stream(students).boxed().collect(Collectors.toList());
for (int i = 0; i < sandwiches.length; i++) {
int sandwich = sandwiches[i];
int idx = stli.indexOf(sandwich);
if (idx != -1) {
stli.remove(idx);
} else {
return sandwiches.length - i;
}
}
return 0;
}
}채점 결과
✔ Solution with Array & Counting
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.stream.Collectors;
class Solution {
public int countStudents(int[] students, int[] sandwiches) {
int[] stCnt = new int[2];
int[] swCnt = new int[2];
for (int i = 0; i < sandwiches.length; i++) {
stCnt[students[i]]++;
}
for (int i = 0; i < sandwiches.length; i++) {
swCnt[sandwiches[i]]++;
if (swCnt[sandwiches[i]] > stCnt[sandwiches[i]]) {
return students.length - i;
}
}
return 0;
}
}채점 결과
💥 오늘 만난 문제 & 나의 시도 💦 & 해결 방법 👍
📌 오늘 만난 문제 : 매개변수로 정수 배열 students와 sandwiches가 주어질 때,
점심을 먹지 못하는 학생 수 반환하기
- Queue를 이용한 풀이
처음에는 문제 주제가 Stack, Queue라서 앞에 서 있는 학생과 먼저 비교하고 아니면 그 학생을 맨 뒤로 보내서 계속 비교한다고 해서 FIFO 방식의 Queue를 이용하였는데
제출하고 나서 속도가 너무 느리게 나와서 다른 풀이도 작성해 보았다.
(처음에는 주석도 달려있어서 맨 뒤에 막대그래프에 내 코드가 위치했어서 더 그런 것 같다.
주석을 제거하니 3ms가 나왔다.)
- List를 이용한 풀이
indexOf() 를 이용하고 remove() 메서드를 사용해 샌드위치를 가져간 학생을 제거하려고 했는데
remove()메서드가 매개변수를 인덱스로 보는지 object로 보는지 정확히 모르겠어서 처음에는 set()메서드로 해당 인덱스를 -1로 바꿔주고 문제를 풀어서 해결했는데
뒤에 다시 풀어보니 인덱스로 제거가 되는 것을 확인할 수 있어서 remove()메서드를 이용해서도 코드를 작성할 수 있었다.
- Counting을 이용한 풀이
sandwiches의 원소들을 앞에서부터 볼 때, 0또는 1의 개수가 students에 존재하는 0 또는 1의 개수보다 많아지면 샌드위치를 가져갈 학생이 없어서 점심을 못 먹는 학생이 나온다는 것을 알 수 있다.
그래서 길이 2인 일차원 정수배열로 students의 0과 1개수, sandwiches의 0과 1개수를 각각 반복문을 돌며 counting해 주어서 문제를 해결하였다.
💬 무엇을 새롭게 알았는지
Queue를 이용해 문제를 풀어보았다.
for문 2번이 실행 속도가 더 빠르게 나와서 신기했다.
List에서 remove()메서드는 매개변수를 인덱스로 보고 List의 원소를 삭제한다는 것을 알게되었다.
