[코딩테스트] Softeer javascript - 금고털이, 장애물 인식 프로그램, 지도 자동구축, 전광판

금고털이

 

문제

루팡은 배낭을 하나 메고 은행금고에 들어왔다. 금고 안에는 값비싼 금, 은, 백금 등의 귀금속 덩어리가 잔뜩 들어있다. 배낭은 W ㎏까지 담을 수 있다.

 

각 금속의 무게와 무게당 가격이 주어졌을 때 배낭을 채울 수 있는 가장 값비싼 가격은 얼마인가?

 

루팡은 전동톱을 가지고 있으며 귀금속은 톱으로 자르면 잘려진 부분의 무게만큼 가치를 가진다.

 

문제풀이

- 귀금속 배열을 가격순으로 정렬한다.

- 귀금속 가격이 높은 무게씩 베낭에 넣는다.

 

 

 

장애물 인식 프로그램

https://softeer.ai/practice/info.do?idx=1&eid=409 

Softeer

문제 설명

자율주행팀 SW 엔지니어인 당신에게 장애물과 도로를 인식할 수 있는 프로그램을 만들라는 업무가 주어졌다.

 

[그림 1] 지도 예시

 

우선 [그림 1]과 같이 정사각형 모양의 지도가 있다. 1은 장애물이 있는 곳을, 0은 도로가 있는 곳을 나타낸다.

 

당신은 이 지도를 가지고 연결된 장애물들의 모임인 블록을 정의하고, 불록에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 장애물이 좌우, 혹은 아래위로 붙어 있는 경우를 말한다. 대각선 상에 장애물이 있는 경우는 연결된 것이 아니다.

 

 

[그림 2] 블록 별 번호 부여

 

[그림 2]는 [그림 1]을 블록 별로 번호를 붙인 것이다. 

 

지도를 입력하여 장애물 블록수를 출력하고, 각 블록에 속하는 장애물의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

 

 

문제풀이

- 전형적인 BFS 문제이다. 이중 for문을 돌면서 방문 여부와 map을 확인한다.

for(let i=0;i<n;i++){
	for(let j=0;j<n;j++){
    	if (!visit[i][j] && map[i][j]) {
        	BFS(i,j);
       }
   }
}

- BFS 함수를 생성해서 개수를 세고 배열에 넣는다.

function BFS(i,j) {
	visit[i][j]=true;
    queue.push([i,j])
    while(queue.length) {
    	const [y,x] = queue.shift();
        let count = 1;
        for(let i=0;i<4;i++){
        	const ny= y+ dy[i];
            const nx = x+ dx[i];
            if(ny>=0&&ny<n&&nx>=0&&nx<n&&!visit[ny][nx]) {
            	queue.push([ny.nx]);
                visit[ny][nx] = true;
                count++
            }
        }
        answer.push(count)
    }

 

 - 최종코드

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const map = input.slice(1).map(v=>v.split(''))
const [n] = input;
// console.log(map)

let arr = [];

let visit = map.map(v=>v.map(a=>false))
let queue = [ ]
const dy = [-1,1,0,0]
const dx = [0,0,-1,1]

function bfs(i,j) {
    visit[i][j]=true;
    queue.push([i,j]);
    let sum = 1;

    while(queue.length){
        const [y,x] = queue.shift();
        if (map[y][x]==='1') {
            for (let j=0;j<4;j++){
                const ny=y+dy[j]
                const nx=x+dx[j]
                if (ny>=0&&ny<n&&nx>=0&&nx<n&&map[ny][nx]==='1'&&!visit[ny][nx]) {
                    visit[ny][nx]=true;
                    queue.push([ny,nx])
                    sum++ }
            }
           
        }
    }
    arr.push(sum);
}

for (let i=0;i<n;i++){
    for (let j=0;j<n;j++){
        if (map[i][j]==='1'&&!visit[i][j]) {
            bfs(i,j)
        }
    }
}





//출력문
console.log(arr.length)
arr.sort((a,b)=>a-b)
arr.forEach(v=>console.log(v))

 

지도 자동 구축

 

문제 설명

현대자동차그룹이 레벨3 자율주행차 상용화 목표에 발맞춰 총력을 다하고 있는 가운데, 국내 최고 수준의 지도 구축 기술력을 보유한 현대엠엔소프트는 자율주행에 필요한 정밀지도를 제작해 배포하고, 기술 고도화를 위한 연구에 매진하고 있다.

최근에는 도로 데이터를 기반으로 자동으로 정밀지도를 구축하는 ‘지도 자동 구축(Map Auto Creation, 이하 MAC)’ 기술을 개발해 지도 제작 시간을 단축하고 정밀도를 향상시키는 데 성공했다.

 

자율주행차용 정밀 지도에 관한 궁금증으로 인터넷 검색을 해보니, Diamond-Square-Algorithm이라는 것을 찾게 되었다. 이 알고리즘은 정사각형을 이루는 점 4개를 고르고 그 후에는 다음과 같은 과정을 거쳐 모양이 만들어진다.

 

정사각형의 각 변의 중앙에 점을 하나 추가한다.

 

정사각형의 중심에 점을 하나 추가한다.

 

 

[그림]은 0단계(start)에서 2단계(2 iterations)까지 수행한 결과이다. 각 단계(N)가 계속해서 커져갈수록 점의 수가 커져간다.

 

문제풀이

- 사각형의 개수와 각 선과 점의 개수를 구해서 규칙을 찾아낸다.

- 사각형의 개수는 1,4,16, 즉  4의 제곱근만큼 늘어난다. 

- 그러나 늘어나는 횟 수는 2의 제곱근만큼 늘어난다.

- 점의 개수는 2,3,5, 즉 이전 버전의 (점의 개수 + 사각형의 개수) 이다. 

 

즉, 점배열[i] = 2의 제곱근 배열[i-1] + 점배열[i-1]

const n = require('fs').readFileSync('/dev/stdin').toString().trim()*1
// console.log(n)

let count = [1]; //정사각형의 개수
let dot = [2]; // 선의 개수이자 한 선의 점의 개수

for (let i=1;i<=n;i++){
    count.push(2**i)
    dot.push(count[i-1]+dot[i-1])
}
console.log(dot[n]*dot[n])

 

 

전광판

 

문제 설명

현대차그룹에 다니는 당신은 전세계 유가 변동에 대해 실시간으로 파악하기 위해 사무실에 유가를 실시간으로 표시하는 전광판을 설치하였다. 전광판은 최대 다섯 자리의 자연수만을 표시할 수 있도록, 아래와 같이 육각형 모양의 전구 7×5=35개로 구성되어 있다.

 

 

8자 모양의 전구 묶음은 0부터 9까지의 숫자를 표현할 수 있으며, 표현 방법은 아래와 같다. 아래 그림에서 전구가 켜졌으면 검정색, 꺼졌으면 옅은 회색으로 표현되었다.

각각의 전구에는 스위치가 달려 있다. 전구에 달려 있는 스위치를 누를 때, 그 전구가 켜져 있었다면 꺼지고, 그 전구가 꺼져 있었다면 켜진다.

 

지금 전광판에 자연수 A가 표시되어 있는데, 유가가 변동됨에 따라 전광판에 표시된 자연수를 B로 바꿔야 한다. 이러한 목표를 달성하기 위해 스위치를 최소 몇 번 눌러야 하는지를 구하는 프로그램을 작성하라.

 

문제풀이

- 각 전구는 7개의 스위치가 달려있으므로 1은 켜져있는 것, 0은 꺼져 있는 것으로 string으로 만든다.

  ex) str = "1111111"

 

- 길이가 다를 경우 앞에 '0'을 붙여 현재 전구와 바꿔야 할 전구를 확인해 다른 개수를 더해준다.