[CodeKata] 위클리 프로그래머스(2월 2주차)

🥋 Ooooth!! (Level 2)

레벨2 첫 문제부터 쉽지가 않았다. 첫 날 문제에서 1시간 반 정도를 투자해서 풀어낸 것 같다!

조금 시간이 걸리더라도 혼자 힘으로 최대한 풀어보고, 다 푼 뒤에도 관련개념(스택, 큐 등)과 다른 풀이들을 한번씩 보고 넘어가자!

---

👊 2.8(월) / 다리를 지나는 트럭

📜 문제

 

🧮 풀이

function solution(bridge_length, weight, truck_weights) {
  var answer = 0;
  let waitWeight = truck_weights.slice();
  let crossWeight = [];
  let crossTime = [];

  while (truck_weights.length !== 0) {

    crossTime = crossTime.map(time => time - 1)
    if (crossTime[0] === 0) {
      crossWeight.shift();
      crossTime.shift();
      truck_weights.shift();
    }
    if (crossWeight.length === 0 || crossWeight.reduce((a,b) => a + b) + waitWeight[0] <= weight) {
      crossWeight.push(waitWeight.shift())
      crossTime.push(bridge_length);
    }

    answer++;
  }
  return answer;
}

1. crossWeight(지나는 트럭 무게), crossTime(지나는 트럭 경과시간), waitWeight(대기중인 트럭) 등 배열을 준비한다.
2. truck_weights 은 트럭들이 다 건넜는지 확인하는 용도의 배열로 쓴다. 다 건넌 트럭(무게)은 shift() 한다.
3. 2번 내용에 따라, truck_weights 가 빌 때까지를 while 반복문의 조건으로 활용할 수 있다.
4. 트럭이 있다고 가정하자. 연산은 1) 트럭이 이동한다(crossTime) - 2) 지난 트럭을 뺀다(shift) - 3) 새 트럭을 올린다(push) 순
5. 트럭의 이동은 crossTime 배열값을 1씩 빼준다(map). (각 트럭의 초기값은 bridge_length)
6. 지난 트럭이 있다면 첫 트럭이고, 그 time값은 0일 것이다. 이 경우, 지나는 트럭 무게/시간 및 truck_weights까지 빼준다.
7. 새 트럭을 올리는 조건은 1) 다리가 비어있거나, 2) 다리위의 트럭들과 대기 트럭 첫번째 무게의 합이 무게한도(weight) 보다 작은 경우이다.
8. 이 때, 대기 트럭 첫번째 트럭(무게)을 shift() 해서 crossWeight에 push()한다. crossTime엔 이 트럭의 시간을 push() 한다.
9. 모든 반복에서 answer에 1을 더한다. 이는 시간이 경과하는 개념.

 

🖇 리뷰

- ADT(Abstract Data Type) : 추상 자료형

 

어떤 데이터의 구체적인 구현 방식은 생략한 채, 데이터의 추상적 형태와 이를 다루는 방법을 정해놓은 것이 ADT이다.

널리 이용되는 ADT로는 큐(Queue), 스택(Stack), 트리(Tree) 등이 있다.

• Queue: 선형(linear) 자료형. FIFO(First In First Out) 유형. 순서대로 처리하는 임시저장소(buffer)로 통용. 
• Stack: 선형(linear) 자료형. LIFO(Last In Furst Out) 유형. 서로 관계가 있는 작업을 수행할 때 이전 내용을 저장하는 용도. 
• Tree: 계층 자료형. 트리의 각 항목을 노드(node)라고 하며, 각 노드는 부모, 자식 관계를 가진다. (추후, DFS, BFS)

* 이번 문제에서 트럭의 다리진입은 Queue 의 형태임을 알 수 있었다.

 

- 모범예시

function solution(bridge_length, weight, truck_weights) {
  const trucks = truck_weights.map(v => ({ v: v, t: bridge_length - 1}))
  let bridge = [];
  let cnt = 0;
  while(trucks.length || bridge.length) {
    bridge = bridge.filter(item => item.t > 0);
    bridge = bridge.map(item => ({ v: item.v, t: item.t - 1}))
    cnt++;
    if(trucks.length && getSum(bridge.map(v => v.v)) + trucks[0].v <= weight){
      bridge.push(trucks.shift());
    }
  }
  return cnt;
}
 
function getSum(arr) {
  return arr.reduce((acc, cur) => acc + cur, 0);
}

* 출처: juicylog.com/38

 

내 풀이의 crossWeight, crossTime 배열쌍을, {v, t} 객체로 관리한 좋은 풀이다. (두 배열은 같은 조건에서 로직이 발동되므로?)

위에서 bridge.length가 내 crossWeight의 길이가 될 텐데, 위처럼 or(||) 조건을 썼으면 truck_weight 체크배열이 필요없지 않았을까 생각된다.

---

👊 2.9(화) / 스킬트리

📜 문제

 

🧮 풀이

function solution(skill, skill_trees) {
  var answer = skill_trees.length;
  for (let tree of skill_trees) {
    let treeIdx = -2
    for (let i = 0 ; i < skill.length ; i++) {
      if (tree.indexOf(skill[i]) !== -1 && tree.indexOf(skill[i]) < treeIdx) {
        answer--;
        break;
      }
      if (tree.indexOf(skill[i]) >= 0 && treeIdx === -1) {
        answer--;
        break;
      }
      treeIdx = tree.indexOf(skill[i]);
    }
  }
  return answer;
}

1. answer를 스킬트리의 길이로 설정했다. 조건에 어긋나면 1씩 차감하는 로직으로 작성했다.
2. 스킬트리의 각 트리를 순회하며 스킬순서(skill)와 비교한다. treeIdx 변수에는 이전 스킬의 순서(인덱스)가 들어있다.
3. 첫 번째 조건은 현재 스킬순서가 treeIdx보다 작을때이다. 대신, -1인 경우는 제외했다.(뒷 순서 스킬들을 안찍을수도 있으므로)
4. 두 번째 조건은 현재 스킬을 찍는데 treeIdx가 -1(없는)인 경우이다. 중간스킬이 생략된 경우로 역시 제외한다.

 

🖇 리뷰

간결하면서도 직관적인 더 좋은 풀이가 있었다. String 값을 변수화해서 적절한 메서들을 사용하는 중요성을 다시금 느꼈다.

function solution(skill, skill_trees) {
    let count = 0;
    for(let i=0;i<skill_trees.length;i++){
        const str = skill_trees[i].split("").filter(element => skill.includes(element)).join("");
        if(str === skill.substring(0,str.length)){
            count++;
        }
    }
    return count; 
}

1. 스킬트리들을 순회하며 str을 만든다. 우선, 배열 메서드 활용을 위해 split(String화), join(Array화) 메서드들을 썼다.
2. str은 각 트리에서 skill에 포함된(스킬순서를 고려해야 하는) 요소들만 필터링한 String이다.
3. 이 str과 skill을 비교해서 같으면 순서가 같은 것이다. 뒷 스킬들을 안찍는 경우를 생각해서 skill을 str의 길이만큼 잘랐다.(substring)

---

👊 2.10(수) / 프린터

📜 문제

 

🧮 풀이

function solution(priorities, location) {
  let printReady = priorities.map((prior, index) => [prior, index])
  let printOrder = 1;
  while (printReady.length !== 0) {
    const printNow = printReady.shift();
    if (printReady.some(ready => ready[0] > printNow[0])) {
      printReady.push(printNow)
    }
    else {
      if (printNow[1] === location) {
        break;
      }
      else {
        printOrder++;
      }
    }
  } 
  return printOrder
}

1. 프린터 순위배열(priorities)을 [순위값, 인덱스] 배열(printReady)로 재구성(map)했다. 추후 location 인덱스와 비교 위함
2. 프린터 순서(printOrder)가 우리가 반환할 answer 값이다. n번째 개념이므로, 0이 아닌 1로 시작했다.
3. while 반복문을 활용했다. (printReady 가 빌 때까지) 매 반복에서, printReady의 첫 번째 요소(printNow)를 활용한다.
4. some() 메서드를 통해, printNow 우선순위와 printReady에 남은 요소들의 우선순위를 비교했다. true라면, 이를 다시 push()
5. false라면 현재 printNow가 출력된다. 여기서 인덱스와 location을 비교해서, 일치하면 반복문을 종료한다.(break)
6. 일치하지 않는다면, printOrder에 1을 더하고 반복문을 지속한다. 일치할 때 까지, 이 순서값이 증가할 것이다.

 

🖇 리뷰

월, 화에 비하면 난이도가 낮은 편이고, 정답을 바로 맞출 수 있었다. 문제를 풀면서, 나만의 알고리즘 원칙 2번을 정했다.

(원칙 1번은 단순 반복문/조건문보단 메서드를 활용하자)

 

순위값 비교에서, some()을 쓰든 every()를 쓰든 문제는 없었다. 하지만, 문제가 더 높은 값이 하나라도 존재할 경우(true)로 명시했다.

또한, printOrder를 숫자보다, 인쇄된 printNow들을 배열로 모아놓을까 고민도 했다. (직관적이고, 순서말고 순위값 등 다양한 반환가능)

하지만, 문제에서 요구한 나의 location에 대한 순서값만 필요하므로, printOrder 변수에 숫자만 저장하여 메모리 소모를 최소화했다.

 

즉, 원칙 2번은 문제의 내용과 요구에 충실한 풀이방법을 설계하는 것이다.

필요 이상의 메모리 소모가 없어질 뿐더러, 변수명과 자료형들을 통해 문제내용이 유추가 될 정도의 싱크로를 추구해보고자 한다.

---

👊 2.11(목) / 

📜 문제

 

🧮 풀이

function solution(priorities, location) {
  let printReady = priorities.map((prior, index) => [prior, index])
  let printOrder = 1;
  while (printReady.length !== 0) {
    const printNow = printReady.shift();
    if (printReady.some(ready => ready[0] > printNow[0])) {
      printReady.push(printNow)
    }
    else {
      if (printNow[1] === location) {
        break;
      }
      else {
        printOrder++;
      }
    }
  } 
  return printOrder
}

1. 프린터 순위배열(priorities)을 [순위값, 인덱스] 배열(printReady)로 재구성(map)했다. 추후 location 인덱스와 비교 위함
2. 프린터 순서(printOrder)가 우리가 반환할 answer 값이다. n번째 개념이므로, 0이 아닌 1로 시작했다.
3. while 반복문을 활용했다. (printReady 가 빌 때까지) 매 반복에서, printReady의 첫 번째 요소(printNow)를 활용한다.
4. some() 메서드를 통해, printNow 우선순위와 printReady에 남은 요소들의 우선순위를 비교했다. true라면, 이를 다시 push()
5. false라면 현재 printNow가 출력된다. 여기서 인덱스와 location을 비교해서, 일치하면 반복문을 종료한다.(break)
6. 일치하지 않는다면, printOrder에 1을 더하고 반복문을 지속한다. 일치할 때 까지, 이 순서값이 증가할 것이다.

 

🖇 리뷰

월, 화에 비하면 난이도가 낮은 편이고, 정답을 바로 맞출 수 있었

 

---

👊 2.12(금) / 124 나라의 숫자

📜 문제

🧮 풀이

function solution(n) {
  let arrRef = [1, 2, 4];
  let arrAns = [];
  while(n !== 0) {
    const num = n - 1;
    const q = Math.floor(num / 3)
    const r = num % 3;
    arrAns.unshift(arrRef[r])
    n = q
  }
  return arrAns.join("");
}

1. 인덱스값으로 대칭시킬 arrRef 배열을 선언한다. arrAns는 정답을 모을 배열이다. (unshift 앞으로 넣어야 해서)
2. 진법 풀이와 유사하다. 숫자(n)를 몫으로 최신화하면서, 나머지가 해당 자릿수 값이 되는 것이다.
3. 여기서 n-1을 하는 이유는, 이 숫자는 진수와 다르게 0이 아닌 1부터 시작했다. 처음에 -1을 줄여서 대칭시켜야 한다.
4. 그 다음, 몫(q)에서도 유사하다. 몫은 1이 나오겠지만, 이는 인덱스값으로 활용되기 위해 0으로 만들어주는 것이다.
5. 이렇게 모인 나머지값들(arrAns) 을, join 메서드를 통해 한글자로 묶어서 반환한다.

 

🖇 리뷰

막연하게, -1 을 주어야겠다는 생각이 들었고, 바깥과 반복문 안쪽에서 순서를 바꿔가면서 주었다.

반복문 안의 최상위에 위치하는 것이 맞았고, 그 이유를 곰곰히 생각해보니 위처럼 처음과 이후가 조금 다른 것을 알았다.

우연히 풀게 되었지만, 그 이유를 고심하면서 리뷰를 쓰도록 하자!