[33번] [중상] 체육복 (미완)

프로그래머스

 

이 문제는 아직 극복을 못했다!!!

 

아래는 여러 시도를 통해 풀이를 해보려고 시도한 흔적들...

 

* 체육복 (탐욕법)
 * 체육복 여벌이 있는 학생은 본인 번호의 +/- 1 번호의 학생에게만 빌려줄 수 있으므로, +/-reserve[i] 번호가 lost 배열에 있는지 확인하고, 있으면 n-lost.length 값에 +1 해주기
 * linear search이므로, sort를 먼저 해줌

 

[pseudo code] => 배열 루프 충첩 + 반복이 너무 많은것 같아 폐기하고 아래로 넘어감
1. result =[] 생성
2. 1~n을 돌는 for loop 생성
    - lost에는 없는 번호를 push 
    - lost에 있는데, reserve에 있는 학생은 result에 푸쉬 후 reserve에서 삭제
3. lost 배열을 도는 for loop 생성 (뒤에서부터 돌면서 pop 하면 빠름)
    - lost[i]+1 || lost[i]-1 값이 reserve에 있다면, lost[i]를 result에 push
    - reserve 값을 삭제
4. result.length를 반환

function solution(n, lost, reserve) {
  let result = [];
  // reserve에 있는데,
  for (let num of lost) {
    if (reserve.includes(num)) {
      result.push(num);
      lost.splice(lost.indexOf(num), 1);
      reserve.splice(reserve.indexOf(num), 1);
    }
  }

  for (let i = 1; i <= n; i++) {
    if (!result.includes(i)){
        if (!lost.includes(i)) {
            result.push(i);
          } else if (lost.includes(i) && reserve.includes(i)) {
            result.push(i);
          }
    }

  }
}

 

 

[psuedo code version 2] => 안됨ㅋㅋ 정확도에서 실패..ㅠㅠ
1. lost 배열을 돌는 for문 생성
    - 각 요소가 reserve 배열에 있으면, result 배열에 push
    - 해당 요소를 lost와 reserve 모두에서 삭제
2. 체육복을 가진 전체 학생수 result 변수를 선언하고 n - lost.length로 초기화
3. + 값을 먼저 검사하는 함수 생성
    함수의 겁사값을 받을 temp, 배열을 함수 안에서 받을 lost, reserve 선언 및 초기화
    lost 배열을 도는 for loop 생성
        - lost[i]+1 번호가 reserve에 있으면 temp++ 하고, reserve에서 지우기 
        - lost[i]-1 값이 reserve에 배열에 있으면 temp++ 하고, reserve에서 지우기
    temp 값을 함수 리턴 값으로 반환
4. 위와 같은 로직으로 -값을 먼저 검사하는 함수 생성
5. 두 함수의 리턴 값을 비교해서 더 큰 값을 result에 더해줌
5. result.length 반환

 

function solution(n, lost, reserve) {
  lost.sort((a, b) => a - b);
  reserve.sort((a, b) => a - b);
  let result = n - lost.length;

  let temp1 = addFirst(lost, reserve),
    temp2 = deductFirst(lost, reserve);
  console.log(result, temp1, temp2);

  return temp1 >= temp2 ? result + temp1 : result + temp2;
}

function addFirst(lost, reserve) {
  let temp = 0,
    l = [...lost],
    r = [...reserve];
  console.log("addFirst:", r, l);

  for (let i = r.length - 1; i >= 0; i--) {
    let n = r[i]; // 항상 r의 마지막 값으로 유지
    let e = l.length - 1;

    if (l.includes(n, e)) {
      temp++;
      let lastIdx = l.indexOf(n, e);
      if (lastIdx < e) {
        do {
          l.pop();
        } while (lastIdx === e);
      }
      continue;
    } else if (l.includes(n + 1, e)) {
      temp++;
      let lastIdx = l.indexOf(n + 1, e);
      if (lastIdx < e) {
        do {
          l.pop();
        } while (lastIdx === e);
      }
    } else if (l.includes(n - 1, l.length - 1)) {
      temp++;
      let lastIdx = l.indexOf(n - 1, l.length - 1);
      if (lastIdx < e) {
        do {
          l.pop();
        } while (lastIdx === e);
      }
    }
    r.pop();
  }
  return temp;
}

function deductFirst(lost, reserve) {
  let temp = 0,
    l = [...lost],
    r = [...reserve];
  console.log("deductFirst:", r, l);
  for (let i = r.length - 1; i >= 0; i--) {
    let n = r[i]; // 항상 r의 마지막 값으로 유지
    let e = l.length - 1;
    console.log("i번째", i, temp);
    if (l.includes(n, e)) {
      temp++;
      let lastIdx = l.indexOf(n, e);
      if (lastIdx < e) {
        do {
          l.pop();
        } while (lastIdx === e);
      }
      continue;
    } else if (l.includes(n - 1, e)) {
      temp++;
      let lastIdx = l.indexOf(n - 1, e);
      if (lastIdx < e) {
        do {
          l.pop();
        } while (lastIdx === e);
      }
    } else if (l.includes(n + 1, l.length - 1)) {
      temp++;
      let lastIdx = l.indexOf(n + 1, l.length - 1);
      if (lastIdx < e) {
        do {
          l.pop();
        } while (lastIdx === e);
      }
    }
    r.pop();
  }
  return temp;
}

 

 

[pseudo code] => 킹왕짱 동기 분의 도움으로 키밸류 쌍을 이용 시도하였지만.. 왜인지 실패..? 이제 너무 낡고 지치고 힘들어서 자려고 한다..ㅋㅋㅋ
1. 빈 배열 students를 생성
2. 1 ~ n까지 for loop를 돌면서 students[i]에 {num: i, clothes: 0}을 부여
3. lost 배열을 돌면서 students[l].clothes에 -1
3. reserve 배열을 돌면서 
  - students[r].clothes에 +1
4. students1과 students2에 students 배열 복사
5. 앞 뒤로 체육복을 빌려주는 작업 수행할 for loop 생성
  - (i 값을 기준으로 i-1 -> i+1 순으로 검사)
  - (i 값을 기준으로 i+1 -> i-1 순으로 검사)
4. students 배열을 돌면서 -1 값을 n 값에서 빼고, 이를 리턴

 

function solution(n, lost, reserve) {
  let a1 = 0,
    a2 = 0;
  let students = [];

  for (let i = 1; i <= n; i++) {
    students[i] = { num: i, clothes: 0 };
  }
  for (let l of lost) {
    students[l].clothes = -1;
  }
  for (r of reserve) {
    students[r].clothes = +1;
  }

  let students1 = [...students];
  let students2 = [...students];

  for (let i = 1; i < students1.length; i++) {
    let s = students1;
    if (
      s[i].clothes == 1 &&
      i + 1 < students1.length &&
      s[i + 1].clothes == -1
    ) {
      s[i].clothes = 0;
      s[i + 1].clothes = 0;
    } else if (s[i].clothes == 1 && i - 1 > 0 && s[i - 1].clothes == -1) {
      s[i].clothes = 0;
      s[i - 1].clothes = 0;
    }
  }

  a1 = students1.forEach((e, i) => {
    if (i > 0 && e.clothes >= 0) {
      return a1++;
    }
  });
  console.log(a1);

  for (let i = 1; i < students2.length; i++) {
    let s = students2;
    if (s[i].clothes == 1 && i - 1 > 0 && s[i - 1].clothes == -1) {
      s[i].clothes = 0;
      s[i - 1].clothes = 0;
    } else if (
      s[i].clothes == 1 &&
      i + 1 < students1.length &&
      s[i + 1].clothes == -1
    ) {
      s[i].clothes = 0;
      s[i + 1].clothes = 0;
    }
  }

  return a1 >= a2 ? n - a2 : n - a1;
}

console.log(solution(5, [2, 4], [1, 3, 5]));
console.log(solution(5, [2, 4], [3]));
console.log(solution(3, [3], [1]));

---

2022.11.27 추가

key-value 오브젝트로 다시 접근해봤다. 그런데, 여전히 통과를 못함..? 왜???

function sol(n, lost, reserve) {
  let students = {};

  for (let i = 1; i <= n; i++) {
    students[i] = 1;
  }

  lost.forEach((l) => students[`${l}`]--);
  reserve.forEach((r) => students[`${r}`]++);

  for (let s in students) {
    if (students[`${s}`] === 0) {
      if (students[`${s - 1}`] === 2) {
        students[`${s - 1}`]--;
        students[`${s}`]++;
      } else if (students[`${s + 1}`] === 2) {
        students[`${s + 1}`]--;
        students[`${s}`]++;
      }
    }
  }

  let answer = 0;
  for (let s in students) {
    if (students[`${s}`] >= 1) {
      answer++;
    }
  }
  return answer;
}

console.log(sol(5, [2, 4], [1, 3, 5]));
console.log(sol(5, [2, 4], [3]));
console.log(sol(3, [3], [1]));


테스트 1 〉	통과 (0.11ms, 33.4MB)
테스트 2 〉	통과 (0.34ms, 33.4MB)
테스트 3 〉	통과 (0.21ms, 33.4MB)
테스트 4 〉	통과 (0.20ms, 33.5MB)
테스트 5 〉	실패 (0.18ms, 33.5MB)
테스트 6 〉	통과 (0.15ms, 33.4MB)
테스트 7 〉	실패 (0.20ms, 33.4MB)
테스트 8 〉	통과 (0.19ms, 33.5MB)
테스트 9 〉	통과 (0.21ms, 33.6MB)
테스트 10 〉	실패 (0.26ms, 33.4MB)
테스트 11 〉	실패 (0.10ms, 33.4MB)
테스트 12 〉	통과 (0.10ms, 33.6MB)
테스트 13 〉	실패 (0.10ms, 33.4MB)
테스트 14 〉	실패 (0.13ms, 33.4MB)
테스트 15 〉	실패 (0.11ms, 33.4MB)
테스트 16 〉	실패 (0.09ms, 33.4MB)
테스트 17 〉	통과 (0.09ms, 33.5MB)
테스트 18 〉	통과 (0.10ms, 33.4MB)
테스트 19 〉	통과 (0.10ms, 33.4MB)
테스트 20 〉	통과 (0.09ms, 33.5MB)