매일 매일 하루 한 문제씩.
꾸준히 이어가는 코딩테스트 풀이 기록 ✅
오늘 푼 문제는 '체육복'
탐욕법(greedy)로 풀라는 힌트가 있었는데 매번 이 문제는 내 스스로 풀지 못했던 문제라서 약간 마음의 부담도 있었고... 어제 풀던 카카오 기출문제는 거의 4번째 푸는데도 해결이 안되서 약간 마음이 꺾인 상태였는데...ㅋㅋㅋ
오늘은 정말 해결해봐야지!! 하는 마음으로 문제를 풀었고 몇 개의 테스트케이스에 대한 힌트를 얻고서 결국 자바와 자바스크립트 두가지 언어로 모두 풀어냈다.
자바스크립트는 최대한 immutable한 방식으로 풀려고 노력은 했으나 결국 splice를 사용하여 배열을 변형시킬 수 밖에 없었는데, 그래도 filter와 map 배열메서드를 사용하여 for문을 배제하고 풀어보았다.
다른 사람의 풀이를 보다가 '유지보수'와 관련된 내용을 읽게 되었는데...
솔직히 오늘 내가 작성한 코드는 유지보수에 용이하다고 볼 순 없을 것이다.
지금은 문제를 푸는데 좀 급급한 면이 있지만, 유지보수의 면이나 효율성 등을 계속 고려하면서 문제를 풀어야겠단 생각이 들었다.
프로그래머스 코딩테스트 체육복
문제
java solution
모든 문제들이 그렇겠지만 이번 문제를 풀면서 가장 애를 먹었던 부분이 바로 엣지 케이스를 찾아내는 것이었다.
왜 이렇게 엣지 케이스를 찾는게 쉽지 않은지... 분명 될 것 같은 논리인데도 계속 통과가 되지 않아 너무 시간을 오래 써먹었고 계속 밀리다간 또 풀어내지 못할 것 같아 힌트를 확인하여 나와 동일한 상황에 처한 사람이 쓴 글을 봤는데...
아래 케이스가 통과되지 않는 것을 보면서 '정렬'을 하지 않았을 때의 문제라는 점을 눈치챌 수 있었다.
assertEquals(5, solution.solution(5, new int[]{4, 2}, new int[]{3, 5}));아하... 앞으로 탐욕법과 관련된 어떤 문제를 풀게될 지 모르겠지만, 적어도 '정렬'에 대한 부분을 누락하지 말고 풀자 ㅠㅠ
import java.util.*;
class Solution {
public int solution(int n, int[] lost, int[] reserve) {
int answer = 0;
List<Integer> losts = new LinkedList<>();
List<Integer> reserves = new LinkedList<>();
Arrays.sort(lost);
Arrays.sort(reserve);
for (int item : reserve) {
reserves.add(item);
}
for (int value : lost) {
if (reserves.contains(value)) {
int index = reserves.indexOf(value);
reserves.remove(index);
continue;
}
losts.add(value);
}
// 진짜 잃어버린 아이와 진짜 빌려줄수 있는 아이가 각각 losts, reserves에 남아있음
// 잃어버린 사람 목록이 없다면 모두가 다 수업에 들어갈 수 있으므로 n을 그대로 리턴
if (losts.size() == 0) {
return n;
}
n -= losts.size();
for (int theNumberOfLost : losts) {
if (reserves.contains(theNumberOfLost - 1)) {
n += 1;
int index = reserves.indexOf(theNumberOfLost - 1);
reserves.remove(index);
continue;
}
if (reserves.contains(theNumberOfLost + 1)) {
n += 1;
int index = reserves.indexOf(theNumberOfLost + 1);
reserves.remove(index);
}
}
answer = n;
return answer;
}
}javascript solution
솔직히 자바 문제를 풀고 나서는 '와.. 이걸 어떻게 immutable한 방식으로 자바스크립트로 풀어낼것이냐...' 하는 압도적인 절망감(ㅋㅋ)에 빠졌다.
솔직히 한참을 고민하다가 forEach, map 등등 여러가지 생각이 떠올랐고, 우선 자바에서 풀어낸 방법과 마찬가지로 정말 잃어버린 아이, 그리고 정말로 빌려줄 수 있는 아이만 남겨두고 난 뒤에 문제를 풀어내자! 라고 마음먹었다.
그리고 나서 떠올린 방법은 예전에 reduce를 중간에 멈추는 방법을 찾다가 알아낸 'splice'를 활용하는 것이었다.
map을 활용하면서 빌려줄 수 있는 경우는 true, 그렇지 않은 경우는 false를 반환하게 했는데, 계속 이 사이클이 돌아가면서 realReserve 배열에 변화를 주어야 했다.
immutable한 방식은 아니나(원본 배열을 변형하기 때문에) map, filter를 활용해보는 것이 내게는 더 중요했기 때문에 우선 splice 메서드를 사용하여 문제를 해결했고, 남은 resultArray에서 false값의 size(빌리지 못하는 경우의 수)를 전체 학생값에서 빼 주었다.
function solution(n, lost, reserve) {
const realLost = lost.sort().filter((value) => !reserve.includes(value));
const realReserve = reserve.sort().filter((value) => !lost.includes(value));
if (!realLost.length) {
return n;
}
const resultArray = realLost.map((value) => {
if (realReserve.includes(value - 1)) {
realReserve.splice(realReserve.indexOf(value - 1), 1);
return true;
}
if (realReserve.includes(value + 1)) {
realReserve.splice(realReserve.indexOf(value + 1), 1);
return true;
}
return false;
});
return n - resultArray.filter((value) => value === false).length;
}어제 문제를 풀어내지 못해서 상심했었지만...ㅋㅋ 또 이렇게 하나의 문제를 스스로의 힘으로 풀어보면서 조금씩 힘을 내본다.
공부하고 또 공부하다보면 풀어내지 못할 문제는 없을거라 믿으며...
또 새로운 배움을 위해 화이팅!!
