본문 바로가기
Algorithm/BOJ

1차원 배열 편(1) - Node.js로 [백준/BOJ] 단계별로 풀어보기를 풀어보다

by Muko 2020. 4. 25.

안녕하세요~ Muko 입니다.

이번 포스팅도 계속해서 백준의 단계별로 풀어보기를 진행하려고 합니다. 벌써 5번째 시간인데요! 요즘 백준에서 단계별로 풀어보기를 대대적으로 수정하고 있는지 예전과 달라진 곳 들도 있고, 아직 개편 중인 곳도 있어서 확정된 문제집 부터 풀어보려고 합니다. 그래서 오늘은 6번 째 단계인 1차원 배열 편을 풀어보도록 하겠습니다.

사실 블로그를 운영하는데는 C언어나 Java, Python으로 풀이를 올리는게 더 유입이 잘 될 것 같아서 계속해서 흔들리고 있습니다. 열심히 포스팅을 올리고 있는데, 구글이나 네이버에서 유입이 전혀 안되고 있어서 더욱 그러네요. 포스팅을 하고, 사람들이 들어와서 공부하고 왔다는 표시가 늘어날 수록 보상 받는 기분에서 더 열심히 하게될텐데, 제가 컨텐츠를 잘못 잡았나 하는 생각도 듭니다. 사실 개인적인 공부를 정리하는 목적으로만 포스팅한다면 안해도 되는 포스팅인까요.

그럼에도 불구하고 저도 계속해서 사용해야 하는 언어이고, 이왕 시작한거 끝을 보기위해 흔들리지 않도록 다시 마음을 다잡고 포스팅을 계속 하도록 하겠습니다.

BOJ 10818 - 최소, 최대

이 문제에서는 입력이 먼저 정수 N이 들어오고, 그 아래 줄에 N개의 정수가 입력으로 들어올 때 그 중에서 최솟값과 최댓값을 구하는 문제입니다. 사실 많은 알고리즘 문제도 그렇고, 수학 문제도 그렇듯이 풀이 방법이 하나만 있지는 않습니다. 이 문제도 다양하게 풀어보도록 하죠.

우선 문제집의 분류가 1차원 배열인 만큼, 입력을 배열에 보관한 상태에서 반복문을 돌리면서 최댓값과 최솟값을 찾는 방법이 있습니다.

// 입출력에 사용할 rl을 받아오는 함수
const getRl = () => {
  const readline = require('readline');
  return readline.createInterface({
    input: process.stdin,
    output: process.stdout
  });
}
const rl = getRl();

// 주어진 입력들을 이용해서 정답을 반환하는 함수
const printAnswer = (input) => {
  const N = parseInt(input[0]);
  let minValue = 1000001 // 문제 최대 숫자 범위보다 큰 수로 초기화
  let maxValue = -1000001 // 문제 최소 숫자 범위보다 작은 수로 초기화
  for (let i=0; i<N; i++) {
    const value = parseInt(input[1][i]);
    minValue = minValue > value ? value : minValue;
    maxValue = maxValue < value ? value : maxValue;
  }
  console.log(minValue, maxValue);
};

// 입력 받아와서 알고리즘 동작하는 함수
const input = [];
const start = (rl) => {
  rl.on('line', line => {
    input.push(line.split(' '));
  }).on('close', () => {
    printAnswer(input);
    process.exit();
  });
}

// 프로그램 동작
start(rl);



하지만 자바스크립트에서는 반복문을 돌릴 수 있는 방법이 더 있습니다. 다른 포스팅에서 다루었던 while, forEach, map도 있을 뿐만 아니라 reduce라는 문법으로도 배열을 순회하면서 원하는 작업을 수행하는게 가능합니다. 이번에는 반복문 포스팅에서 다루지 않았던 reduce를 사용해서 풀어보도록 하겠습니다.

const printAnswer = (input) => {
  const N = parseInt(input[0]);
  const minValue = input[1].reduce((acc, cur) => {
    return parseInt(acc) > parseInt(cur) ? parseInt(cur) : parseInt(acc);
  });
  const maxValue = input[1].reduce((acc, cur) => {
    return parseInt(acc) < parseInt(cur) ? parseInt(cur) : parseInt(acc);
  });
  console.log(minValue, maxValue);
}



만약 input 배열에 문자열이 아니라 숫자로 넣었다면, 위의 함수에서 parseInt를 제거할 수 있겠죠? 그럼 더 빠르게 수행하는 함수가 완성이 될 겁니다.

여기서 acc는 reduce 내부의 함수 반환값을 계속해서 저장하면서 마지막에 반환되는 값입니다. 변수명은 accumulator의 약자로 acc라고 사용했는데요, 영어 단어에서 알 수 있듯이 해석하면 배열을 순회하면서 로직의 결과를 계속해서 가지고 있는 변수입니다. 예제를 보시면 쉽게 이해할 수 있으실 겁니다.

const arr = [1, 2, 45, 2, 4, 1];
arr.reduce((acc, cur) => {
  console.log(acc, cur);
  return acc > cur ? cur : acc;
});
/*
1 2
1 45
1 2
1 4
1 1
*/

arr.reduce((acc, cur) => {
  console.log(acc, cur);
  return acc < cur ? cur : acc;
});
/*
1 2
2 45
45 2
45 4
45 1
/*



console.log를 이용해서 reduce가 동작하는 것을 계속해서 출력하다보면, 결국 위에서 구현했던 for문과 동일하게 작동하는 것을 확인할 수 있습니다. 배열 요소를 하나씩 탐색하면서, 가장 작은 것은 보관하고 있고, 인덱스는 다음꺼로 넘어가면서 최종적으로 가장 작은 것을 찾아내는 것과 같은 로직입니다. 위에 for문을 사용해서 구할 때 변수가 minValue였다면, 여기서 reduce를 사용할 때는 acc에 보관이 되는 방식인 것이죠. 이처럼 javascript에서는 for문을 쓰지 않고도 더 짧은 코드로 같은 동작 방식을 구현하는 것이 가능합니다.

사실 이것보다 더 쉬운 방법이 있습니다. Math라는 것을 사용하는 방식입니다.

const printAnswer = (input) => {
  // Math.min.apply(null, 배열)
  // Math.max.apply(null, 배열)
  const minValue = Math.min.apply(null, input[1]);
  const maxValue = Math.max.apply(null, input[1]);
  console.log(minValue, maxValue);
}

 

const printAnswer = (input) => {
  const minValue = Math.min(...input[1]);
  const maxValue = Math.max(...input[1]);
  console.log(minValue, maxValue);
}

 

마지막 방법으로 정답을 맞기위해서는 마찬가지로 문자열이 아니라 숫자로 input에 넣어주어야 합니다. 만약 입력이 정수로 들어가 있으면 이렇게 푸는 것도 가능하다는 것을 보여드리기 위해 작성한 코드입니다 :)




BOJ 2562 - 최댓값

이 문제는 9개의 서로 다른 자연수가 입력으로 주어질 때, 이 값들 중 최댓값을 찾으면 끝나는 것이 아니라 몇 번째 수인지도 구해야 하는 문제입니다. 위의 문제처럼 단순히 숫자만 찾으면 답을 맞출 수가 없겠죠? 최댓값을 구해서 저장할 변수, 그리고 그 변수가 어디 위치해 있는지를 보관할 변수를 두고 반복문을 돌리면서 풀면 쉽게 해결할 수 있습니다.

for이나 while문은 다른 문제에서도 충분히 연습가능하니, 이번에는 익숙하지 않은 reduce를 이용해서 풀어볼까요?

// 입출력에 사용할 rl을 받아오는 함수
const getRl = () => {
  const readline = require('readline');
  return readline.createInterface({
    input: process.stdin,
    output: process.stdout
  });
}
const rl = getRl();

// 주어진 입력들을 이용해서 정답을 반환하는 함수
const printAnswer = (input) => {
  let findIndex = 1;
  const findValue = input.reduce((acc, cur, index) => {
    if (acc < cur) {
      findIndex = index;
      return cur;
    }
    return acc;
  });
  console.log(findValue+'\n'+(findIndex+1));
};

// 입력 받아와서 알고리즘 동작하는 함수
const input = [];
const start = (rl) => {
  rl.on('line', line => {
    input.push(parseInt(line));
  }).on('close', () => {
    printAnswer(input);
    process.exit();
  });
}

// 프로그램 동작
start(rl);

 

여기서 주의하셔야할 점은 인덱스입니다. for문도 그렇고, 제가 풀이한 방법도 그렇고 보통은 0에서 시작하는데 정답에서 요구하는 인덱스는 1부터 시작한 다는 점을 고려해서 코드를 작성하셔야 틀리지 않고 답을 맞출 수 있습니다.




BOJ 2577 - 숫자의 개수

이번에는 세 개의 자연수 A, B, C가 입력으로 들어왔을 때 ABC를 계산한 결과에 0부터 9까지 각 숫자가 몇 번 사용되었는지를 출력하는 문제입니다. 따라서 계산 결과에서 자리 수를 분리해서, 각 숫자가 몇 번 사용되었는지 저장할 수 있도록 변수를 구성해야 합니다. 이럴 때는 길이가 10인 배열을 0으로 모두 초기화 한 뒤에, 각 자리수를 배열의 인덱스로 사용해서 접근하고, 접근할 때 마다 그 안에 있는 값을 증가시키는 방법으로 쉽게 해결할 수 있는 패턴의 문제입니다. 자주 사용되는 방법이니까 꼭 연습해보세요!

// 입출력에 사용할 rl을 받아오는 함수
const getRl = () => {
  const readline = require('readline');
  return readline.createInterface({
    input: process.stdin,
    output: process.stdout
  });
}
const rl = getRl();

// 주어진 입력들을 이용해서 정답을 반환하는 함수
const printAnswer = (input) => {
  const counts = Array(10).fill(0);
  const digits = ''+(input[0] * input[1] * input[2]);

  // 브라우저에서는 동작하는 코드
  // digits.forEach(digit => counts[digit]++);
  // counts.map(elem => console.log(elem));

  // 백준 정답용 코드
  for(let i=0; i<digits.length; i++){
      counts[parseInt(digits[i])]++;
  }
  for(let i=0; i<10; i++){
      console.log(counts[i]);
  }
};

// 입력 받아와서 알고리즘 동작하는 함수
const input = [];
const start = (rl) => {
  rl.on('line', line => {
    input.push(parseInt(line));
  }).on('close', () => {
    printAnswer(input);
    process.exit();
  });
}

// 프로그램 동작
start(rl);

 

위에서 const digits = ''+(input[0] * input[1] * input[2]); 부분이 이해가 되지 않는 분들이 있으실 겁니다. 이 코드는 우선 괄호 안에 있는 곱하기 연산이 먼저 이루어지고, 빈 문자열에 더해지게 됩니다. 더하기 기호는 숫자끼리 더해주는 덧셈 기능도 하지만, 문자열이 있을 경우에는 문자열 연산자로서 두 개의 자료형을 이어 붙여서 하나의 문자열로 반환하게 됩니다. 따라서 만약 곱셈 결과가 1423 라면 digits에는 '1423' 이 저장되게 됩니다. 이렇게 숫자를 문자열로 만들게 되면 좋은 점이, length를 알 수 있다는 점, 그리고 인덱스로 각 자리 수에 접근이 가능해 진다는 점입니다. 그래서 바로 아래에서 counts 배열에 접근한 것이죠.



다음 포스팅에 이어가겠습니다!

댓글7