[TIL] 알고리즘 문제 javascript

2019년 상반기 LINE 인턴 채용 코딩테스트

나 잡아 봐라

Q. 연인 코니와 브라운은 광활한 들판에서 ‘나 잡아 봐라’ 게임을 한다.
이 게임은 브라운이 코니를 잡거나, 코니가 너무 멀리 달아나면 끝난다.
게임이 끝나는데 걸리는 최소 시간을 구하시오.

조건은 다음과 같다.
코니는 처음 위치 C에서 1초 후 1만큼 움직이고,
이후에는 가속이 붙어 매 초마다 이전 이동 거리 + 1만큼 움직인다.
즉 시간에 따른 코니의 위치는 C, C + 1, C + 3, C + 6, …이다.

브라운은 현재 위치 B에서 다음 순간 B – 1, B + 1, 2 * B 중 하나로 움직일 수 있다.
코니와 브라운의 위치 p는 조건 0 <= x <= 200,000을 만족한다.
브라운은 범위를 벗어나는 위치로는 이동할 수 없고, 코니가 범위를 벗어나면 게임이 끝난다

(10,3) => 결과 = 3
(51,50) => 결과 = 8
(550,500) => 결과 = 28

// Queue를 사용하기 위해 긁어 왔다.
// 출처: https://velog.io/@longroadhome/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-JS%EB%A1%9C-%EA%B5%AC%ED%98%84%ED%95%98%EB%8A%94-.%ED%81%90-Queue

class Queue {
	constructor() {
		this.storage = {}
		this.front = 0
		this.rear = 0
	}

	size() {
		if (this.storage[this.rear] === undefined) {
			return 0
		} else {
			return this.rear - this.front + 1
		}
	}

	add(value) {
		if (this.size() === 0) {
			this.storage['0'] = value
		} else {
			this.rear += 1
			this.storage[this.rear] = value
		}
	}

	popleft() {
		let temp
		if (this.front === this.rear) {
			temp = this.storage[this.front]
			delete this.storage[this.front]
			this.front = 0
			this.rear = 0
		} else {
			temp = this.storage[this.front]
			delete this.storage[this.front]
			this.front += 1
		}
		return temp
	}
}

// DFS와 DP가 혼합된 문제

let cony = 550
let brown = 500

const queue = new Queue()
queue.add(brown)

let runaway = 1
let time = 1
let endCheck = false

const visited = []
for (let i = 0; i < 200000; i++) {
	visited.push({})
}

while (!endCheck) {
	cony += runaway++
	time++

    if (cony > 200000) break

	const size = queue.size()
	for (let i = 0; i < size; i++) {
		const toCalculate = queue.popleft()

		if (
			cony === toCalculate - 1 ||
			cony === toCalculate + 1 ||
			cony === toCalculate * 2
		) {
			endCheck = true
			break
		}

		if (toCalculate - 1 >= 0 && toCalculate - 1 <= 200000) {
			if (!visited[toCalculate - 1][time]) {
				queue.add(toCalculate - 1)
				visited[toCalculate - 1][time] = true
			}
		}

        if (toCalculate + 1 >= 0 && toCalculate + 1 <= 200000) {
			if (!visited[toCalculate + 1][time]) {
				queue.add(toCalculate + 1)
				visited[toCalculate + 1][time] = true
			}
		}

        if (toCalculate * 2 >= 0 && toCalculate * 2 <= 200000) {
			if (!visited[toCalculate * 2][time]) {
				queue.add(toCalculate * 2)
				visited[toCalculate * 2][time] = true
			}
		}
	}
}
console.log(time - 1)

백준 14503 로봇 청소기

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

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

let [_, [h, w, d], ...map] = input
	.map((x) => x.split(' '))
	.map((x) => x.map((x) => +x))

// 북 동 남 서
const dh = [-1, 0, 1, 0]
const dw = [0, 1, 0, -1]

let count = 0
while (true) {
	// 현재 칸 청소
	if (map[h][w] !== -1) {
		map[h][w] = -1
		count++
	}

	// 방향 정의
	const left_d = d === 0 ? 3 : d - 1
	const right_d = d === 3 ? 0 : d + 1
	let back_d
	if (d === 2) {
		back_d = 0
	} else if (d === 3) {
		back_d = 1
	} else {
		back_d = d + 2
	}

	const left_dh = dh[left_d]
	const left_dw = dw[left_d]
	const right_dh = dh[right_d]
	const right_dw = dw[right_d]
	const back_dh = dh[back_d]
	const back_dw = dw[back_d]
	const front_dh = dh[d]
	const front_dw = dw[d]

	// 왼쪽 칸의 숫자 확인
	if (map[h + left_dh][w + left_dw] === 0) {
		d = left_d
		h += left_dh
		w += left_dw
	} else if (
		map[h + left_dh][w + left_dw] !== 0 &&
		map[h + right_dh][w + right_dw] !== 0 &&
		map[h + front_dh][w + front_dw] !== 0 &&
		map[h + back_dh][w + back_dw] !== 0
	) {
		if (map[h + back_dh][w + back_dw] === 1) {
			break
		} else if (map[h + back_dh][w + back_dw] === -1) {
			h += dh[back_d]
			w += dw[back_d]
		}
	} else {
		d = left_d
	}
}
console.log(count)

(추가) 프로그래머스 문자열 압축 문제 복습