[Javascript로 정리하는 이코테] 2. 구현

http://www.yes24.com/Product/Goods/91433923

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24

 

개념

• 구현이란 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다.
• 구현 유형
  • 완전 탐색: 모든 경우의 수를 주저 없이 다 계산하는 방법
  • 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 유형

 

Javascript 환경 고려 사항

일반적으로 컴퓨터는 1초에 1억(10^8)번의 연산이 가능하다. 따라서 C++은 이 기준에 맞추어 시간복잡도를 계산하고, 조금 느린 Python은 1초에 2000만(2*10^7)번 연산을 한다고 가정하고 문제를 풀면 된다. Javascript도 대략 10^7번 연산 기준에 맞춰 시간복잡도를 계산하면 될 것 같다. 조금 명확한 기준을 알고 싶었지만, 아직 찾지 못했다ㅠㅠ

 

 

예제 4-1. 상하좌우

• 시뮬레이션 -> O(이동 횟수) = O(100)

const fs = require('fs');
let input = fs.readFileSync("./tc.txt").toString().trim().split('\n');

let [n, arr] = input;
n = Number(n);
arr = arr.split(' ');

function solution(n, arr){
  const DIR = {
    L: [0, -1],
    R: [0, 1],
    U: [-1, 0],
    D: [1, 0]
  }
  
  let point = [1, 1];
  for(const d of arr){
    const [x, y] = DIR[d];

    const nx = point[0] + x;
    const ny = point[1] + y;
    
    if(nx < 1 || nx > n || ny < 1 || ny > n)
      continue;
    
    point[0] = nx;
    point[1] = ny;
  }
  
  return point;
}

console.log(solution(n, arr));

 

예제 4-2. 시각

• 완전 탐색 -> O(24 * 60 * 60)

const fs = require('fs');
let input = fs.readFileSync("./tc.txt").toString().trim();

let n = Number(input);

function solution(n){
  let count = 0;
  
  for(let h = 0; h <= n; h++){
    for(let m = 0; m <= 59; m++){
      for(let s = 0; s <= 59; s++){
        const time = `${h}${m}${s}`;
        if(time.includes('3')){
          count++;
        }
      }
    }
  }
  
  return count;
}

console.log(solution(n));

 

 

실전 문제

왕실의 나이트

• 문자열로 들어오는 위치 정보를 인덱스로 변환하는 것이 하나의 포인트 -> O(1)

const fs = require('fs');
let input = fs.readFileSync("./tc.txt").toString().trim();

const x = input.charCodeAt(0) - 97 + 1;
const y = +input[1];

function solution(x, y){
  const DIR = [
    [-1, -2], [1, -2], [2, -1], [2, 1], 
    [1, 2], [-1, 2], [-2, 1], [-2, -1]
  ];
  
  let count = 0;
  for(let i = 0; i < 8; i++){
    const nx = x + DIR[i][0];
    const ny = y + DIR[i][1];

    if(nx < 1 || nx > 8 || ny < 1 || ny > 8)
      continue;

    count++;
  }
  
  return count;
}

console.log(solution(x, y));

 

게임 개발

• O(nm) = O(50*50)

const fs = require('fs');
let input = fs.readFileSync("./tc.txt").toString().trim().split('\n');

const [nm, abd, ...arr] = input;
const [n, m] = nm.split(' ').map(v => +v);
let [x, y, d] = abd.split(' ').map(v => +v);
const map = arr.map(v => v.split(' ').map(v => +v));

function solution(n, m, x, y, d, map){
  //북동남서 방향
  const DIR = [[0, -1], [1, 0], [0, 1], [-1, 0]];

  //방문 정보
  let visited = Array.from(Array(n), () => Array(m).fill(false));
  visited[x][y] = true;

  let count = 1; //방문한 칸의 수
  let turnTime = 0; //현재 칸에서 탐색한 방향의 수
  
  while(1){
    //왼쪽으로 회전
    d =  d === 0 ? 3 : d - 1;
    let nx = x + DIR[d][0];
    let ny = y + DIR[d][1];

    //정면에 가보지 않은 칸이 존재하는 경우 전진
    if(!map[nx][ny] && !visited[nx][ny]){
      visited[nx][ny] = true;
      x = nx;
      y = ny;
      count++;
      turnTime = 0;
      continue;
    } else{ 
      //정면에 가보지 않은 칸이 없거나 바다인 경우
      turnTime++;
    }

    //네 방향 모두 갈 수 없는 경우
    if(turnTime === 4){
      nx = x - DIR[d][0];
      ny = y - DIR[d][1];
      
      //뒤로 갈 수 있으면 이동
      if(!map[nx][ny]){
        x = nx;
        y = ny;
        turnTime = 0;  
      } else{
        //뒤가 바다로 막혀있는 경우
        break;
      }
    }
  }

  return count;
}

console.log(solution(n, m, x, y, d, map));