Problem (lev.2) : 멀쩡한 사각형
-
가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.
-
가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.
-
제한 사항
- W, H : 1억 이하의 자연수
-
예시 1:
- 입력값 : w = 8, h = 12
- 출력값 : 80
- 설명 :
- 가로가 8, 세로가 12인 직사각형을 대각선 방향으로 자르면 총 16개 정사각형을 사용할 수 없게 됩니다. 원래 직사각형에서는 96개의 정사각형을 만들 수 있었으므로, 96 - 16 = 80 을 반환합니다.
Solution
function solution(w, h) {
function getMaximumDivisor(dividend, divisor){
const remainder = dividend % divisor;
if (remainder === 0) {
return divisor;
}
return getMaximumDivisor(divisor, remainder);
}
// crossArea = width + height - (maxminum divisior between weight and height)
const maximumDivisor = getMaximumDivisor(w, h);
const crossArea = w + h - maximumDivisor;
const result = w * h - crossArea;
return result;
}Problem (lev.2) : 스킬트리
-
선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.
- 예를 들어 선행 스킬 순서가
스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.
- 예를 들어 선행 스킬 순서가
-
위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서
스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만,썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다. -
선행 스킬 순서 skill과 유저들이 만든 스킬트리를 담은 배열
skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요. -
제한 조건
- 스킬은 알파벳 대문자로 표기하며, 모든 문자열은 알파벳 대문자로만 이루어져 있습니다.
- 스킬 순서와 스킬트리는 문자열로 표기합니다.
- 예를 들어,
C → B → D라면 "CBD"로 표기합니다
- 예를 들어,
- 선행 스킬 순서 skill의 길이는 1 이상 26 이하이며, 스킬은 중복해 주어지지 않습니다.
skill_trees는 길이 1 이상 20 이하인 배열입니다.skill_trees의 원소는 스킬을 나타내는 문자열입니다.skill_trees의 원소는 길이가 2 이상 26 이하인 문자열이며, 스킬이 중복해 주어지지 않습니다.
-
예시 1:
- 입력값 : skill = "CBD", skill_trees = ["BACDE", "CBADF", "AECB", "BDA"]
- 반환값 : 2
- 설명 :
- "BACDE": B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트립니다.
- "CBADF": 가능한 스킬트리입니다.
- "AECB": 가능한 스킬트리입니다.
- "BDA": B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트리입니다.
Solution
function solution(skill, skill_trees) {
let answer = skill_trees.length;
const prerequisiteTrees = skill_trees.map((skillTree) => {
return skillTree.split('').filter((str) => skill.includes(str));
});
let currSkillTree;
for (let i = 0; i < prerequisiteTrees.length; i++) {
currSkillTree = prerequisiteTrees[i];
console.log(currSkillTree, answer);
for (let j = 0; j < currSkillTree.length; j++) {
if (currSkillTree[j] !== skill[j]) {
answer--;
break;
}
}
}
return answer;
}Problem (lev.2) : 영어 끝말잇기
- 1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있습니다. 영어 끝말잇기는 다음과 같은 규칙으로 진행됩니다.
- 1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다.
- 마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다.
- 앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다.
- 이전에 등장했던 단어는 사용할 수 없습니다.
- 한 글자인 단어는 인정되지 않습니다.
- 다음은 3명이 끝말잇기를 하는 상황을 나타냅니다.
- tank → kick → know → wheel → land → dream → mother → robot → tank
- 위 끝말잇기는 다음과 같이 진행됩니다.
- 1번 사람이 자신의 첫 번째 차례에 tank를 말합니다.
- 2번 사람이 자신의 첫 번째 차례에 kick을 말합니다.
- 3번 사람이 자신의 첫 번째 차례에 know를 말합니다.
- 1번 사람이 자신의 두 번째 차례에 wheel을 말합니다.
- (계속 진행)
- 끝말잇기를 계속 진행해 나가다 보면, 3번 사람이 자신의 세 번째 차례에 말한 tank 라는 단어는 이전에 등장했던 단어이므로 탈락하게 됩니다.
- 사람의 수
n과 사람들이 순서대로 말한 단어words가 매개변수로 주어질 때, 가장 먼저 탈락하는 사람의 번호와 그 사람이 자신의 몇 번째 차례에 탈락하는지를 구해서 return 하도록 solution 함수를 완성해주세요. - 제한 사항
- 끝말잇기에 참여하는 사람의 수
n은 2 이상 10 이하의 자연수입니다. words는 끝말잇기에 사용한 단어들이 순서대로 들어있는 배열이며, 길이는 n 이상 100 이하입니다.- 단어의 길이는 2 이상 50 이하입니다.
- 모든 단어는 알파벳 소문자로만 이루어져 있습니다.
- 끝말잇기에 사용되는 단어의 뜻(의미)은 신경 쓰지 않으셔도 됩니다.
- 정답은 [ 번호, 차례 ] 형태로 return 해주세요.
- 만약 주어진 단어들로 탈락자가 생기지 않는다면, [0, 0]을 return 해주세요.
- 끝말잇기에 참여하는 사람의 수
- 예시 1:
- 입력값 : n = 3, words = ["tank", "kick", "know", "wheel", "land", "dream", "mother", "robot", "tank"]
- 출력값 : [3, 3]
- 설명 :
- 3명의 사람이 끝말잇기에 참여하고 있습니다.
- 1번 사람 : tank, wheel, mother
- 2번 사람 : kick, land, robot
- 3번 사람 : know, dream,
tank - 와 같은 순서로 말을 하게 되며, 3번 사람이 자신의 세 번째 차례에 말한
tank라는 단어가 1번 사람이 자신의 첫 번째 차례에 말한tank와 같으므로 3번 사람이 자신의 세 번째 차례로 말을 할 때 처음 탈락자가 나오게 됩니다.
- 예시 2:
- 입력값 : n = 5, words = ["hello", "observe", "effect", "take", "either", "recognize", "encourage", "ensure", "establish", "hang", "gather", "refer", "reference", "estimate", "executive"]
- 출력값 : [0, 0]
- 설명 :
- 5명의 사람이 끝말잇기에 참여하고 있습니다.
- 1번 사람 : hello, recognize, gather
- 2번 사람 : observe, encourage, refer
- 3번 사람 : effect, ensure, reference
- 4번 사람 : take, establish, estimate
- 5번 사람 : either, hang, executive
- 와 같은 순서로 말을 하게 되며, 이 경우는 주어진 단어로만으로는 탈락자가 발생하지 않습니다. 따라서 [0, 0]을 return하면 됩니다.
Solution
function solution(n, words) {
let answer = [0, 0];
let usedWords = [];
let word, firstWord, lastWord;
function getDropout(orders) {
const isLast = orders % n === 0;
const loopCount = Math.floor(orders / n);
const user = isLast ? n : orders % n;
const userOrder = isLast ? loopCount : loopCount + 1;
answer = [user, userOrder];
}
for (let i = 0; i < words.length; i++) {
word = words[i];
firstWord = word[0];
if (i !== 0 && firstWord !== lastWord) {
getDropout(i + 1);
break;
}
if (usedWords.includes(word)) {
getDropout(i + 1);
break;
}
lastWord = word[word.length - 1];
usedWords.push(word);
}
return answer;
}- 다른 풀이
function solution(n, words) {
const usedWordSet = new Set();
let stage = 0;
let prevWord = words[0][0];
for (let index = 0; index < words.length; index += n) {
stage += 1;
for (let order = 0; order < n; order++) {
const word = words[index + order];
if (word[0] !== prevWord.at(-1) || usedWordSet.has(word)) {
return [order + 1, stage];
}
usedWordSet.add(word);
prevWord = word;
}
}
return [0, 0];
}Problem (lev.2) : 점프와 순간 이동
-
OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈트는 건전지로 작동되는데, 순간이동을 하면 건전지 사용량이 줄지 않지만, 앞으로 K 칸을 점프하면 K 만큼의 건전지 사용량이 듭니다. 그러므로 아이언 슈트를 착용하고 이동할 때는 순간 이동을 하는 것이 더 효율적입니다. 아이언 슈트 구매자는 아이언 슈트를 착용하고 거리가 N 만큼 떨어져 있는 장소로 가려고 합니다. 단, 건전지 사용량을 줄이기 위해 점프로 이동하는 것은 최소로 하려고 합니다.
-
아이언 슈트 구매자가 이동하려는 거리
N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 return하는 solution 함수를 만들어 주세요. -
예를 들어 거리가 5만큼 떨어져 있는 장소로 가려고 합니다.
- 아이언 슈트를 입고 거리가 5만큼 떨어져 있는 장소로 갈 수 있는 경우의 수는 여러 가지입니다.
- 처음 위치 0 에서 5 칸을 앞으로 점프하면 바로 도착하지만, 건전지 사용량이 5 만큼 듭니다.
- 처음 위치 0 에서 2 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 2) x 2에 해당하는 위치로 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 3 만큼 듭니다.
- 처음 위치 0 에서 1 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 1) x 2에 해당하는 위치로 이동할 수 있으므로 위치 2로 이동됩니다. 이때 다시 순간이동 하면 (현재까지 온 거리 : 2) x 2 만큼 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 2 만큼 듭니다.
- 위의 3가지 경우 거리가 5만큼 떨어져 있는 장소로 가기 위해서 3번째 경우가 건전지 사용량이 가장 적으므로 답은 2가 됩니다.
- 아이언 슈트를 입고 거리가 5만큼 떨어져 있는 장소로 갈 수 있는 경우의 수는 여러 가지입니다.
-
제한 사항
- 숫자 N: 1 이상 10억 이하의 자연수
- 숫자 K: 1 이상의 자연수
Solution
function solution(n){
let answer = 0;
while (n > 0) {
if (n % 2 === 0) {
n /= 2;
} else {
n -= 1;
answer += 1;
}
}
return answer;
}Problem (lev.2) : 방문 길이
-
게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다.
- U: 위쪽으로 한 칸 가기
- D: 아래쪽으로 한 칸 가기
- R: 오른쪽으로 한 칸 가기
- L: 왼쪽으로 한 칸 가기
-
캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다.
- 예를 들어, "ULURRDLLU"로 명령했다면 1번 명령어부터 7번 명령어까지 다음과 같이 움직입니다.
- 8번 명령어부터 9번 명령어까지 다음과 같이 움직입니다.
-
이때, 우리는 게임 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구하려고 합니다.
- 예를 들어 위의 예시에서 게임 캐릭터가 움직인 길이는 9이지만, 캐릭터가 처음 걸어본 길의 길이는 7이 됩니다. (8, 9번 명령어에서 움직인 길은 2, 3번 명령어에서 이미 거쳐 간 길입니다)
-
단, 좌표평면의 경계를 넘어가는 명령어는 무시합니다.
-
예를 들어, "LULLLLLLU"로 명령했다면 1번 명령어부터 6번 명령어대로 움직인 후, 7, 8번 명령어는 무시합니다. 다시 9번 명령어대로 움직입니다.
-
이때 캐릭터가 처음 걸어본 길의 길이는 7이 됩니다.
-
명령어가 매개변수
dirs로 주어질 때, 게임 캐릭터가 처음 걸어본 길의 길이를 구하여 return 하는 solution 함수를 완성해 주세요.
제한사항
dirs는 string형으로 주어지며, 'U', 'D', 'R', 'L' 이외에 문자는 주어지지 않습니다.dirs의 길이는 500 이하의 자연수입니다.
Solution
function solution(dirs) {
let answer = 0;
const coordinates = {
'U': [1, 0],
'D': [-1, 0],
'R': [0, 1],
'L': [0, -1]
};
const visited = new Set();
let start = [5,5];
for (let i = 0; i < dirs.length; i++) {
const coordinate = coordinates[dirs[i]];
const x = start[0] + coordinate[0];
const y = start[1] + coordinate[1];
if (x >= 0 && y >= 0 && x < 11 && y < 11) {
const xline = start[0] + coordinate[0]/2;
const yline = start[1] + coordinate[1]/2;
if (!visited.has(`${xline}${yline}`)) {
answer++;
visited.add(`${xline}${yline}`)
}
start[0] = x;
start[1] = y;
}
}
return answer;
}Problem (lev.3) : 숫자 게임
-
xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다.
- 먼저 모든 사원이 무작위로 자연수를 하나씩 부여받습니다.
- 각 사원은 딱 한 번씩 경기를 합니다.
- 각 경기당 A팀에서 한 사원이, B팀에서 한 사원이 나와 서로의 수를 공개합니다. 그때 숫자가 큰 쪽이 승리하게 되고, 승리한 사원이 속한 팀은 승점을 1점 얻게 됩니다.
- 만약 숫자가 같다면 누구도 승점을 얻지 않습니다.
-
전체 사원들은 우선 무작위로 자연수를 하나씩 부여받았습니다. 그다음 A팀은 빠르게 출전순서를 정했고 자신들의 출전 순서를 B팀에게 공개해버렸습니다. B팀은 그것을 보고 자신들의 최종 승점을 가장 높이는 방법으로 팀원들의 출전 순서를 정했습니다. 이때의 B팀이 얻는 승점을 구해주세요.
-
A 팀원들이 부여받은 수가 출전 순서대로 나열되어있는 배열
A와 i번째 원소가 B팀의 i번 팀원이 부여받은 수를 의미하는 배열B가 주어질 때, B 팀원들이 얻을 수 있는 최대 승점을 return 하도록 solution 함수를 완성해주세요.
제한사항
A와B의 길이는 같습니다.A와B의 길이는 1 이상 100,000 이하입니다.A와B의 각 원소는 1 이상 1,000,000,000 이하의 자연수입니다.
Solution
function solution(A, B) {
let answer = 0;
let indexA = 0;
A.sort((a,b) => b - a);
B.sort((a,b) => b - a);
for (let indexB = 0; indexB < B.length; indexB++) {
const numB = B[indexB];
let canWin = false;
while (!canWin && indexA < A.length) {
const numA = A[indexA];
if (numB > numA) {
canWin = true;
answer++;
}
indexA++;
}
}
return answer;
}Problem (lev.3) : 기지국 설치
-
N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5g 기지국은 4g 기지국보다 전달 범위가 좁아, 4g 기지국을 5g 기지국으로 바꾸면 어떤 아파트에는 전파가 도달하지 않습니다.
-
예를 들어 11개의 아파트가 쭉 늘어서 있고, [4, 11] 번째 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 만약 이 4g 기지국이 전파 도달 거리가 1인 5g 기지국으로 바뀔 경우 모든 아파트에 전파를 전달할 수 없습니다. (전파의 도달 거리가 W일 땐, 기지국이 설치된 아파트를 기준으로 전파를 양쪽으로 W만큼 전달할 수 있습니다.)
-
초기에, 1, 2, 6, 7, 8, 9번째 아파트에는 전파가 전달되지 않습니다.
- 1, 7, 9번째 아파트 옥상에 기지국을 설치할 경우, 모든 아파트에 전파를 전달할 수 있습니다.
- 더 많은 아파트 옥상에 기지국을 설치하면 모든 아파트에 전파를 전달할 수 있습니다.
-
이때, 우리는 5g 기지국을 최소로 설치하면서 모든 아파트에 전파를 전달하려고 합니다. 위의 예시에선 최소 3개의 아파트 옥상에 기지국을 설치해야 모든 아파트에 전파를 전달할 수 있습니다.
-
아파트의 개수
N, 현재 기지국이 설치된 아파트의 번호가 담긴 1차원 배열stations, 전파의 도달 거리W가 매개변수로 주어질 때, 모든 아파트에 전파를 전달하기 위해 증설해야 할 기지국 개수의 최솟값을 리턴하는 solution 함수를 완성해주세요.
제한사항
N: 200,000,000 이하의 자연수stations의 크기: 10,000 이하의 자연수stations는 오름차순으로 정렬되어 있고, 배열에 담긴 수는 N보다 같거나 작은 자연수입니다.
W: 10,000 이하의 자연수
Solution
- 정확성 테스트 통과, 효율성 테스트 시간 초과 풀이
function solution(n, stations, w) {
let answer = 0;
const apartments = new Array(n).fill(false);
stations.forEach((station) => {
let distance = w;
apartments[station - 1] = true;
let frontStation, backStation;
while (distance) {
frontStation = station - 1 - distance;
backStation = station - 1 + distance;
if (frontStation >= 0) {
apartments[frontStation] = true;
}
if (backStation < n) {
apartments[backStation] = true;
}
distance--;
}
});
let apartmentCount = 0;
const cummunicatableGap = 1 + w * 2;
for (let i = 0; i < n; i++) {
let isCommunicatable = apartments[i];
if (isCommunicatable) {
answer += Math.ceil(apartmentCount / cummunicatableGap);
apartmentCount = 0;
} else {
apartmentCount++;
}
}
if (apartmentCount) {
answer += Math.ceil(apartmentCount / cummunicatableGap);
}
return answer;
}- 통과한 풀이
function solution(n, stations, w) {
let answer = 0;
let left = 1;
let distance = 0;
const deliveryRange = (w * 2) + 1;
for (const station of stations) {
let startPosition = station - w;
distance = startPosition - left;
if (startPosition >= 0 && distance > 0) {
answer += Math.ceil(distance / deliveryRange);
}
left = station + w + 1;
}
if (left <= n) {
distance = n + 1 - left;
answer += Math.ceil(distance / deliveryRange);
}
return answer;
}