1, 2, 3으로만 이루어진 수열 바코드를 만들어야 합니다. 무조건 1, 2, 3만 붙여서 바코드를 만들었다면 쉬웠겠지만, 아쉽게도 바코드를 만드는 데에 조건이 걸려 있습니다. 바코드에서 인접한 두 개의 부분 수열이 동일하다면 제작할 수 없다고 할 때, 주어진 길이 len의 바코드 중 가장 작은 수를 반환하는 함수를 작성하세요.
만들 수 없는 바코드만들 수 있는 바코드
112
1312
1231312
3
232312
231213
부분수열? 주어진 수열에서 연속된 모든 구간을 말합니다. 수열 123의 부분수열은 1, 2, 3, 12, 23, 123 입니다.
인접한 두 부분수열? 첫번째 부분수열과 두번째 부분수열이 연속된 경우를 말합니다.
수열 1234에서 인접한 부분수열 (우리는 두 부분수열이 같은 지 관심이 있으므로 길이가 서로 다른 경우는 무시한다)
1과 2, 2와 3, 3과 4, 12와 34입니다.
만들 수 없는 바코드를 보자면,
'11'2
12'3131'2
'2323'12 인접한 두 개의 부분 수열이 동일하기 때문에 만들 수 없습니다. 고로, '12131213'과 같이 네 자리씩 중복되어도 만들 수 없습니다. 자릿수와 상관없이, 인접한(붙어있는) 부분수열이 같다면 바코드를 만들 수 없습니다.
입력
인자 1: len
Number 타입의 1 이상 50 이하의 자연수
출력
String 타입을 리턴해야 합니다.
예시로, 121도, 123도 전부 바코드로 제작할 수 있지만 제일 작은 수는 121이기 때문에 121을 반환해야 합니다.
function connectedVertices(edges) {
let result = []
for(let edge of edges){
//result: [[0,1],[2,3]]
//edge : 3,4
let li = edge
let flag = false;
//toDo
for(let el of result){
//el: [2,3]
if(el.includes(edge[0]) || el.includes(edge[1])){
flag = true
if(el.includes(edge[0])){
el.push(edge[1])
}
else{
el.push(edge[0])
}
}
}
if(flag === false){
result.push(li)
}
}
let combine = function(arr){
let result = []
for(let i =0; i<arr.length; i++){
let nextArr = arr[i+1] || []
let flag= false;
for(let j=0;j<nextArr.length;j++){
if(arr[i].includes(nextArr[j])){
flag = true
}
}
if(flag){//포함이 되있다.
result.push(arr[i].concat(nextArr))//서로 포함관계인 두 요소를 합치고
arr[i + 1] = arr[i+2] //합쳐졌으니 자리를 옮겨준다
result = combine(result) //포함이 있는지 다시 확인. 있다면 다시 포함.없으면 그대로
}else{
result.push(arr[i])
if(i === arr.length-1 && nextArr.length >= 1){
result.push(nextArr)
}
}
}
return result
}
let result2 = combine(result)
let tempArr = result2.slice()
for(let el of tempArr){
if(el === undefined){
result2.pop()
}
}
return result2.length
}
방향이 있는 간선과 방향이 없는 간선들의 목록들을 받아 2차원 배열의 인접행렬을 반환하는 함수를 작성하세요.
조건
각 간선은 3가지 정보를 담고 있습니다.
0번째: 간선의 시작 정점 (0 이상의 정수)
1번째: 간선의 도착 정점 (0 이상의 정수)
2번째: 방향성 ('undirected' 일시 무향, 'directed' 일시 방향)
입력
인자 1: edges
Number 타입의 방향/무향인 간선들의 목록이 담긴 배열
출력
Array 타입을 리턴해야 합니다.
2차원 배열의 인접 행렬
주의사항
정점 0에서 정점4로 이어주는 간선이 존재할 경우 정점 1, 2, 3도 존재합니다.
반환하는 인접행렬은 2차원 배열이며, 행(row)는 바깥 배열, 열(column)은 안쪽 배열입니다.
let matrix = [[0, 0], [0, 0]]
matrix[0] === 0번째 행
matrix[0][0] === 0번째 행의 0번째 열
두 정점간의 간선의 유무는 0과 1로 표시합니다.
0: 두 정점간에 간선이 존재하지 않을 경우
1: 두 정점간에 간선이 존재할 경우
아래의 2차원 배열에서 세로축은 시작 정점, 가로축은 도착 정점입니다.
const matrix =[[0,0,0],[0,0,0],[0,0,0],];
function createMatrix(edges) {
// TODO: 여기에 코드를 작성합니다.
let maxNum = 0
let numArr= []
for(let a of edges){//배열의 크기 정하기(가장 큰 숫자 찾기)
for(let b of a){
if(typeof b === 'number'){
numArr.push(b)
}
}
}
maxNum = Math.max(...numArr)
let matrix = []
for(let i =0; i <= maxNum;i++){//배열 만들기
matrix.push(new Array(maxNum + 1).fill(0))
}
//좌표 찾아서 값 바꾸기
for(let edge of edges){
matrix[edge[0]][edge[1]] = 1
if(edge[2] === 'undirected'){
matrix[edge[1]][edge[0]] = 1
}
}
return matrix
}
선생님께서는 미리 모든 발표 순서의 경우의 수를 저장해 놓았지만 김코딩의 버릇을 고치기 위해 문제를 내겠다고 말씀하셨습니다.
김코딩은 모든 조별 발표 순서에 대한 경우의 수를 차례대로 구한 뒤, 선생님께서 숫자를 말하면 그 순서에 맞는 경우의 수를 말해야 하고, 발표 순서를 말하면 이 발표순서가 몇번째 경우의 수인지를 대답해야 합니다.
총 학생의 수 N과 선생님이 말하는 k가 주어질 때, 김코딩이 정답을 말 할 수 있게 올바른 리턴 값을 구하세요.
모든 경우의 수가 담긴 배열은 번호가 작을수록 앞에 위치한다고 가정합니다. ex) N = 3일경우, [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
입력
인자 1: n
Number 타입의 1 <= N <= 20인 조의 갯수
인자 2: k
k가 Number 일 때, k번째 배열을 리턴합니다.
ex) n이 3이고 k가 3일 경우
모든 경우의 수를 2차원 배열에 담는다면 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]이 되고,
반환하는 값은 [2, 3, 1]이 됩니다.
k가 Array일 때, 몇 번째인지를 리턴합니다. (0 <= index 입니다.)
ex) n이 3이고 k가 [2, 3, 1]일 경우
모든 경우의 수를 2차원 배열에 담는다면 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]이 되고,
반환하는 값은 3이 됩니다.
function orderOfPresentation(n, k) {
// TODO: 여기에 코드를 작성합니다.
let numbers = []
for(let i = 1; i<=n ; i++){
numbers.push(i)
}
//obj에다가 key를 경우의 수로 두고 value를 boolean으로 줘서 이미 사용했던 숫자인지 판별
//만들었던 숫자이면 for문 안에서 numbers의 인덱스를 올려서 숫자 조합하기.
//n이 몇이 될지 모르니까 재귀를 통해서 구현해야한다.
//조합한 숫자는 result에 담고 obj에 키로 추가
//사용했던 카드의 정보를 담아야한다
let result = []
// let rec = (obj = {} ,combinated = '') =>{
// for(let i = 0; i < numbers.length; i++){//카드들을 순회
// //카드를 선택하기전에 사용가능한 카드인지 확인
// if(obj[numbers[i]] === true || obj[numbers[i]] === undefined){//사용 가능한 카드
// combinated += numbers[i]//카드를 선택하고
// obj[numbers[i]] = false //사용했던 카드로 표시
// console.log('combinated: ', combinated)
// console.log('obj[numbers[i]]: ', obj[numbers[i]])
// //그다음 카드를 선택하기 위해 재귀
// if(combinated.length < n){
// console.log("재귀-----------")
// combinated = rec(obj,combinated)
// }
// else{//카드가 다 만들어지면 체크
// let strArr = combinated.split('')
// let numArr = strArr.map((el)=>Number(el))
// //result에 넣기전에 숫자로 변환시키기
// result.push(numArr)
// console.log('result: ', result)
// }
// combinated = combinated.slice(0,-1) //다음 숫자 확인을 위해 썼던거 뺴주기
// obj[numbers[i]] = true //재귀가 끝났으니 다시 사용 가능하게 해줌
// }
// console.log("obj: ", obj)
// console.log('end of for loop @@@@@@@@@@@@@@@@@@@@')
// }
// return combinated
// }
// rec()
//위의 코드는 나의 코드인데 아래 코드처럼 순회해야하는 배열 자체를 줄여주면 더 효율적으로 순회할 수 있다
const permutation = (arr, m = []) => {
// 탈출 조건을 생성합니다.
// arr의 length가 0일 때 result에 만들어진 발표 순서 배열을 담습니다.
if (arr.length === 0) {
result.push(m);
} else {
// 순열의 재료가 담긴 배열을 순환합니다.
for (let i = 0; i < arr.length; i++) {
// 현재 배열을 카피합니다. (원본을 건드리면 모든 경우의 수를 찾을 수 없습니다.)
let currentArray = arr.slice();
// 제일 앞에 있는 요소를 가지고 와서 변수에 할당합니다.
let element = currentArray.splice(i, 1);
// 제일 앞에 있는 요소가 사라진 배열 ([1, 2, 3]이었다면 현재는 [2, 3])을 arr 인자에 넣고, m 배열과 element를 합쳐서 m 인자에 넣습니다.
permutation(currentArray.slice(), m.concat(element));
// 이렇게 되면 다음은 [2, 3]을 카피하고, element가 [2]가 될 것이며
// 제일 앞에 있는 요소가 사라진 배열 [3]이 arr에 들어갈 것이고, element는 m과 다시 합쳐져 [1, 2]를 만들 것입니다.
// 이렇게 계속 재귀를 돌려서 m이 [1, 2, 3]이 되면, arr의 lenght는 0이 될 것이고, 재귀에서 빠져나옵니다.
// arr === []일 때(m이 [1, 2, 3]) result에 push를 하여 함수를 종료하고, 그다음 arr === [3]일 때(m이 [1, 2]) for문의 길이가 1이었으므로 함수를 그대로 종료하고,
// arr === [2, 3]일 때(m이 [1]) for문은 arr.length에 따라 2번 돌기 때문에 2를 지나 3이 될 것입니다.
// [1] => [1, 3] => [1, 3, 2] => (1의 모든 경우의 수를 다 돌았으니 2로 진입) [2] => [2, 1] => [2, 1, 3] ...
}
}
};
permutation(numbers);
console.log('final result: ', result)
//리턴
if(Array.isArray(k)){
return result.findIndex((el)=>{
return String(el) === String(k)
})
}else{
return result[k]
}
}
orderOfPresentation(5,3) //5만들어오게 되도 경우의수가 120가지, 9가 들어오게되면 36만가지가된다.
Javascript는 프로토타입 기반 언어라고도 불리우는데, 모든 객체들이 속성과 메서드를 상속받기 위해 프로토타입 객체를 기본적으로 갖고있다. 상속받은 메서드와 속성들은 프로토타입 객체에 담긴다. 객체 인스턴스와 프로토타입간의 연결이 구성되고 이 연결을 따라 프로토타입 체인을 타고 올라가며 속성과 메서드를 탐색한다.
