28일-2 Group the People Given the Group Size They Belong To
1. 문제 및 접근
leetCode
Group the People Given the Group Size They Belong To
문제 이해가 어려웠다
배열이 주어지면, 같은 배열의 크기만큼 넣어서 그 숫자에 묶음 대한 index를 반환
일단 수가 들어오면 처음 들어오거나,or full이거나 확인하고 새로 만들어야 할듯 ?
즉 배열의 i번째 만큼의 크기의 배열을 만들고, 거기에 그 수를 넣는 것
처음엔 list로 들어온 것들을 찾고, 하려고 했는데, 사실 찾는다면 map을 써야 더 좋을 것 같아
Constraints:
- groupSizes.length == n
- 1 <= n <= 500
- 1 <= groupSizes[i] <= n
2. 풀이
public List<List<Integer>> groupThePeople(int[] groupSizes) {
List<List<Integer>> answer = new ArrayList<>();
HashMap<Integer, List<Integer>> map = new HashMap<>();
//그 인덱스 만큼 찾는 게 어려워서 걍 정렬 ?
// Arrays.sort(groupSizes);
for (int i = 0; i < groupSizes.length; i++) {
int size = groupSizes[i];
if (!map.containsKey(size)) { // 없을 경우
map.put(size, new ArrayList<>());
}
map.get(size).add(i); // map에서 list를 가져오고 그 list에 add
if (map.get(size).size() == size) {
answer.add(new ArrayList<>(map.get(size)));
map.get(size).clear();
}
}
// for (int i = 0; i < groupSizes.length; i++) {
// if (answer.get(i).isEmpty() || answer.get(i).size() == groupSizes[i]) {
// // 없거나 다 찾거나
// answer.add(new ArrayList<>(groupSizes[i]));
//
// } if (answer.get(i).size() > groupSizes[i]) {
// answer.get(i).add(i);
// }
//
// answer.get(i).contains()
// }
return answer;
}
2-1. 틀린 접근
첫 접근은 array를 정렬해 차근차근 다 넣어줄려고 생각했다.
여기서 막힌 게 answer(i).isEmpty로 했는데 contain을 쓰면 될 것 같았고,
여기 저기 손 보는 도중 (else if, isEmpty()) map으로 활용하면 더 쉽게 될 것 같았다.
2-2. map 활용
정답을 담을 answer과
중간에 get을 하기 쉽게 map을 선언
int[] arr = new int[] {3, 3, 3, 3, 3, 1, 3}를 예시로 들겠다..
현재 배열에 주어진 수를 size로 초기화
map에 size인 현재 수를 key값으로 찾고,
없을 경우
- key = size (현재 3), value로 빈 List 생성
있을 경우
- map.get(3).add(i) map에서 key로 가져와 그 값에 index 추가
2-3. 정답에 담기
추가한 후에
map.get(key값인 3)으로 list에 접근해 size가 현재 group[i]인 수라면 ex) 3
answer에 map.get(3)의 value를 추가해주고 value 값 초기화!
4. 마무리
원래 풀이는 사이즈까지 체크하고, 더하려고 했는데 틀린 답이 나온다
사실 순서대로 들어가기 때문에 먼저 추가해주고 해야 되는데 놓쳤다.
arr = {3, 3, 3, 3, 3, 1, 3 }로 예시를 들자면,
1. map = {k = 3, v = {} }
IF문에 걸려 먼저 3에 빈 배열이 만들어지고, 그 다음 3추가
map = {k = 3, v = {0}}
index가 추가된다.
2.map = {k = 3, v = {0,1}}
map.get(size).add(1)
3. map의 경우의 수
map.put이 2번 째 if문 앞이라면 ? (정답의 경우)
- map = {k = 3, v = {0, 1, 2}} -> answer에 추가 후 Clear
map.put이 2번째 if문 뒤에 있다면 ? (틀린 내 답의 경우)
- map = {k = 3, v = {0, 1, null} -> answer에 추가하지 않고, 다음 반복문으로
안들어간다는 걸 null로 표현
먼저 검사하고 넣어야 한단 생각이였는데, 사실 먼저 나온 수라면
추가할 시점에 0번째 index에서 size를 초과해서 넣을 일이 없긴 하다..
이런 예외때문에 미리 넣었는데 반만 생각했다 ㅠㅠ
아직 많이 부족하다..