230221 프로그래머스 롤케이크 자르기

매일 매일 하루 한 문제씩.
꾸준히 이어가는 코딩테스트 풀이 기록 ✅

프로그래머스 롤케이크 자르기 자바, 자바스크립트.
오늘 코테를 풀면서 '효율성'을 개선하지 못하는 스스로에 굉장히 자신감이 떨어지고 있다는 점을 알았다.
그래서 오늘은 그냥 과감히 시간초과가 나는 코드를 먼저 만들어보는데 집중했다. 그리고 빠르게 다른 사람의 코드를 봤다.

여전히 길을 잃은 느낌이지만 이렇게 해야 막혀있는 벽에라도 계속 부딪히고 부딪혀서 무너뜨릴 수 있을 것 같다.

---

문제 링크

롤케이크 자르기

---

Java

처음에 자바스크립트로 먼저 풀었기에 자바는 약간 쉬운편이었다.
자바와 자바스크립트를 넘나들면서 Map, Set 자료구조가 조금씩 헷갈리기 시작했는데 자료구조는 이미 결제해둔 인강이 있으니 좀 반복적으로 보면서 상기시켜야겠다.

참, 어제 새롭게 알았던 getOrDefault() 메서드를 다시 한번 사용해봤다. 은근히 편한듯.

import java.util.*;

class Solution {
    public int solution(int[] topping) {
        int answer = 0;

        Map<Integer, Integer> toppings = new HashMap<>();

        for (int item : topping) {
            toppings.put(item, toppings.getOrDefault(item, 0) + 1);
        }

        Map<Integer, Boolean> brother = new HashMap<>();

        for (int item : topping) {
            toppings.put(item, toppings.get(item) - 1);

            brother.put(item, true);

            if (toppings.get(item) == 0) {
                toppings.remove((item));
            }

            if (toppings.size() == brother.size()) {
                answer += 1;
            }

            if (toppings.size() < brother.size()) {
                break;
            }
        }

        return answer;
    }
}

---

JavaScript

시간초과 코드를 먼저 작성했다.

function sliceCake(topping) {
  const slices = {};
  for (let i = 0; i < topping.length - 1; i += 1) {
    slices[i] = {
      me: new Set(topping.slice(0, i + 1)).size,
      brother: new Set(topping.slice(i + 1, topping.length)).size,
    };
  }

  return slices;
}

function solution(topping) {
  let answer = 0;

  const slices = sliceCake(topping);

  for (let i = 0; i < topping.length - 1; i += 1) {
    if (slices[i].me === slices[i].brother) {
      answer += 1;
    }
  }

  return answer;
}

그리고 다른 분의 블로그를 참고해 작성한 코드.
문제 조건을 보면 10만까지 범위로 설정되어 있기 때문에 중첩문이 나오게 되면 반드시 시간초과가 난다고 한다.
어쨌든 처음에 slice로 풀고 이를 set 자료구조로 전환하면 모든 경우의 수를 다 고려해야 하기 때문에 시간초과가 날 수 밖에 없다고 생각했고 예상이 맞았다.

이런 유형의 문제를 풀 때는 한 쪽에 몰빵(?)을 해주고 하나씩 빼고 더해가면서 경우의 수를 비교하다가 역전이 되는 순간 break를 하면 모든 경우의 수를 탐색하지는 않아도 되므로 시간초과가 나지 않게 되는 것 같다.

function solution(topping) {
  let answer = 0;

  const allToppings = new Map();
  const brother = new Map();

  topping.forEach((item) => {
    allToppings.set(item, (allToppings.get(item) || 0) + 1);
  });

  for (const i of topping) {
    allToppings.set(i, allToppings.get(i) - 1);

    brother.set(i, true);

    if (!allToppings.get(i)) {
      allToppings.delete(i);
    }

    if (allToppings.size === brother.size) {
      answer += 1;
    }

    if (allToppings.size < brother.size) {
      break;
    }
  }

  return answer;
}

어제 10년차 FE 개발자와 인터뷰를 할 일이 있었는데,
한껏 마음이 꺾이고 포기 상태의 나에게 마음에 다가오는 말씀을 해 주셨다.

'개발자로서의 성장을 멈추지 말라'

곱씹을수록 중요한 말인 것 같다.
취준생의 포지션에 갇혀 시야가 많이 좁아져있었던듯...

조금 더 힘내보자.