[알고리즘 떠먹여 주는 남자] 백준 1157 - 단어 공부 for Node.js

안녕하세요.. 오늘도 알고리즘을 떠 드리기 위해 왔습니다. 최근 자바스크립트 공부에 열을 올렸는데, 아무래도 알고리즘을 너무 소홀히 한 것 같습니다. 가뜩이나 알고리즘 푸는 것도 오래 걸리는데 말이죠.. 참 연습을 하는데도 잘 늘지가 않는 것 같네요 ㅠㅠ 좀 더 정진해야 할 것 같습니다..!

 

https://www.acmicpc.net/problem/1157

1157번: 단어 공부

오늘은 어떤 문제를 풀어볼까 찾아보다가 예전에 알고리즘 다시 공부 시작했을 때 빼먹고 넘어간 게 있더라구요.. 정확히 말하자면 못풀고 넘어간.. 그래서 오늘 다시 도전해 보았습니다.

문제

알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다.

입력

첫째 줄에 알파벳 대소문자로 이루어진 단어가 주어진다. 주어지는 단어의 길이는 1,000,000을 넘지 않는다.

출력

첫째 줄에 이 단어에서 가장 많이 사용된 알파벳을 대문자로 출력한다. 단, 가장 많이 사용된 알파벳이 여러 개 존재하는 경우에는 ?를 출력한다.

예제 입력 1 복사

Mississipi

예제 출력 1 복사

?

예제 입력 2 복사

zZa

예제 출력 2 복사

Z

예제 입력 3 복사

z

예제 출력 3 복사

Z

예제 입력 4 복사

baaa

예제 출력 4 복사

A

 

문제풀이

처음에 잠깐 헤맸지만 어려운 난이도는 아니라고 생각합니다 (하지만 저에게는 어려웠습니다ㅠ). 문제에 제시되어 있는 조건을 살펴보면:

• 주어진 스트링 안에서 가장 빈도수가 높은 단어를 대문자의 형태로 출력할 것
• 만약 빈도수가 가장 높은 단어가 여러개일 경우, ? 를 출력할 것.

처음에 헤매었던 이유는 출력 값이 제대로 나옴에도 불구하고 자꾸 메모리 초과 에러가 떴습니다. 메모리.. 너무 어렵네요 흑흑 😭

채점 결과

제 치부책입니다.

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : `${__dirname}/input.txt`;
const input = fs.readFileSync(filePath).toString().toUpperCase();

let mostFrequentChar = '';
let count = 0;

for (let idx = 0; idx < input.length; idx++) {
  if (input.split(input[idx]).length > count) {
    count = input.split(input[idx]).length;
    mostFrequentChar = input[idx];
  } else if (input.split(input[idx]).length === count && input[idx] !== mostFrequentChar) {
    mostFrequentChar = '?';
  }
}

console.log(mostFrequentChar);

최근 자바스크립트 기초를 책으로 공부하면서 JS 에서 변수가 선언 되거나 새 값이 assign 될 때 어떻게 메모리가 할당되는지 배웠는데 그럼에도 아직 이해가 잘 가지 않네요..

 

그런고로, 다른 방법을 써서 문제를 해결해 보았습니다.

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : `${__dirname}/input.txt`;
const input = fs.readFileSync(filePath).toString().trim().toUpperCase();

const obj = {};

for (const char of input) {
  if (!obj[char]) {
    obj[char] = 1;
  } else {
    obj[char] += 1;
  }
}

let mostFrequentChar = '';
let count = 0;

for (const [key, value] of Object.entries(obj)) {
  if (value > count) {
    count = value;
    mostFrequentChar = key;
  } else if (value === count) {
    mostFrequentChar = '?';
  }
}

console.log(mostFrequentChar);

먼저 객체 하나를 선언해 주고 캐릭터를 키로, 존재하는 갯수를 값으로 설정해 준 후에, 그 결과를 iteration 해 주었습니다. 이렇게 하니 메모리 초과 에러가 나지 않더군요.

 

한가지 주의해야 할 점은 위의 채점 결과 화면에서 메모리 초과와 성공 중간에 오답이 하나 있는데, 그건 처음 input 값을 받을 때 .toString() 다음에 trim() 을 안해주어서 그렇습니다. 백준에서 알고리즘을 풀다 보면 로직이 틀렸을 때 어디서 틀렸다.' 라고 말을 안해주니 초보자의 입장에선 답답할 때가 많습니다. 정말 알고리즘은 풀어도 풀어도 끝이 없네요.. 문제 해결 잘 하시는 분들 보면 정말 대단하신 것 같습니다.. 저도 더 노력해야겠어요.

 

그럼 한탄은 이정도로 마치고 다음 글로 찾아뵙도록 하겠습니다. 모두 열공하시기 바라요!