[이코테] 02 구현

개념

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

❓자바스크립트 메모리 제약 사항

일반적으로 컴퓨터는 1초에 `10억(10^8)`번 연산의 연산이 가능하다. C++이나 파이썬은 기준이 정해져 있지만, 자바스크립트는 대략 `10^7`번 정도를 기준으로 계산하라는 이야기가 있다. 공식적으로는 정의되어있지 않고, 언어 자체의 특성보다는 브라우저나 실행 환경의 성능에 따라 다를 수 있다고 한다. 정확한 "1초에 몇 번"의 연산으로는 일반적으로 표현되지 않는 대신에, 브라우저나 실행 환경에서의 실제 성능 측정을 통해 어떤 연산이 더 효율적인지 판단하는 것이 보편적인 방법이다.

 

예제 4-1 상하좌우

일련의 명령에 따라서 개체를 차례대로 이동시킨다는점 → 시뮬레이션 > O(이동 횟수) = `O(100)`

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

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

function isSafe(x,y){
    if(x<1 || x>n || y<1 || y>n) return false;
    else return true;
}

function solution(n,arr) {
    const dir={ //y,x
        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 newx = point[0] + x;
        const newy = point[1] + y;

        if (isSafe(newx, newy)){
        point[0] = newx;
        point[1] = newy;
        }
    }
    return point;
}

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

isSafe 함수를 생성해 좌표가 유효한 범위 내에 있는지 확인하는 함수 생성. 범위를 벗어나면 `false`, 아니면 `true`를 반환한다.

solution 함수로 문제가 원하는 이동을 제어한다.

dir 객체를 생성해 방향을 정의한다.

for문으로 각 요소를 순회한다. dir 객체에 해당하는 배열의 현재요소 d를 `[x,y]`에 구조분해할당 한다.

new 변수에 현재 좌표 point에서 이동 방향에 따른 새로운 좌표를 계산한다.

isSafe 함수를 사용하여 확인하고, 유효한 범위 내에 있는 경우에만 다음 작업을 수행한다.

범위에 있을 경우, point 에 현재 좌표로 업데이트

 

예제 4-2 시각

가능한 경우의 수를 모두 검사해봄 → 완전 탐색 > `O(24 * 60 * 60)`

하루 86,400초

시각을 문자열로 바꾼 다음 문자열에 '3' 이 포함되었는지 검사하기. h,m,s 삼중 for 문

const fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim();

let n = Number(input);

function solution(n){
    let cnt = 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')) cnt++;
            }
        }
    }
    return cnt;
}
console.log(solution(n));

자바스크립트에서는 '3' 문자열과 숫자 3을 비교할 수 있다. 문자열과 숫자가 비교될 때는 자바스크립트 엔진이 자동으로 형 변환을 수행하며, 문자열이 숫자로 변환되어 비교된다.

 

실전문제

왕실의 나이트 > `O(1)`

위치좌표 알파벳 가로, 숫자 세로

1. 입력 : 문자열로 들어오는 위치 정보를 인덱스로 변환하는 것

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim();

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

.charCodeat() :  주어진 index에 해당하는 유니코드 값을 리턴하는데 이 값은 unicode가 지원되는 모든 시스템에서 동일한 문자를 가르킨다.

function isSafe(x,y){
    if(x<1 || x>8 || y<1 || y>8) return false;
    else return true;
}

function solution(x,y) {
    const dir=[//나이트가 이동할 수 있는 8가지 방향
        [-1,-2],[1,-2],[2,-1],[2,1],
        [1,2],[-1,2],[-2,1],[-2,-1]
    ]

    let cnt = 0;
    for(let i=0; i<8; i++) {
        const newx = x+dir[i][0];
        const newy = y+dir[i][1];

        if(isSafe(newx, newy))
        cnt++;
    }
    return cnt;
}

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

예제 상하좌우와 비슷한 흐름

solution 함수이 for문을 돌면서 각 방향으로 나이트가 이동했을 때의 새로운 좌표를 계산한다.

dir 의 i가 변화량, 0이 x좌표, 1이 y좌표를 가리킨다.

isSafe 함수로 범위내에 있는지 확인하고, 유효한 위치인 경우, cnt 증가한다.

 

게임 개발 > `O(nm)` = `O(50*50)`

직사각형

input.txt

4 4       // n*m 맵 생성
1 1 0     // (1,1)에 북쪽(0)을 바라보고 서있는 캐릭터
1 1 1 1   //바다 바다 바다 바다
1 0 0 1   //바다 육지 육지 바다
1 1 0 1   //바다 바다 육지 바다
1 1 1 1   //바다 바다 바다 바다

1. 입력

const fs = require('fs');
let input = fs.readFileSync('/dev/stdin').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));

1차 구조분해 할당 후, 2차 할당

map 변수 2차원 할당 : .map 메서드 안에 .map 메서드

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 cnt = 1;
    let turncnt = 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;
            cnt++;
            turncnt=0;
            continue;
        }else{//정면에서 가보지 않은 칸이 없거나, 바다인 경우
            turncnt++;
        }

        //네 방향 모두 갈 수 없는 경우
        if(turncnt === 4){
            nx = x-dir[d][0];
            ny = y-dir[d][1];

            //뒤로 갈 수 있으면 이동
            if(!map[nx][ny]){
                x=nx;
                y=ny;
                turncnt=0;
            }else{//뒤가 바다로 막혀있는 경우
                break;
            }
        }
    }
    
    return cnt;
}
console.log(solution(n,m,x,y,d,map));

dir : 상하좌우

visited 방문한 곳 표기하기 위한 배열. 2차원 배열로 생성하는 방법

• `Array(n)` : 길이가 n인 배열 생성
• `Array(m).fill(false));` : 길이가 m이고, 모든 요소가 false인 배열 생성
• 즉, 길이가 n이고 모든 요소가 길이가 m이며, 값이 false 인 2차원 배열을 생성한다.

cnt : 방문한 칸의 개수

turncnt : 현재 위치에서 진행방향으로 이동할 수없을때 체크!

• 바다이거나, 방문했던 곳이라면 다른 방향으로 전환해야 하는데, 이때 turncnt++ 증가한다.
• 증가시킨 turncnt가 4가 되면, 네 방향 모두 이동할 수 없기 때문에 뒤로 한칸 이동하게 된다.
• 뒤로 이동할때 turncnt 변수는 초기화한다.

 

while 루프 안에서 이동시킨다

d의 값으로 방향을 변경한다. 북쪽일때, 왼쪽으로 회전해 서쪽을 볼 수 있도록 3으로 값을 변경하고, 이외의 경우에는 현재d 방향에서 -1로 변경한다.

nx, ny로 왼쪽으로 회전한 후에 이동할 x,y 좌표를 계산한다

1. 정면에 가보지 않은 칸이 존재하는 경우?
   • 방문표시
   • x,y 좌표 업데이트
   • 방문한 칸의 개수 증가
   • 이동할 수 있는 방향이 있으니, turncnt 0으로 초기화
2. 정면에서 가보지 않은 칸이 없거나, 바다인 경우
   • 이동할 수 없는 방향의 개수를 증가 `turncnt++`
3. 네 방향 모두 갈 수 없는 경우
   • turn이 4일 경우, 뒤로 이동 x,y 좌표 계산
   • 뒤로이동 가능할 경우 : 좌표 업데이트
   • 뒤로이동 불가능할 경우 : 작업 종료

 

백준 문제

8979번 : 올림픽

8979번: 올림픽

let input = require('fs').readFileSync('/dev/stdin').toString().split('\n').map((val)=>val.trim());

function solution(input) {
    let [n,k] = input.shift().split(' ').map((v)=>+v);

    let country=[];
    let rank = 1;
    for (let i=0; i<n; i++){
        let temp = input.shift().split(' ').map((v)=>+v);
        country.push(temp);
    }

    country.sort((a,b)=>a[0]-b[0]);

    rank += country.filter((v)=>
    v[1] > country[k-1][1] ||
    (v[1] === country[k - 1][1] && v[2] > country[k - 1][2]) ||
      (v[1] === country[k - 1][1] && v[2] === country[k - 1][2] && v[3] > country[k - 1][3])
).length;

    console.log(rank);
}

solution(input);

 

2852번 : NBA 농구

2852번: NBA 농구

let [N,...input] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');

let one = 0;
let two = 0;
const score = [];
let ans = [0,0];

input.forEach(v=>{
    const [team,t] = v.split(' ');
    const [mm,ss] = t.split(':');
    
    team==1? one++ : two++;

    const time = Number(mm) * 60 + Number(ss);

    if (one > two) score.push([1, time])
    else if (two > one) score.push([2, time])
    else score.push([0, time])
})

score.push([0, 2880])

for (let i = 1; i < score.length; i++) {
    if (score[i - 1][0] != 0)
        ans[score[i - 1][0] - 1] += score[i][1] - score[i - 1][1];
  }

ans = ans.map(v => {
    const mm = String(Math.floor(v / 60)).padStart(2, '0')
    const ss = String(v % 60).padStart(2, '0');
    return `${mm}:${ss}`
  }).join('\n')

console.log(ans);

 

20006번 : 랭킹전 대기열

20006번: 랭킹전 대기열

// 입력 처리
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');

const [p, m] = input[0].split(' ').map(Number);
const players = input.slice(1).map(val => {
    const [level, name] = val.split(' ');
    return { level: parseInt(level), name };
});

// 매칭 함수 정의
function matching(p, m, players) {
    //빈방 생성
    const rooms = [];
    //각 방에 플레이어를 매칭
    players.forEach(player => {
        let matched = false;
        rooms.some(room => {
            if (room.length < m && Math.abs(room[0].level - player.level) <= 10) {
                room.push(player);
                matched = true;
                return true; // some 함수를 종료하기 위해 true 반환
            }
            return false;
        });
        if (!matched) {
            rooms.push([player]);
        }
    });
    
    rooms.forEach(room => {
        console.log(room.length === m ? 'Started!' : 'Waiting!');
        room.sort((a, b) => a.name.localeCompare(b.name));
        room.forEach(player => {
            console.log(`${player.level} ${player.name}`);
        });
    });
}

// 매칭 수행
matching(p, m, players);

입력 첫번째줄 : 플레이어수 p, 방의 정원 m

p줄동안 : 레벨 l, 닉네임 n

출력 방의 시작유무, 각 플레이어 레벨l 닉네임n 줄 바꾸며 출력. 사전 순서대로 정렬

 

`slice(1)` : input의 첫번째줄 제외하고 밑의정보 가져옴

map을 순회하면서 레벨과 이름을 추출함

공백 기준으로 lever과 name을 할당하고, 객체를 생성한다. level은 문자열로 추출되기 때문에 정수로 변환한다.

 

matching 함수

첫번째 forEach문으로 플레이어 순회하며 각 방에 매칭

방 매칭이 가능한 조건

• 방의 현재 인원수 `room.length` 가 `m` 방의 정원보다 작아야하고
• 방의 첫번째 플레이어의 레벨 `room[0].level` 보다 10 이내로 차이나야한다
  • `Math.abs` 절대값 반환하는 메서드로 표현

매칭 가능하다면? 해당 방에 플레이어를 추가하고, matched를 true로 설정한다

some 메서드로 배열 안의 어떤 요소라도 주어진 판별 함수를 적어도 하나라도 통과하는지 테스트

매칭 안될경우? 새로운 방에 플레이어를 추가한다. `rooms.push([player]);`

 

두번째 forEach 문으로 각 방을 순회하며 정보 출력

방이 다 차서 시작되었다면, Started! 출력하고, 정보 출력함

각 방에 속한 플레이어의 정보를 for문을 돌면서 출력한다.

 

JS 문자열 비교 메서드 localeCompare

String.prototype.localeCompare() - JavaScript | MDN