[백준 알고리즘] Node.js 14171. Cities and States

1. 문제

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

14171번: Cities and States

 

2. 풀이

• 처음에는 도시의 이름을 코드별로 두글자씩 잘라서 이용하려고 했었다.

const inputs = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const N = +inputs.shift(); // 주어지는 도시와 두글자의 수
const shareCities = new Set(); // {두글자 : 도시 이름을 앞의 두글자 자른 단어} 로 만들 object

let count = 0; // 몇개나 있는지 확인하고 쌍이기 때문에 마지막에 나누기 2.
for(let i = 0; i < N; i++){
  const [cityName, code] = inputs[i].split(" "); // 도시이름과 두 글자 단어.
  if(!shareCities[code]) { // object에 없다면 배열로 생성.
    shareCities[code] = [cityName.slice(0,2)];
  } else { //object에 있다면 추가.
    shareCities[code].push(cityName.slice(0,2));
  }
}

for(code in shareCities){
  shareCities[code].forEach(item => {
   //만약 해당 두 글자가 존재하고, 두 글자의 배열에 도시 이름에 대한 내용이 존재한다면 count증가.
    if(shareCities[item] && shareCities[item].includes(code)) count++; 
  })
}

console.log(count / 2);

• 위의 코드로 예제에 대한 답은 구할 수 있었지만 반례가 존재했다.
• N = 2, inputs = ['MIA MI', 'MIB MI'] / answer = 0;
  • MIA, MIB는 city이고, MI는 state 이다. 같은 주에 있으므로 special pair가 아닙니다.

 

• 다른 분의 python 코드(?) 를 참고했다. city의 이름 두글자와 주어지는 두 글자를 합쳐서 해결하신 코드이다.

const inputs = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const N = +inputs.shift();
const cityArr = Array(N).fill("");
const cityMap = new Set();

for(let i = 0; i < N; i++){
  const [cityName, code] = inputs[i].split(" ");
  cityArr[i] = cityName.slice(0,2) + code; // city의 앞 두 글자와 주어지는 두 글자를 합쳐서 만듬.
  if(cityMap[cityArr[i]]) cityMap[cityArr[i]] += 1;  // 만약 object에 같은 게 있다면 1 증가.
  else {
    cityMap[cityArr[i]] = 1; // 없다면 1로 생성.
  }
}

let count = 0;
for(let i = 0; i < N; i++){
  const reverseString = cityArr[i].slice(2) + cityArr[i].slice(0,2); // 만든 4글자를 두글자씩 잘라서 뒤집음.
  
  // 뒤집은 글자와 기존 4글자가 동일하지 않아야만 함. 주(state)가 달라야 하기 때문!
  if(cityArr[i] === reverseString) continue; 
  if(cityMap[reverseString]){
    count += cityMap[reverseString]; // 존재한다면 object의 값을 더해줌.
  }
}

console.log(count / 2) // 쌍으로 존재하기 때문에 나누기 2.

 

3. 정리

• 처음에 얼추 잘 가는 듯해서 기분 좋았는데, '틀렸습니다' 마주하고 어디가 틀렸는지 고민했었다. 다국어 문제이다 보니 질문 게시판에도 글이 없어서 당황했지만 딱 하나있던 글이 도움이 되었다.
• 코테를 연습하다보면 늘 드는 생각이지만, 다양하게 생각할 수 있도록 해봐야겠다. 아직은 센스가 좀 부족한 거 같다 ㅠㅠ

 

4. 참고

• https://mindflip.github.io/algorithm/boj/2-BOJ14171/