✏️ 백준 - 과제(13904번)

점수를 기준으로 내림차순 정렬을 하는 것이 포인트!

💭 코드 설계

1. N으로 과제의 개수를 저장하고, works 배열에 2차원 배열로 각 과제별 마감일과 점수를 저장한다.
2. works 배열을 점수를 기준으로 내림차순 정렬하여 sortedWorks 배열로 저장한다.
3. plan 배열을 과제의 개수만큼 크기를 지정하고, 0으로 초기화한다.
4. sortedWorks 배열에서 순서대로 가져오면서 index에 "마감일 - 1"을 저장한다. plan[index]의 값이 0이면 해당 index에 과제의 점수를 넣는다. 0이 아니라면, index가 0이 되거나, plan[index]의 값이 0일때까지 index 값을 줄여나간다. plan[index]의 값이 0이라면 과제의 점수를 넣고 break한다.
5. plan에 저장된 값들을 모두 더한다.

🅰️ 제출한 답

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n")
  .map((el) => el.split(" "));

  const N = Number(input[0][0]);
  let works = input.slice(1, N + 1).map((row) => row.map(Number));
  const sortedWorks = works.sort((a, b) => b[1] - a[1]);

  let plan = Array(N).fill(0);

  sortedWorks.forEach((work) => {
    let index = work[0]-1;
    if(plan[index] === 0){
      plan[index] = work[1];
    }else{
      while(index >= 0){
        if(plan[index] === 0){
          plan[index] = work[1];
          break;
        }else{
          index--;
        }
      }
    }
  })

  console.log(plan.reduce((acc, cur) => acc+cur, 0));

💡 해설

🤔 소감

✏️ 백준 - 3차원 막대기 연결하기(19950번)

다각형의 변의 길이 조건을 적용하는 것이 포인트!

💭 코드 설계

1. N으로 막대기 개수, start로 시작점, end로 끝점, lines 배열로 막대기들의 길이를 저장한다.
2. 시작점과 끝 점 사이의 거리를 계산하여 distance에 저장한다. (피타고라스 정리를 활용한다.)
3. 만약 막대기가 1개라면, distance와 막대기의 길이가 같아야만 한다.
4. 막대기가 2개 이상이라면, distance를 포함한 가장 긴 변의 길이가 나머지 길이의 합보다 작거나 같아야한다. 따라서 distance를 lines 배열에 넣고, max에 최댓값을 저장한 다음, 최댓값을 뺀 나머지 값들의 합을 최댓값과 비교한다.

🅰️ 제출한 답

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n")
  .map((el) => el.split(" "));

  // 막대기 1개 = 점과 점 사이의 거리(선)
  // 막대기 2개 이상: 가장 긴 변의 길이 <= 나머지 길이의 합

  const N = Number(input[1][0]); // 막대기 개수

  const start = input[0].slice(0, 3).map(Number); // 시작점
  const end = input[0].slice(3, 6).map(Number); // 끝점
  const lines = input[2].map(Number); // 막대기들

  const distance = Math.sqrt((end[0] - start[0]) **2 + (end[1] - start[1])**2 + (end[2] - start[2])**2);

  if(N === 1){
    if(lines[0] === distance){
      console.log("YES");
    }else{
      console.log("NO");
    }
  } else{
    lines.push(distance);
    const max = Math.max(...lines);
    const restLines = lines.filter((line)=> line !== max);
    const restSum = restLines.reduce((acc, cur) => acc+cur, 0);

    if(max <= restSum){
      console.log("YES");
    }else{
      console.log("NO");
    }
  }

💡 해설

🤔 소감

백준 - 팔(1105번)

자리수를 비교하는 것이 포인트인 문제이다.

코드 설계

문제 해결의 단계는 아래와 같다.

1. L로 최솟값, R로 최댓값을 받고, 각 자리의 숫자를 비교하기 위해 string으로 변환한다.
2. counter 변수를 통해 8의 최소 개수를 셀 것이다. 0으로 초기화한다.
3. L과 R의 자리수가 다르면 0을 출력한다.
4. 자리수가 같을 경우 자리수만큼 반복한다. 이때 L과 R의 각 자리의 숫자가 같으면서 그 숫자가 8이면 counter를 하나 증가한다. L과 R의 각 자리의 숫자가 다를경우 반복문을 종료한다.
5. counter 값을 출력한다.

제출한 답

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split(/\s+/) // \s: 공백 문자, + : 하나 이상 연속 된 경우
  .map(Number);

  const L = input[0].toString();
  const R = input[1].toString();

  let counter = 0;
  if(L.length != R.length){
    console.log(counter);
  }else{
    for(let i=0; i<L.length; i++){
      if(L[i] === R[i] && L[i] == 8){
        counter++;
      }else if(L[i] != R[i]){
        break;
      }
    }
    console.log(counter);
  }

시행착오

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split(/\s+/) // \s: 공백 문자, + : 하나 이상 연속 된 경우
  .map(Number);

  const L = input[0].toString();
  const R = input[1].toString();

  let counter = 0;
  if(L.length != R.length){
    console.log(counter);
  }else{
    for(let i=0; i<L.length; i++){
      if(L[i] != R[i])
        break;
      counter++;
    }
    console.log(counter);
  }

처음에는 단지 자릿수 비교, 각 자리의 숫자 비교해서 같거나 다를 경우에 대해서만 코드를 작성했다. 이 경우 180 189와 같은 입력값이 들어왔을 때는 2를 출력한다. 그 이유는 8과의 비교를 놓쳤기 때문이다.

💡한줄평
일주일 간 일본 여행을 끝내고 오랜만에 돌아와서 문제풀이를 진행중이다. 다시 열심히 공부할 것이다.

백준 - 로프(2217번)

저번에 풀었던 백준- 온라인 판매(1246번)과 비슷한 유형의 문제이다.

코드 설계

문제 해결의 단계는 아래와 같다.

1. N으로 로프의 갯수를 받고, rope 배열에 각 로프가 버틸 수 있는 최대 중량을 저장한다.
2. 로프 배열을 오름차순으로 정렬한다.
3. maxWeight 배열을 N번 반복하며 각 로프의 중량에 따른 물체의 최대 중량을 저장한다.
4. maxWeight 배열의 최댓값을 출력한다.

제출한 답

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split(/\s+/) // \s: 공백 문자, + : 하나 이상 연속 된 경우
  .map(Number);

  const N = input[0];
  let rope = input.slice(1, N+1)
  rope = rope.sort((a,b)=>b-a); // 오름차순
//   console.log(rope);

let maxWeight = [];

for(let i=0; i<N; i++){
    // maxWeight[i] = rope[i] * (rope.filter(arg => arg <= rope[i]).length);
    maxWeight[i] = rope[i] * (i+1);
}
// console.log(maxWeight);

console.log(Math.max(...maxWeight));

💡한줄평
비슷한 유형의 문제를 한 번 풀고나니 이 문제를 푸는 것은 쉬웠다. 스터디에서 그 유형과 비슷한 문제인 것 같으니 비슷한 방식으로 풀어보는 것이 어떻냐는 의견을 참고했다. 나 혼자 풀었으면 조금 헤맸을지도..

백준 - 1로 만들기(1463번)

문제는 간단하지만 푸는 방법을 고민하는 것이 어려웠다. 스스로 풀지 못하고 다른 사람들의 풀이를 참고하여 풀었다. DP 방법을 사용했다. 동적 계획법(Dynamic Programming, DP)은 문제를 작은 하위 문제로 나누고, 그 결과를 저장하여 전체 문제를 해결하는 방법이다. 즉, 중복 계산을 줄여 효율적으로 문제를 해결하는 기법이다.

코드 설계

문제 해결의 단계는 아래와 같다.

1. N으로 숫자를 입력받는다. dp 배열을 생성하여 N개만큼 0으로 초기화한다.
2. 1은 이미 0으로 초기화되었으므로, 2부터 N까지 돌면서 연산의 최솟값을 구해 초기화한다.
3. -1을 하는 조건은 항상 실행될 수 있으므로 기본적으로 실행하여 -1을 했을때의 연산횟수와 2를 나눴을때의 연산 횟수, 3을 나눴을 때의 연산횟수를 비교하며 각 숫자의 최소 연산횟수를 배열에 채워나간다.

제출한 답

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split(/\s+/)
  .map(Number);

const N = input[0];
const dp = new Array(N + 1).fill(0);

// dp[1] = 0 (이미 초기화됨)
for (let i = 2; i <= N; i++) {
  dp[i] = dp[i - 1] + 1; // 항상 1을 빼는 경우 고려
  if (i % 2 === 0) dp[i] = Math.min(dp[i], dp[i / 2] + 1);
  if (i % 3 === 0) dp[i] = Math.min(dp[i], dp[i / 3] + 1);
}

console.log(dp[N]);

💡한줄평
스스로 풀어내지 못한 첫 번째 문제라 좀 답답했다. 다른 사람들의 풀이 방식을 보니 정말 간단한 방법인데 이걸 생각해내지 못한 것이 아쉽다. 그래도 DP라는 방식에 대해서 알아보는 시간을 가진 것 같아서 의미있었다. 다음에 비슷한 문제를 풀어봐야겠다.

백준 - 온라인 판매(1246번)

생각보다 문제가 굉장히 까다롭고 복잡하다. 이 문제에서의 포인트는 아래 세 가지 조건이다.

1. A가격에 달걀을 판다고 하면 Pi가 A가격보다 크거나 같은 모든 고객은 달걀을 산다.
2. 달걀 총 수량을 초과하여 팔 수 는 없다
3. 최대 수익을 올릴 수 있는 달걀의 가장 낮은 가격을 책정하는 것이다

코드 설계

문제 해결의 단계는 아래와 같다.

1. 달걀의 개수를 N, 고객의 수를 M으로 받고, 고객이 제시한 금액은 consumer 배열로 받는다.
2. consumer 배열을 오름차순 정렬한다.
3. total 배열을 초기화한다. 이 배열은 각 금액에 구매 가능한 고객의 수를 곱하여 모든 케이스의 수익을 저장한다.
4. 고객의 수 만큼 반복한다.counter로 현재 제시된 금액보다 크거나 같은 가격의 수를 측정한다. 즉, counter가 해당 금액에 판매 가능한 고객의 수가 된다. 이때, counter의 크기가 N보다 작으면 total 배열에 0을 저장한다. 판매가 불가능 하기 때문이다.
5. maxTotal에 total 배열의 최댓값 즉, 수익의 최댓값을 저장한다. maxIndex에 통해 해당 최댓값의 index 값을 저장하고 이를 이용하여 maxPrice에 달걀의 가격을 책정한다.

코드 설계 2번 단계가 중요하다. 조건 3번째에서 달걀의 가장 낮은 가격을 책정한다 했다. 오름차순으로 정렬을 해야 달걀의 가격과 그 가격에 알맞은 수량을 곱해서 total에 저장할 경우 findIndex 함수는 앞에서부터 찾기 때문에 max값과 동일한 경우, 가격이 낮은 것을 선택할 수 있다.

제출한 답

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split(/\s+/) // \s: 공백 문자, + : 하나 이상 연속 된 경우
  .map(Number);

  const N = input[0];
  const M = input[1];

  consumer = input.slice(2, 2+M);
  consumer = consumer.sort((a,b)=>a-b);

  let total = [];

  for(let i=0; i<M; i++){
    let counter = consumer.filter((arg) => arg >= consumer[i]).length;
    if(counter <= N)
      total[i] = consumer[i] * counter;
    else
      total[i] = 0;
  }

  const maxTotal = Math.max(...total);
  const maxIndex = total.findIndex(arg => arg===maxTotal);
  const maxPrice = consumer[maxIndex];


  console.log(maxPrice + " " + maxTotal);

💡한줄평
이 문제는 생각보다 말장난이 많았던 것 같다. 얼핏 보기엔 간단해보이지만 왠지 모르게 정답을 이끌어내기가 어려웠다. 테스트 케이스가 1개밖에 없는 것도 큰 이유로 작용했던 것 같다. 테스트 케이스를 직접 생각해보는 시간도 필요한 것 같다.

백준 - 국회의원 선거(1417번)

이 문제는 결국 반복하며 최댓값을 찾는 문제이다.

코드 설계

문제 해결의 단계는 아래와 같다.

1. 국회의원 후보의 수를 N으로 받는다.
2. 다솜이의 득표 수를 dasom으로 받고, 나머지 득표 수를 vote 배열로 저장한다.
3. counter 변수를 0으로 초기화한다.
4. while 반복을하며 vote 배열에서의 최댓값을 구한다. 최댓값을 max로, 최댓값의 위치를 index에 저장한다.
5. max가 dasom보다 크거나 같으면 최댓값에서 1을 뺀 후, dasom에 1을 더하고 counter를 증가시킨다.
6. max가 dasom보다 작으면, 반복문을 빠져나와 counter 값을 출력한다.

제출한 답

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n")
  .map(Number);

  const N = input[0];
  let dasom = input[1];
  let vote = input.slice(2, N+1);

  let counter = 0;

  while(true){
    let max = Math.max(...vote);
    let index = vote.findIndex(arg => arg === max);

    if(max < dasom)
      break;
    else{
      vote[index]--;
      dasom++;
      counter++;
    }
  }

  console.log(counter);

💡한줄평
이 문제를 스터디 시간에 간단하게 브레인스토밍을 통해 설계를 하는 과정에서 팀원 한 명이 최대히프 정렬을 사용해보는 것이 어떻냐는 말을 했었다. 직전학기 수업에서 배웠던 알고리즘을 떠올렸던 것이다. 그 말을 듣고 처음에는 최대 히프를 사용해서 해보려했으나 간단한 문제였기 때문에 코드가 더 복잡해진다는 생각이 들어 배열에서 최댓값을 구하는 방식으로 문제풀이를 했다. 그러나 최대히프 정렬이 조금 더 시간 단축엔 도움이 될 것 같다.

백준 - 크게 만들기(2812번)

정답 비율에 겁먹지 말자는 생각으로 선정하게 된 문제이다. 다양한 방법을 시도해보았으나 스택으로 풀이하는 문제였다.

코드 설계

문제 해결의 단계는 아래와 같다.

1. N으로 숫자의 길이, K로 지워야할 숫자의 갯수를 받는다.
2. numArr에 숫자를 한자리씩 배열로 저장한다.
3. counter로 지워야할 남은 갯수를 센다. 초기값은 K로 설정한다.
4. stack 배열을 생성한다.
5. numArr에 있는 digit의 갯수 동안 반복한다.
6. 이때 stack의 길이가 0보다 크고, stack의 마지막 요소가 새로 들어올 digit보다 작으면서 counter가 0보다 크다면 stack에서 pop을 하며 counter를 감소시킨다.
7. 만약 하나라도 만족하지 않는다면 digit값을 stack에 push한다.
8. stack에 남은 갯수가 지워져야할만큼(N-K만큼) 지워지지 않았다면, 반복하며 pop을 통해 지운다.

제출한 답

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n")
  .map((el) => el.split(" "));

  const N = Number(input[0][0]);
  const K = Number(input[0][1]);

  let counter = K;
  let numArr = Array.from(input[1][0]);
  let stack = [];

  for(let digit of numArr){
    while(stack.length && stack[stack.length - 1] < digit && counter){
        stack.pop();
        counter--;
    }
    stack.push(digit);
  }

    while(stack.length > N-K){
        stack.pop();
    }

  console.log(stack.join(''));

시행착오 1

처음 생각했던 방식은 처음 숫자부터 K번째의 숫자까지 중에서 가장 작은 값을 선택하여 삭제하는 방식을 택했다. 예를들어 입력값이

4 2
1924

로 들어온다면 [1,9,2,4] 중에서 첫번째 숫자를 제외한 제일 앞 두자리인 [1, 9, 2] 중에서 가장 작은 수인 1을 삭제한다. 아직 삭제할 횟수가 남았으므로 [9, 2, 4] 중 [9, 2] 중 가장 작은 수인 2를 삭제한다. 그러면 최종적으로 [9, 4]가 남게된다.

이 방식은 예제로 제시된 3가지는 통과하였으나 반례를 더 찾아본 후 옳지 않은 방법임을 알아차렸다. 이 방법의 반례는 아래와 같다.

9 3
543211211

일 경우 541211 가 나온다.

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n")
  .map((el) => el.split(" ").map(Number));

  const N = input[0][0];
  const K = input[0][1];
  let num = String(input[1][0]);
  let numArr = Array.from(num, (el)=>Number(el));

  let len = num.length;
  let end = K;

  while(len > N-K){
    if(end > len){
      numArr.splice(0, 1);
      len--;
      end = K;
    }
    let newNum = numArr.slice(0, end);
    let min = Math.min(...newNum);
    let max = Math.max(...newNum);
    if(min === max){
      end++;
      continue;
    }
    for(let j=0; j<N; j++){
      if (newNum[j] === min){
        numArr.splice(j, 1);
        len--;
        end = K;
        break;
      }
    }
  }

  console.log(Number(numArr.join('')));

시행착오 2

두 번째 생각한 방식은 현재 숫자보다 큰 숫자가 뒤에 있을 경우 삭제하는 방식이다. 예를들어 입력값이

4 2
1924

라면 i=0일 때 i번째 자리는 1이다. 그럼 현재 삭제가능한 횟수가 2번이므로 1을 제외한 2자리인 [9, 2] 중 큰 수가 9이고, 9가 i번째 자리인 1보다 크므로 1을 삭제한다.

이 방법은 반례가 없었으나 메모리 초과로 인해 위에서 언급한 스택으로 문제 풀이를 하였다.

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n")
  .map(el => el.split(" "));
//   .map((el) => el.split(" ").map(Number));

  const N = Number(input[0][0]);
  const K = Number(input[0][1]);
  const num = input[1][0];
  let numArr = Array.from(num);
  let len = numArr.length;
  let count = 0;

  for(let i = 0; i<N; i++){
    if(count === K)
        break;
    tempArr = numArr.slice(i+1, i + 1 + K-count); 
    let max = Math.max(...tempArr);
    if(numArr[i] < max){
        numArr.splice(i,1);
        len--;
        count++;
        i--;
    }
  }
  if(count != K){
    numArr.splice(-(K-count), (K-count));
  }

  console.log(numArr.join(''));

이때 중요했던 부분이 처음에는 아래 코드에서와 같이 배열을 숫자로 정하고 풀었는데 수의 자리수가 커지면 오버플로우로 제대로 값이 나오지 않는 경우가 발생하였다. 그래서 숫자를 문자열로 두고 최종 출력에서 join을 통해 문자열을 붙여서 숫자처럼 출력했다.

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n")
  .map((el) => el.split(" ").map(Number));

  const N = input[0][0];
  const K = input[0][1];
  const num = String(input[1][0]);
  let numArr = Array.from(num, (el)=>Number(el)); // 숫자 배열 생성
  let len = numArr.length;
  let count = 0;

  for(let i = 0; i<N; i++){
    if(count === K)
        break;
    tempArr = numArr.slice(i+1, i + 1 + K-count); 
    let max = Math.max(...tempArr);
    if(numArr[i] < max){
        numArr.splice(i,1);
        len--;
        count++;
        i--;
    }
  }
  if(count != K){
    numArr.splice(-(K-count), (K-count));
  }

  console.log(Number(numArr.join('')));

문제에서 주어지는 숫자가 최대 500,000자리까지 될 수 있는데, 입력받을 때 이미 .map((el) => el.split(" ").map(Number))를 사용해서 숫자형으로 변환하고 있다. 이 경우 15~16자리 이상의 정수는 자바스크립트의 Number(IEEE‑754 64비트 부동소수점)로 표현할 때 정밀도가 깨져서 잘못된 값이 된다. 예를 들어, 아래와 같이 20자리 이상의 숫자가 주어지는 경우,

20 1
12345678901234567890

2345678901234567890 가 되어야 한다. 그러나 이 코드가 출력하는 결과는 2345678901234567000이다.

💡한줄평

이 문제를 풀며 조금 방황했다. 위에서 보았듯이 두 가지 시행착오를 거치며 꽤 오랜 시간을 소모했다. 그러나 그 시행착오를 통해 스택을 사용해야하는 타당한 이유를 찾을 수 있었고, 스택을 사용하는 과정에서 코드를 설계하는데 보다 짧은 시간을 들일 수 있었다. 역시 실패없는 배움은 없는 것 같다.

백준 - 짐 챙기는 숌(1817번)

문제

• 숌은 짐을 챙겨서 겨울캠프에서 집으로 가려고 한다. 근데 숌은 공부를 많이 하러 캠프에 온 것이기 때문에 책을 엄청나게 많이 가지고 왔다. 숌은 이 책을 방에 탑처럼 쌓아 놨다.
• 숌은 책을 박스에 차곡차곡 넣어서 택배로 미리 보내려고 한다. 책은 탑처럼 차곡차곡 쌓여있기 때문에, 차례대로 박스에 넣을 수밖에 없다.
• 각각의 책은 무게가 있다. 그리고 박스는 최대 넣을수 있는 무게가 있다. 숌이 필요한 박스의 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 책의 개수 N과 박스에 넣을 수 있는 최대 무게 M이 주어진다. N은 0보다 크거나 같고 50보다 작거나 같은 정수이고, M은 1,000보다 작거나 같은 자연수이다.
• N이 0보다 큰 경우 둘째 줄에 책의 무게가 공백을 사이에 두고 주어진다. 책의 무게는 M보다 작거나 같은 자연수이다.

  출력

• 첫째 줄에 필요한 박스의 개수의 최솟값을 출력한다.

이 문제는 다음에 올 책의 무게를 고려하는 것이 포인트이다.

코드 설계

문제 해결의 단계는 아래와 같다.

1. 책의 갯수를 N으로, 최대 무게를 M으로 받는다.
2. 각 책의 무게를 배열 books로 받는다.
3. 박스의 갯수를 counter로 하여 초기값을 1로 준다.
4. sum과 nextSum으로 현재 박스의 총 책의 무게의 합과 다음 책의 무게의 합을 계산한다.
5. N만큼 루프를 돌며 현재 책의 무게가 최대무게인 M이랑 같아지면 counter를 증가하고, sum과 nextSum의 값을 초기화한다.
6. 다음 책의 무게를 미리 재서 최대무게인 M을 초과하면 counter를 미리 증가하고, nextSum과 sum의 값을 초기화한다.
7. 이때 책의 갯수인 N값이 0개이면 0을 출력한다.

제출한 답

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n")
  .map((el) => el.split(" ").map(Number));


const N = input[0][0]; // 책의 갯수
const M = input[0][1]; // 최대 무게 M

const books = input[1];

let counter = 1;
let sum = 0;
let nextSum = 0;

for(let i=0; i<N; i++){
    if(sum === M){
        counter++;
        sum = 0;
        nextSum = 0;
    }
    sum += books[i];
    nextSum = sum + books[i+1];
    if(nextSum > M){
        counter++;
        nextSum = 0;
        sum = 0;
    }
}
if(N === 0)
    counter = 0;

console.log(counter);

💡한줄평
사실 이 문제는 한 번에 풀었다. 미리 설계를 하지 않고 예제를 하나씩 넣어가면서 때려맞추기를 했다. 그래서 그런지 코드가 깔끔하지 않고 개연성이 없는 것 같다. 시간관계상 우선 이렇게 풀고 넘어간다. 더 좋은 풀이를 고민하고 추가할 계획이다. 다음부터는 좀 여유를 가지고 문제를 풀이해야겠다.

백준 - 장신구 명장 임스(25496번)

문제

• 메이플스토리에는 전문 기술이라는 제작 시스템이 있다. 전문 기술은 특정량의 피로도가 쌓이는 대신 다양한 장비 및 비약을 제작할 수 있는 시스템이다. 장신구 명장인 임스는 어떻게 하면 더 효율적으로 많은 장신구를 제작할 수 있을지 고민에 빠졌다.

• 임스가 만들 수 있는 장신구는 $N$개가 있고, 각각의 장신구를 만들면 $A_i$만큼의 피로도가 누적된다.

• 피로도가 $200$ 미만인 경우, 장신구를 제작할 수 있다. 현재 쌓인 피로도가 $P$일 때, 임스가 제작할 수 있는 장신구의 최대 개수를 구해보자!

입력

• 첫 번째 줄에 정수 $P$와 정수 $N$이 공백으로 구분되어 주어진다. ($1 \le P \le 200$, $1 \le N \le 1,000$)

• 두 번째 줄에는 정수 $A_1, A_2, \dots, A_N$이 공백으로 구분되어 주어진다. ($1 \le A_i \le 200$)

  출력

  제작할 수 있는 장신구의 최대 개수를 출력하시오.

이 문제는 배열 A를 오름차순 정렬하는 것이 포인트이다.

코드 설계

문제 해결의 단계는 아래와 같다.

1. 피로도를 변수 P로, 장신구의 갯수를 변수 N으로 입력받는다.
2. 각각의 장신구의 피로도를 배열 A로 입력받는다.
3. 배열 A를 오름차순 정렬한다.
4. P가 200 미만이면서 장신구의 갯수만큼 반복한다.
5. 반복한 횟수를 index에 저장하여 출력한다.

제출한 답

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int asc(const int* a, const int* b) {
    return *a - *b; // 오름차순
}

int main() {
    int P, N;
    scanf("%d %d", &P, &N);

    int A[1000];
    for (int i = 0; i < N; i++) {
        scanf("%d", &A[i]);
    }

    qsort(A, N, sizeof(int), asc);

    int index = 0;

    while (P<200 && index<N) {
        P += A[index++];
    }

    printf("%d", index);
}

시행착오

• C에서 오름차순, 내림차순 함수를 사용하는 것은 백준 - 보물(1026번) 글에서 사용 및 설명한 적이 있다.

오답

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int asc(const int* a, const int* b) {
    return *a - *b; // 오름차순
}

int main() {
    int P, N;
    scanf("%d %d", &P, &N);

    int A[1000];
    for (int i = 0; i < N; i++) {
        scanf("%d", &A[i]);
    }

    qsort(A, N, sizeof(int), asc);

    int index = 0;

    while (P<200) { // while (P<200 && index<N)
        P += A[index++];
    }

    printf("%d", index);
}

처음 시도에서는 index의 값이 장신구의 갯수인 N회를 넘어가는 것을 고려하지 못하여 틀렸었다. 이러한 반례를 찾아 수정하였다.

💡한줄평
JS와 권태기인지 자꾸 하기 싫어져서 문제풀이를 스터디 당일까지 최대한 미루다가 푸는 중이다. 그래서 이제는 언어에 제한을 두거나 부담을 가지지 않고 우선 문제 풀이 자체에 친숙해지는 연습을 먼저 하려고 한다. 차차 연습하고 노력하다보면 분명히 성장하는 날이 올 것이다!

하루에 한 번씩 강연을 해주시는 졸업생 선배님들이 계셨는데 하나같이 코딩테스트를 미리 대비하는 것에 대한 중요성을 언급하셨다.

이를 위해 현장에서 팀원을 결성하여 스터디를 만들었다.

혼자서 대비하는 것보다 서로 응원해주며 새로운 문제풀이 방법을 공유할 수 있는 좋은 기회라고 생각되었기 때문이다.

또한 그냥 문제를 풀이하는 것보단 기록으로 남기는 것이 의미있다고 생각하여 블로그도 시작하게 되었다.

우리의 규칙은 아래와 같다.

1. 일주일에 두 번 진행한다.
2. 공통된 문제를 풀이한다. 단, 언어의 제한은 없다. 나는 C, Js를 번갈아가며 진행할 계획이다.
3. 미리 정해서 풀어온 문제에 대한 풀이 설명을 30분간 진행한다.
4. 이후 30분간 현장에서 정한 문제를 다같이 풀이한다.

따라서 일주일에 총 4개의 공통된 문제를 풀고, 풀이를 공유할 수 있다.

프로그래밍 문제에 익숙해지는 과정동안은 따로 알고리즘을 공부하며 풀지 않고 기본적인 문제풀이만 진행한다. 익숙해지는 여름방학부터 알고리즘을 공부하며 관련 문제를 풀어나갈 계획이다.

백준 - 동전 0(11047번)

문제

• 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.
• 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

  출력

• 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

동전이 오름차순으로 주어지기 때문에 따로 재배열할 필요가 없다.

코드 설계

문제 해결의 단계는 아래와 같다.

1. 동전의 가짓수를 N으로 입력받는다.
2. 금액을 K로 입력받는다.
3. N만큼 반복하며 K를 각 금액으로 나눈 값을 합하고, K에 나머지를 저장하여 다시 반복한다.

제출한 답

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n")
  .map((el) => el.split(" ").map(Number));


  const N = input[0][0];
  let K = input[0][1];

  let num = 0;
  for(let i=N; i>0; i--){
    if(K === 0)
        break;
    if(K >= input[i][0]){
        num += Math.floor(K/input[i][0]);
        K %= input[i][0];
    }
  }

  console.log(num);

Js로 백준 풀기

이전 문제 풀이에서 언급했듯이 Js로 백준을 푸는 것은 꽤나 까다롭다. 그래서 계속 피해왔지만 그래도 풀어야한다. 이 글을 참고해서 문제를 풀었다. 혹시 Js로 문제풀이를 할 경우 참고하시길 바란다.

간략하게 설명하자면

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n")
  .map((el) => el.split(" ").map(Number));

백준은 리눅스 환경에서 실행된다. VSCode에서 실행을 위해 삼항연산자를 활용하여 input.txt 파일을 동일 디렉토리에 저장해 사용한다.

.toString()을 사용하여 입력값을 문자열로 받고, .trim()으로 공백을 제거한 후, .split("\n")으로 줄바꿈을 기준으로 문자열을 나눈다. .map()은 새로운 배열을 반환해주는 함수이다.

예를들어 해당 문제에서 입력이 아래와 같은 형식으로 들어온다.

10 4200
1
5
10
50
100
500
1000
5000
10000
50000

1. .toString()으로 해당 입력값들을 문자열로 변환한다.
2. .trim()으로 혹시 모를 공백을 제거한다.
3. .split("\n")으로 배열을 생성한다.

    [
      "10 4200",
      "1",
      "5",
      "10",
      "50",
      "100",
      "500",
      "1000",
      "5000",
      "10000",
      "50000"
    ]

4. .map()으로 각 문자열을 공백을 기준으로 분리하고 숫자로 변환한다.

   [
    [10, 4200],
    [1],
    [5],
    [10],
    [50],
    [100],
    [500],
    [1000],
    [5000],
    [10000],
    [50000]
   ]

기본적인 틀은 위와 같고 입력받는 값에 따라 잘 변환해서 사용하면 된다.

💡한줄평
역시 백준을 Js로 풀 때는 입력받는 것에 신경을 잘 써야하는 것이 번거롭고 어렵다. 이 부분으로 인해 두 번이나 오답이 발생했다. 더 익숙해지도록 노력해야겠다.

백준 - 보물(1026번)

문제

• 옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.

• 길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자. S = A[0] × B[0] + ... + A[N-1] × B[N-1] S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.

• S의 최솟값을 출력하는 프로그램을 작성하시오.

입력

• 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.

  출력

• 첫째 줄에 S의 최솟값을 출력한다.

이 문제에서 포인트는 하나의 배열을 오름차순, 다른 하나의 배열을 내림차순으로 정리한 후 각 인덱스의 배열끼리 곱해서 합하는 것이다.

코드 설계

문제 해결의 단계는 아래와 같다.

1. 수의 갯수를 N으로 입력받는다.
2. A 배열과 B 배열의 값을 입력받는다.
3. A 배열을 오름차순으로, B 배열을 내림차순으로 정렬한다.
4. 각 인덱스의 값끼리 곱하여 합한다.

제출한 답

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int asc(const int* a, const int* b) {
    return *a - *b; // 오름차순
}

int dsc(const int* a, const int* b) {
    return *b - *a; // 내림차순
}

int main() {
    int N;
    int A[50];
    int B[50];
    int S = 0;

    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d", &A[i]);
    }
    for (int i = 0; i < N; i++) {
        scanf("%d", &B[i]);
    }

    qsort(A, N, sizeof(int), asc);
    qsort(B, N, sizeof(int), dsc);

    for (int i = 0; i < N; i++) {
        S += (A[i] * B[i]);
    }

    printf("%d", S);
}

qsort() 함수

이번 코드에서는 정렬함수를 사용해서 문제를 해결했다.

우선 qsort() 함수를 사용하기 위해서는 <stdlib.h>를 import 해와야한다. 첫 번째 인자로는 정렬할 배열의 시작 주소를 넘겨준다. 두 번째 인자로는 요소의 갯수를 넘겨준다. 세 번째 인자로는 요소의 크기를 넘겨준다. 마지막 인자에는 정렬 기준을 세우는 함수를 넘겨주어야한다.

정렬 기준 함수라는 것은 쉽게 말하면 반환값이 양수이면 두 수의 자리를 바꾸고 음수이면 자리를 바꾸지 않는다. 문제 해결에서 사용한 코드를 예시로 설명하겠다.

    int asc(const int* a, const int* b) {
        return *a - *b; // 오름차순
    }

오름차순의 경우 a-b의 값이 양수(a>b)이면 두 수의 자리를 바꾼다. a는 b보다 큰 수 이면서 먼저 오는 수이므로 이 수가 뒤로가게된다. 반대로 a-b의 값이 음수(a<b)이면 두 수의 자리를 바꾸지 않는다. 이때는 작은 수가 앞에 있도록 고정된다. 이 과정을 반복하면서 큰수가 뒤로가게 되므로 자연스럽게 오름차순 정렬이 된다.

    int dsc(const int* a, const int* b) {
        return *b - *a; // 내림차순
    }

내림차순의 경우 오름차순과 반대로 생각하여 뒷 순서인 b-a의 값을 구하는 코드로 수정하면 된다.

💡한줄평
C언어로 문제를 푸는 것은 백준에서 JS로 문제를 푸는 것이 복잡하거니와 순전히 시간복잡도를 고려하지 않고 싶어서였다. 그러나 이 문제를 풀면서 정렬함수의 오름차순, 내림차순을 구현하기 위해 기준이 되는 함수를 만들어야되는 것에 피로감을 느꼈다. 또한, 프론트엔드 개발자를 희망하는 사람으로서 JS를 놓을 수는 없다. 다음 문제는 JS로 풀이해야겠다..

백준 - 단어 공부(11399번)

문제

• 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.
  • 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다. 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.
  • 줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.

• 줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

  출력

• 첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

이 문제에서 포인트는 오름차순으로 값을 누적해서 더하는 것이다.

코드 설계

문제 해결의 단계는 아래와 같다.

1. 사람의 수를 N으로 입력받는다. 이때 사람의 수는 1000이하이다.
2. 각 사람의 시간을 배열 P에 저장한다. 그와 동시에 check라는 배열을 0으로 초기화한다. 이 배열의 용도는 선택 여부이다.
3. check가 0인 사람의 시간 중 최솟값 min을 구한다. 이때 min은 반복문 내에서 시간의 최댓값인 1000으로 초기화한다.
4. 사람 수만큼 반복문을 돌면서 누적 값을 sum으로 설정하고 총 합계를 total로 설정하여 최종적으로 total을 출력한다.

제출한 답

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
    int N;
    int P[1000];
    int check[1000];
    int sum = 0;
    int total = 0;
    int count = 0;
    int index = 0;

    // 사람 수 받기
    scanf("%d", &N);

    // 각 사람에 따른 시간 받기 + check 배열 초기화
    for (int i = 0; i < N; i++) {
        scanf("%d", &P[i]);
        check[i] = 0;
    }

    while (count < N) {
        ++count;
        int min = 1000;
        for (int i = 0; i < N; i++) {
            if ((min > P[i]) && (check[i] == 0)) {
                min = P[i];
                index = i;
            }
        }
        check[index] = 1;
        sum += min;        
        total += sum;
    }

    printf("%d", total);
}

💡한줄평
이 문제를 푸는데 다른 문제에 비해 많은 시간을 들이지 않았다. C 사용에 익숙해진 것인지 이 문제가 쉬웠던 것인지는 아직 판단이 되지 않는다. C언어는 시간이 짧게 걸리는 것이 장점인 것 같다. 그러나 추후 오름차순 정렬하는 알고리즘을 학습한 후 빅오 계산법을 활용해서 비교해보고 싶다.

오랜만에 C언어로 문제를 풀어서 그런지 언어 사용하는 것에 익숙해지는데 시간이 꽤 오래 걸렸다. 아래는 문제를 해결하는 과정에서 어려움을 겪었던 문법들이다.

시행 착오

문제 해결의 단계는 아래와 같다.

1. 단어를 입력받아야한다. C에서는 문자열 자체를 입력받기가 어려워 배열로 문자열을 받으려 시도했다. 이때 가변배열을 사용하려했으나 주의할 점은 입력받을 때 문자열의 길이가 정해지지 않는다는 것이다. 이를 해결하고자 realloc()으로 재할당을 시도했다.
2. 입력받은 단어를 대문자로 변환한다. 이 과정에서 toupper(); 함수를 사용한다. <ctype.h>를 include 해야한다.
3. 대문자로 변환한 알파벳에서 각각 입력받은 횟수를 배열에 저장한다.
4. 각 알파벳 중 가장 많이 사용된 알파벳의 갯수를 알아낸다. 이를 max 변수에 저장한다.
5. 가장 많이 사용된 알파벳이 여러 개 존재하는 경우를 판별하기 위해 max 값만큼의 값을 가진 알파벳이 2개 이상이면 "?"를 출력한다.

1차 시도

#define _CRT_SECURE_NO_WARNINGS
#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
  int main() {
      int size = 10;
      int count = 0;
      char string[26] = { 0 }; // 알파벳 26개를 카운트하기 위한 배열
      char* word = (char*)malloc(size * sizeof(char));
      int max = 0;
      int index = 0;
      int check = 0;

      for (int i = 0;; i++) {
          if (count == size) {
              size *= 2;
              word = realloc(word, size * sizeof(char));
          }

          scanf("%c", &word[i]);
          count++;
          if (word[i] == '\n') {
              word[i] = '\0'; // 문자열의 끝을 표시
              break;
          }
      }

      for (int i = 0; i < count; i++) {
          word[i] = toupper(word[i]);
          if (word[i] >= 'A' && word[i] <= 'Z') {
              string[word[i] - 'A']++;
          }
      }

      for (int i = 0; i < 26; i++) {
          if (string[i] > 0 && string[i] > max) {
              max = string[i];
              index = i;
          }
      }

      for (int i = 0; i < 26; i++) {
          if (string[i] > 0 && string[i] == max) {
              check++;
          }
          if (check >= 2) {
              printf("?");
              return;
          }
      }

      printf("%c", index + 'A');

      free(word); // 동적 메모리 해제
      return 0;
  }

이 부분에서 문제가 된 점은 string 배열을 char 타입으로 설정한 것이다. string 배열은 각 알파벳의 갯수를 카운트하기 위한 배열이므로 int 타입으로 수정하고 난 후 해결되었다.

2차 시도

#define _CRT_SECURE_NO_WARNINGS
#include <stdlib.h>
#include <stdio.h>
#include <ctype.h> // 이게 머지?
int main() { // 런타임 에러
      int size = 10;
      int count = 0;
      int string[26] = { 0 }; // 알파벳 26개를 카운트하기 위한 배열
      char* word = (char*)malloc(size * sizeof(char));
      int max = 0;
      int index = 0;
      int check = 0;

      for (int i = 0;; i++) {
          if (count == size) {
              size *= 2;
              word = realloc(word, size * sizeof(char));
          }

          scanf("%c", &word[i]);
          count++;
          if (word[i] == '\n') {
              word[i] = '\0'; // 문자열의 끝을 표시
              break;
          }
      }

      for (int i = 0; i < count; i++) {
          word[i] = toupper(word[i]);
          if (word[i] >= 'A' && word[i] <= 'Z') {
              string[word[i] - 'A']++;
          }
      }

      for (int i = 0; i < 26; i++) {
          if (string[i] > 0 && string[i] > max) {
              max = string[i];
              index = i;
          }
      }

      for (int i = 0; i < 26; i++) {
          if (string[i] > 0 && string[i] == max) {
              check++;
          }
          if (check >= 2) {
              printf("?");
              return;
          }
      }

      printf("%c", index + 'A');

      free(word); // 동적 메모리 해제
      return 0;
  }

string 배열의 타입을 int로 수정하고 난 후에는 런타임 에러가 발생하였다. 여러 문제점을 찾아보았다.

내가 생각한 문제점

1. 배열의 동적 할당 배열을 동적으로 할당받지 않고 처리하면 이 문제를 해결할 수 있을지도 모른다. 또한, 굳이 이 문제에서 배열을 동적으로 처리할 필요성이 없다고 느껴진다. 문제를 다시 읽어보니 문제 내에서 단어의 길이가 정해져 있기 때문이다.
2. \n문제 문자열의 끝을 표시할 때 \n을 사용할 이유가 없다. 단어는 공백이 없고, scanf 함수는 공백이 입력되면 자동으로 입력이 끝났다고 처리하기 때문이다.
3. 전반적인 코드의 복잡성 코드가 전체적으로 복잡하게 짜여있다고 생각되었다. 코드를 조금 더 간결하게 구성하여 문제점이 한 눈에 보이게 할 필요가 있다.

이러한 문제점들을 개선하여 제출한 답은 아래와 같다.

제출한 답

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <ctype.h> // toupper 사용 위함
#include <string.h> // strlen 사용 위함


int main() {
    char word[1000000];
    scanf("%s", word);
    int len = strlen(word);
    int string[26] = {0}; // 26개 알파벳
    int max=0;
    int count = 0;
    int index;

    for (int i = 0; i < len; i++) {
        word[i] = toupper(word[i]);
        string[word[i] - 'A']++;
    }
    for (int i = 0; i < 26; i++) {
        if (string[i] > 0 && max < string[i]) {
            max = string[i];
            index = i;
        }
    }
    for (int i = 0; i < 26; i++) {
        if (max == string[i])
            count++;
    }
    if (count > 1) {
        printf("?");
    }
    else {
        printf("%c", 'A' + index);
    }
}