푸키키키

문제

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

풀이

trie 자료구조에 입력값을 저장한다.
trie를 구성하던 중에 trie완성된 부분에서 node를 추가해나가는 건 다른 접두사가 있다는 것으로 "NO" 출력
trie를 구성하던 중에 끝났는데 지금까지 구성된 trie가 있다면 (this.pass로 표현) "NO" 출력

코드

let fs = require('fs');
// let input = fs.readFileSync('/dev/stdin').toString().split('\n');
let input = fs.readFileSync('./input.txt').toString().split('\n');

let readlineIdx = 0;

const readInput = () => input[readlineIdx++];

class Trie {
  constructor() {
    this.pass = false;
    this.end = false;
    this.child = {};
  }

  insert(trie, arr) {
    let el = parseInt(arr[0], 10);
    const nowChild = trie.child[el];
    if (nowChild === undefined) {
      const nT = new Trie();
      nT.pass = true;
      trie.child[el] = nT;
      if (arr.length === 1) {
        nT.end = true;
        return true;
      }
      return this.insert(nT, arr.slice(1));

    }
    if (nowChild.end === true) {
      return false;
    }
    if (arr.length === 1) {
      if (nowChild.pass) {
        return false;
      }
      nowChild.pass = true;
      nowChild.end = true;
      return true;
    }
    nowChild.pass = true;
    return this.insert(nowChild, arr.slice(1));
  }
}

function solution(temparr, n) {
  const trie = new Trie();
  for (let i = 0; i < n; ++i) {
    const nowArr = temparr[i].split("").filter((el) => el !== ' ');
    if (trie.insert(trie, nowArr) === false) {
      return false;
    }
  }
  return true;
}

function main() {
  let t = readInput();
  while (t--) {
    let n = readInput();
    let temparr = new Array();
    for (let i = 0; i < n; ++i) {
      temparr.push(readInput());
    }
    console.log(solution(temparr, n) === true ? 'YES' : 'NO');
  }
}

main();

문제

www.hackerrank.com/challenges/new-year-chaos/problem?h_l=interview&playlist_slugs%5B%5D%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D%5B%5D=arrays&isFullScreen=true

풀이

1. arr[i] = i+1 형태의 배열을 만든다.
2. 이 배열을 입력배열 q와 똑같이 만들 수 있는지 판별하고 swap cnt를 기록한다.
3. idx=0부터 증가하면서 조건을 만족하며 swap해 가면 반드시 본래위치에 idx+2 이하에 들어가야 하는 값이 있어야 한다.
4. 조건 만족하면 cnt기록, 조건만족하지 않으면 종료시킨다.

코드

'use strict';

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.replace(/\s*$/, '')
        .split('\n')
        .map(str => str.replace(/\s*$/, ''));

    main();
});

function readLine() {
    return inputString[currentLine++];
}

// Complete the minimumBribes function below.
function minimumBribes(q) {
  let answer = 0;
  let arr = Array(100001);
  let arrCnt = Array(100001);
  for(let i=0;i<arr.length;++i) {
    arr[i] = i+1;
  }
  for(let i=0;i<q.length-1;++i) {
    let originValue = q[i];
    if(arr[i] !== originValue) {
      if(arr[i+1] !== originValue) {
        if(arr[i+2] !== originValue) {
          return 'Too chaotic';
        }
        let temp = arr[i+2];
        arr[i+2] = arr[i+1];
        arr[i+1] = temp;
        answer++;
      }
      let temp = arr[i+1];
      arr[i+1] = arr[i];
      arr[i] = temp;
      answer++;


    }
  }
  return answer;
}

function main() {
    const t = parseInt(readLine(), 10);

    for (let tItr = 0; tItr < t; tItr++) {
        const n = parseInt(readLine(), 10);

        const q = readLine().split(' ').map(qTemp => parseInt(qTemp, 10));

        console.log(minimumBribes(q));
    }
}

문제

https://programmers.co.kr/learn/courses/30/lessons/17677

풀이

1. str1의 길이가 str2보다 짧으면 둘을 swap한다.
2. 입력받은 문자열을 대문자로 바꾼다.
3. 2글자씩 나누어 배열에 담는다.
4. 2글자씩 나누었을 때 부적절한 단어가 있으면 drop 한다.
5. 교집합과 합집합의 수를 구하기 위해 str1을 새로운 배열에 넣고 그곳에 str2의 원소를 하나씩 넣으며 교집합의 원소개수와 합집합 원소개수를 구한다.
6. 값을 구한다.