[자바스크립트] 5089 Travelling Salesman

5089번: Travelling Salesman

문제

Bob Smith has to tour New Zealand visiting his company's customers. His database churns out a list of the towns where each customer lives, but it has not been well programmed so may display a given town more than once. Your job is to help Bob by removing the duplicates and telling him how many towns he actually has to visit.

 

 

입력

Input consists of a number of lists, each representing a week of visits. The first line of each week is a single integer, N (1 < N <= 100), which is the number of towns in the list. Input is terminated by N = 0 – this week should not be processed.

Each week contains a list of N towns, each on a line by itself. The name of a town may contain more than one word. The first letter of each word in a town's name begins with an upper case letter; all other letters are lower case. A town's name will contain no more than 20 characters.

 

 

출력

Output consists of a single line for each week. It contains the word Week, followed by a space, followed by the week number, the first week being 1, followed by a space, followed by the actual number of towns to be visited, duplicates having been removed.

 

 

예제 입력 1

5
Wellsford
Ruakaka
Marsden Point
Wellsford
Warkworth
4
Rangiora
Oxford
Oxford
Rangiora
0

 

 

예제 출력 1

Week 1 4
Week 2 2

 

 

자료구조

① 배열: input

② 정수: count

 

 

알고리즘

① 반복문으로 배열을 순회하면서 마을(town)의 개수(n)를 읽는다.

② 마을이 두 번 이상 중복되면 제거한다.

③ `Week X Y` 형태의 결과를 나타낸다. X는 주차의 수이며, Y는 현재 주차의 방문할 마을의 개수이다.

 

 

소스 코드 1

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().split("\n");
let count = 1;

function reculsive(array) {
  const n = +array.shift();
  if(n === 0) return;
  
  let obj = {};

  for (let i = 0; i < n; i++) {
    const key = array[i];
    obj[key] = (obj[key] || 0) + 1;
  }

  console.log(`Week ${count} ${Object.keys(obj).length}`);
  count++;
  reculsive(array.slice(n));
}

reculsive(input);

120ms

 

 

소스 코드 2

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim().split("\n");
let answer = [];

for (let i = 0; i < input.length - 1; i++) {
  let n = +input[i];
  let set = new Set(input.slice(i + 1, i + 1 + n));

  answer.push(`Week ${answer.length + 1} ${set.size}`);

  i += n;
}

console.log(answer.join("\n"));

116ms

 

 

 

✔ 출처

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