[알고리즘 풀이_Lv0] 저주의 숫자3, 다항식 더하기, 안전지대, 겹치는 선분의 길이

*제주코딩베이스캠프의 JavaScript 알고리즘 100일 챌린지를 참고로 정리하고 있습니다.*

 

저주의 숫자3_32번째

문제

---

https://school.programmers.co.kr/learn/courses/30/lessons/120871

프로그래머스

3x 마을 사람들은 3을 저주의 숫자라고 생각하기 때문에 3의 배수와 숫자 3을 사용하지 않습니다. 

3x 마을 사람들의 숫자는 다음과 같습니다.

 

해결방안

---

방법1_for, while 사용

function solution(n) {
    let answer = 0;
    
    // i는 의미없는 반복이기 때문에 _로 처리
    // _는 숫자를 사용안할 때 사용
    for(let _ =0; _ < n; _++){
        answer += 1;
        
        // 3의 배수이냐 || 숫자3이 들어있냐
        while(answer % 3 == 0 || answer.toString().split('').includes('3')){
            answer += 1 // 해당될때마다 계속 건너뛴다.
        }
    }
    return answer;
}

 

방법 2_제한 사항을 활용해서 구하기(1 ≤ n ≤ 100)

function solution(n) {
    let arr = [];
    
    for(let i =0; i < 100; i++){
        if(i % 3 !== 0 && !i.toString().split('').includes('3')){
            arr.push(i)
        }
    }
    return arr;
}

[1,2,4,5,7,8,10,11,14,16,17,19,20,
22,25,26,28,29,40,41,44,46,47,49,50,
52,55,56,58,59,61,62,64,65,67,68,70,
71,74,76,77,79,80,82,85,86,88,89,
91,92,94,95,97,98]

 

function solution(n) {
    let arr = [];
    
    for(let i = 0; i < 100; i++){
        if(i % 3 !== 0 && !i.toString().split('').includes('3')){
            arr.push(i)
        }
    }
    return arr[n-1];
}

이렇게만 쓰면 실패한다.

100을 1000으로 쓰면 통과가 된다. (중간에 생략되는 값이 발생하기 때문에 넉넉하게 숫자를 넣어야 된다.)

function solution(n) {
    let arr = [];
    
    for(let i =1; i < 1000; i++){
        if(i % 3 !== 0 && !i.toString().split('').includes('3')){
            arr.push(i)
        }
    }
    return arr[n-1];
}

 

소스코드

---

// 방법1
function solution(n) {
    let answer = 0;
    
    for(let _ =0; _ < n; _++){
        answer += 1;
        while(answer % 3 == 0 || answer.toString().split('').includes('3')){
            answer += 1
        }
    }
    return answer;
}

// 방법2
function solution(n) {
    let arr = [];
    
    for(let i =1; i < 1000; i++){
        if(i % 3 !== 0 && !i.toString().split('').includes('3')){
            arr.push(i)
        }
    }
    return arr[n-1];
}

---

다항식 더하기_33번째

문제

---

https://school.programmers.co.kr/learn/courses/30/lessons/120863

프로그래머스

한 개 이상의 항의 합으로 이루어진 식을 다항식이라고 합니다. 

다항식을 계산할 때는 동류항끼리 계산해 정리합니다. 

덧셈으로 이루어진 다항식 polynomial이 매개변수로 주어질 때, 

동류항끼리 더한 결괏값을 문자열로 return 하도록 solution 함수를 완성해보세요. 

같은 식이라면 가장 짧은 수식을 return 합니다.

 

계수 1은 생략합니다. → 1x = x

 

해결방안

---

function solution(polynomial) {
    let arr = polynomial.split(' + ')
    return arr;
}

// "3x + 7 + x"
// ["3x","7","x"]

// "x + x + x"
// ["x","x","x"]

 

x항 처리하기

x항만 뽑기

function solution(polynomial) {
    var answer = '';
    let arr = polynomial.split(' + ')
    return arr.filter(v=>v.includes('x'));
}

// "3x + 7 + x"
// ["3x","x"]

// "x + x + x"
// ["x","x","x"]

 

x항에서 숫자만 뽑기

function solution(polynomial) {
    let arr = polynomial.split(' + ')
    return arr.filter(v=>v.includes('x')).map(v=>v.replace('x', '') || '1');
}

// "3x + 7 + x"
// ["3","1"]

// "x + x + x"
// ["1","1","1"]

 

x항 더해주기

function solution(polynomial) {
    let arr = polynomial.split(' + ')
    return arr
    	.filter(v=>v.includes('x'))
        .map(v=>parseInt(v.replace('x', '')) || 1)
        .reduce((a, c)=>a+c,0);
}

// "3x + 7 + x"
// 4

// "x + x + x"
// 3

 

일반항 처리하기

function solution(polynomial) {
    let arr = polynomial.split(' + ')
    
    return arr
        .filter(v=>!v.includes('x'))
        .reduce((a, c)=>a+parseInt(c),0);
}

// "3x + 7 + x"
// 7

// "x + x + x"
// 0

 

x항 + 일반항

function solution(polynomial) {
    const arr = polynomial.split(' + ')
    
    const x항 = arr
        .filter(v=>v.includes('x'))
        .map(v=>parseInt(v.replace('x', '')) || 1)
        .reduce((a, c)=>a+c,0);
    
    const 일반항 = arr
        .filter(v=>!v.includes('x'))
        .reduce((a, c)=>a+parseInt(c),0);
    
    const answer = [];
    if(x항 === 1){
        answer.push('x')
    }else{
        answer.push(`${x항}x`)
    }
    
    if(일반항){
        answer.push(일반항)
    }
    
    return answer.join(' + ');
}

이렇게 쓰면 실패함

이유. x항이 0일경우도 있기 때문이다.

if(x항) 넣어주기

function solution(polynomial) {
    const arr = polynomial.split(' + ')
    
    const x항 = arr
        .filter(v=>v.includes('x'))
        .map(v=>parseInt(v.replace('x', '')) || 1)
        .reduce((a, c)=>a+c,0);
    
    const 일반항 = arr
        .filter(v=>!v.includes('x'))
        .reduce((a, c)=>a+parseInt(c),0);
    
    const answer = [];
    if(x항){
        if(x항 === 1){
            answer.push('x')
        }else{
            answer.push(`${x항}x`)
        }
        
    }
    
    if(일반항){
        answer.push(일반항)
    }
    
    return answer.join(' + ');
}

 

소스코드

---

function solution(polynomial) {
    const arr = polynomial.split(' + ');
    
    const x항 = arr
        .filter(v=>v.includes('x'))
        .map(v=>parseInt(v.replace('x', '')) || 1)
        .reduce((a, c)=>a+c,0);
    
    const 일반항 = arr
        .filter(v=>!v.includes('x'))
        .reduce((a, c)=>a+parseInt(c),0);
    
    const answer = [];
    x항 && answer.push(x항 === 1 ? 'x' : `${x항}x`);
    일반항 && answer.push(일반항);
    
    return answer.join(' + ');
}

---

안전지대_34번째

문제

---

https://school.programmers.co.kr/learn/courses/30/lessons/120866

프로그래머스

다음 그림과 같이 지뢰가 있는 지역과 지뢰에 인접한 위, 아래, 좌, 우 대각선 칸을 모두 위험지역으로 분류합니다.

지뢰는 2차원 배열 board에 1로 표시되어 있고 board에는 지뢰가 매설 된 지역 1과, 지뢰가 없는 지역 0만 존재합니다.
지뢰가 매설된 지역의 지도 board가 매개변수로 주어질 때, 안전한 지역의 칸 수를 return하도록 solution 함수를 완성해주세요.

 

해결방안

---

8개의 방향 모두 지정

const d = [
    [0,0],
    [0,1],
    [0,-1],
    [1,1],
    [1,0],
    [1,-1],
    [-1,-1],
    [-1,0],
    [-1,1],
]

 

같은 위치의 값이 들어오면 제거하기 위해 set을 사용한다.

let dangerZone = new Set()

 

이렇게만 작성하면 i, j가 0일때 음수값이 나오고, i, j가 n일때 n보다 큰수가 나온다.

const n = board.length;

for(let i=0; i<n; i++){
    for(let j=0; j<n; j++){
        if(board[i][j] === 1){
            d.forEach(v=>i+v[0], j+v[1])
        }
    }
}

 

그러므로 조건을 걸어줘야 된다.

for(let i=0; i<n; i++){
    for(let j=0; j<n; j++){
        if(board[i][j] === 1){
            d.forEach(v=>{
                let [col, row] = [i+v[0], j+v[1]]
                if(col>=0 && col<n && row>=0 && row<n){
                    dangerZone.add(col+" "+row)
                }
            })
        }
    }
}

 

function solution(board) {
    const n = board.length;
    const d = [
        [0,0],
        [0,1],
        [0,-1],
        [1,1],
        [1,0],
        [1,-1],
        [-1,-1],
        [-1,0],
        [-1,1],
    ]
    let dangerZone = new Set();
    for(let i=0; i<n; i++){
        for(let j=0; j<n; j++){
            if(board[i][j] === 1){
                d.forEach(v=>{
                    let [col, row] = [i+v[0], j+v[1]]
                    if(col>=0 && col<n && row>=0 && row<n){
                        dangerZone.add(col+" "+row)
                    }
                    
                })
            }
        }
    }
    console.log(dangerZone)
}

// [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 0, 0]]
// Set(9) { '3 2', '3 3', '3 1', '4 3', '4 2', '4 1', '2 1', '2 2', '2 3' }

 

소스코드

---

function solution(board) {
    const n = board.length;
    const d = [
        [0,0],
        [0,1],
        [0,-1],
        [1,1],
        [1,0],
        [1,-1],
        [-1,-1],
        [-1,0],
        [-1,1],
    ];
    
    let dangerZone = new Set();
    for(let i=0; i<n; i++){
        for(let j=0; j<n; j++){
            if(board[i][j] === 1){
                d.forEach(v=>{
                    let [col, row] = [i+v[0], j+v[1]]
                    if(col>=0 && col<n && row>=0 && row<n){
                        dangerZone.add(col+" "+row)
                    }
                })
            }
        }
    }
    return n*n - dangerZone.size
}

---

겹치는 선분의 길이_35번째

문제

---

https://school.programmers.co.kr/learn/courses/30/lessons/120876

프로그래머스

선분 3개가 평행하게 놓여 있습니다. 세 선분의 시작과 끝 좌표가 [[start, end], [start, end], [start, end]] 형태로 들어있는 2차원 배열 lines가 매개변수로 주어질 때, 두 개 이상의 선분이 겹치는 부분의 길이를 return 하도록 solution 함수를 완성해보세요.

lines가 [[0, 2], [-3, -1], [-2, 1]]일 때 그림으로 나타내면 다음과 같습니다.

선분이 두 개 이상 겹친 곳은 [-2, -1], [0, 1]로 길이 2만큼 겹쳐있습니다.

 

해결방안

---

lines의 원소는 [a, b] 형태이며, a, b는 각각 선분의 양 끝점 입니다.
-100 ≤ a < b ≤ 100를 0 ~ 200으로 바꿉니다.

function solution(lines) {
    let line = new Array(200).fill(0)
    return line;
}
// (200) [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

 

1보다 큰값은 다 곂쳐는 선

function solution(lines) {
    let line = new Array(20).fill(0)
    lines.forEach(([min, max]) => {
        for(; min < max; min++){
            line[min]++
        }
    });
    return line;
}

// [[0, 1], [2, 5], [3, 9]]
// [1,0,1,2,2,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0]

 

0보다 큰 수 추출

function solution(lines) {
    let line = new Array(200).fill(0)
    lines.forEach(([min, max]) => {
        for(; min < max; min++){
            line[min+100]++ // +100하면 -100까지의 음수도 고려한거임
        }
    });
    return line.filter(v=>v>0);
}

// [[0, 1], [2, 5], [3, 9]]
// [1,1,2,2,1,1,1,1]

 

1보다 큰수 추출

function solution(lines) {
    let line = new Array(200).fill(0)
    lines.forEach(([min, max]) => {
        for(; min < max; min++){
            line[min+100]++ // +100하면 -100까지의 음수도 고려한거임
        }
    });
    return line.filter(v=>v>1);
}

// [[0, 1], [2, 5], [3, 9]]
// [2,2]

 

 

소스코드

---

function solution(lines) {
    let line = new Array(200).fill(0)
    lines.forEach(([min, max]) => {
        for(; min < max; min++){
            line[min+100]++;
        }
    });
    return line.filter(v=>v>1).length;
}