[Main-Project 개발일지]-25(주말)

오늘은 알고리즘을 풀다가(중간 모집공고 탐방시간 제외) 알고리즘만 계속 풀어버렸다.
문제가 어렵기도 하지만 해결은 계속 할 수 있기 때문에 간만에 계속 푼 것 같다.
문제만 10시간 이상 푼 것 같은데 해결한 문제는 8개밖에 되지 않아 조금 아쉽다.

쉬운 문제들은 해설 없이 그냥 넘겼지만 
문제 난이도가 올라갈수록 빠른 이해 및 혹시 모를 검색자를 위해 주석을 달다보니
그 부분에서도 시간을 잡아먹는 것 같다.

 

CT(1).백준 14728번 벼락치기는 각 과목의 점수배정과 필요한 시간을 보고 지정된 시간 내에 얻을 수 있는 최대 점수를 구하는 문제였다.
일반적인 배낭 문제의 내용물만 바꾼 느낌으로 dp를 역순으로 조회하면 쉽게 해결할 수 있다.

let input = `3 310
50 40
100 70
200 150`.split('\n')

for(let i = 0 ; i < input.length ; i++){ // number type 만들기
    input[i] = input[i].split(' ').map(Number)
}

let time = input[0][1] 
let unit = input[0][0]
let dp = new Array(time+1).fill(0) //시간만큼 dp만들기(index 0때문에 +1)

for(let i = 1 ; i <= unit ; i++){
    let [a,b] = input[i] //구조분해 할당으로 필요시간(a), 점수(b) 선언
    for(let j = time ; j > 0 ; j--){
        if(j >= a){ //필요시간보다 큰 경우 현재값과 필요시간이 제해진 dp값에 b를 더한 값을 비교 후 큰 값 재할당
            dp[j] = Math.max(dp[j],dp[j-a]+b)
        }
    }
}

console.log(dp[time]) // 해당 시간 dp값 반환

CT(2).프로그래머스 스킬트리는 백준에서 풀었던 유사한 문제와는 다르게 0번을 필수적으로 학습한 다음 1번 2번 순서가 되어야 해서 생각보다 오류가 많이 있었던 것 같다.
오름차순이면 된다고 간단하게 생각하고 접근했다가 0부터 시작해야 한다는 것을 다시 인지한 다음 다시 오름차순이지만 1씩 증가해야 하기 때문에 0,1,2식의 1 등차수열이어야 한다는 것을 다시 알고 만약 내용물이 있는 상태에서 시작이 0이 아닌 경우 --, 1씩 증가하지 않는 경우 -- 하는 방식으로 해결할 수 있었다.

function solution(skill, skill_trees) {
    let arr = []
    for (let i = 0 ; i < skill_trees.length ; i++){
        let data = []
        for(let j = 0 ; j < skill_trees[i].length ; j++){
            if(skill.indexOf(skill_trees[i][j]) !== -1){
                data.push(skill.indexOf(skill_trees[i][j]))
            }
        }
        arr.push(data)
    }
    
    let answer = arr.length;
    
    for(let i = 0 ; i < arr.length ; i++){
        if(arr[i].length >= 1 && arr[i][0] !== 0){
            answer--
            continue
        }
        else{
            for(let j = 0 ; j < arr[i].length-1 ; j++){
                if(arr[i][j]+1 !== arr[i][j+1]){
                    answer--
                    break
                }
            }
        }
    }
    
    return answer;
}

CT(3).프로그래머스 게임 맵 최단거리는 저번에 재귀로 도전헀다가 27ms로 실패했었는데 작은 규모의 문제는 유사한 결과를 보여줬지만 큰 규모의 문제인 경우 bfs?방식(인지 정확히 모르겠다)으로 해결하니 7배가량 더 빠른 모습을 보여줬다.
처음에는 오히려 더 오래 걸렸고 map의 1,0으로 된 벽을 도착한 다음 지워주는 방식으로 진행했는데 재귀보다 오래 걸리고 10초 타임아웃으로 실패하게 되는 모습을 보고 같은 거리일 때 인접하는 면은 둘 다 요청을 보낸다는 사실을 알게 되었고 이를 방지하기 위해 queue에 추가할 때 map의 벽 처리를 넣어주자 효율성에서 통과처리가 되었다.

function solution(maps) {
    var answer = -1;
    let aMax = maps.length-1
    let bMax = maps[0].length-1
    let queue = [[0,0,1]]
    
    while(queue.length !== 0){
        let [a,b,length] = queue.shift()
        maps[a][b] = 0 //초기 벽 설정했던 방식
        if(a === aMax && b === bMax){ //도착지점에서 결과값 반환
            answer = length
            break
        }
        if(a-1 >= 0 && maps[a-1][b]){//위
            queue.push([a-1,b,length+1])
            maps[a-1][b] = 0 //마지막에 추가한 벽 처리 방식
        }
        if(a+1 <= aMax && maps[a+1][b]){//아래
            queue.push([a+1,b,length+1])
            maps[a+1][b] = 0
        }
        if(b-1 >= 0 && maps[a][b-1]){//왼쪽
            queue.push([a,b-1,length+1])
            maps[a][b-1] = 0
        }
        if(b+1 <= bMax && maps[a][b+1]){//오른쪽
            queue.push([a,b+1,length+1])
            maps[a][b+1] = 0
        }
    }
    return answer;
}

CT(4).프로그래머스 다리는 지나는 트럭 문제는 조금 아쉬웠다.
일단 스택/큐 문제인데 스택/큐를 구현하지 않아도 되는 부분까지는 원리파악을 위해 문제해결이라고 넘어갈 수 있지만 범위를 1~10000으로 도배해놓고 막상 그정도의 테스트케이스를 내지 않은 것 같았다. 
의사코드는 아래의 1~5로 풀고 있다가 대기열이 1만이고 무게가 1만 또는 5001이상의 만개가 들어간다면 1만대기(다리길이) x 1만회(만개) x 내부 shift, pop을 통한 재배열 1만짜리로 최적화를 하지 않으면 제한조건내에서는 통과되지 않을 것 같았는데 통과되어버렸다.

1.nowWeight를 통해 다리 위 현재 무게와 weight 비교하기
2.무게 제한이라면 0을 push하기
3.마지막 트럭이었다면 0을 push하지 않기
4.while은 대기트럭, 다리를 건너는 트럭의 length가 0이 아닌 경우에 돌아가게 하기(생각해보니 waitting의 앞부분을 채워서 watting만 봐도 될 것 같다.)
5.한바퀴 돌 때마다 1초가 지났다고 감안하고 sec을 선언 후 ++로 경과시간 처리하기

 

문제를 풀던 도중 nowWeight를 선언하고 아래와 같은 문제를 발견했으나 효율성테스트가 없고 제일 오래 걸린 케이스가 7.91ms였다.(정확성 기준 제한시간 10,000ms)

//생각해보니 sum + 0번째값이 들어가지 않는다면 sum.indexOf를 통해 index를 찾아서 0의 갯수만큼 밀어버리는 작업이 있으면 더 빠를 것 같다.
//index와 차이만큼 sum에 더해주면 되고? nowWeight와 sum이 같은 결말이면 뺴줘야 하니 이 부분도 index처리가 맞는데 일단 제출해보고

 

스택/큐 클래스 구현으로 1만1회 작업(배열 재배치)대신 2회 작업으로 끝나고 다음 트럭이 들어오지 못하는 상황이 감지된 순간 현재 index를 감지해 그 만큼의 시간을 경과했다고 처리하는게 맞다고 생각하지만 통과되었기 때문에 지나가긴 하는데

테스트케이스를 추가시켜서 최소한 조건을 그렇게 설정했으면 조건에 맞는 결과가 나오게 헀으면 좋겠다.

function solution(bridge_length, weight, truck_weights) {
    let sec = 1;
    let aa = truck_weights.shift();
    let nowWeight = aa
    let sum = aa
    let waitting = new Array(bridge_length).fill(0)
    waitting[bridge_length-1] = aa
    
    while(sum > 0){
        sec++
        sum -= waitting.shift()
        if(truck_weights.length === 0){
            continue
        }
        else if(sum + truck_weights[0] <= weight){
            nowWeight = truck_weights.shift()
            sum += nowWeight
            waitting.push(nowWeight)
        }
        else{
            waitting.push(0)
        }
    }
    
    return sec;
}

CT(5).프로그래머스 124 나라의 숫자는 1,2,4를 통한 3진법 문제 같지만 0이 없고 1을 기준으로 하기 때문에 상당히 복잡했다...
제일 문제였던 부분은 0이 존재하면 안되고 1이 존재해야 하는데 1의 값을 포함한 자릿수의 값들을 비교해야만 했다.(1111 = 40 등)
이것저것 보는 도중 문자열을 사용해 조건문을 스킵하는 방법도 알 수 있었는데 정확히 문자열의 한 글자를 필요로 할 때만 쓸 수 있는 어중간한 느낌이었다.

function solution(n) {
    answer = ''
    while(n > 0){
        n -= 1
        answer = '124'[n%3] + answer
        n = Math.floor(n/3)
    }
    return answer
}

CT(6).프로그래머스 삼각 달팽이 문제는 삼각형 모양의 배열을 만들어준 다음 일정 규칙(아래, 오른쪽, 왼쪽위 이동)에 따라 숫자를 채운 다음 채워진 내용물을 결과값에 push하는 방식으로 해결할 수 있었다.

function solution(n) {
    let answer = [] //결과용 배열
    let arrs = [] //삼각형 만들 배열
    let now = 1 //현재 값(1~n*(n+1))으로 증가할 예정 
    let a = -1 //a,b는 좌표값으로 0,0부터 시작하게 하기 위해 -1로 했다.
    let b = 0 //이유는 6,5,4,3,2,1형태로 이동 횟수가 줄어드는데 초기값 고정을 위해
    let way = n // 문제를 풀 때 하나씩 줄이려고 했는데 그럴 필요가 없었다
    for(let i = 1 ; i <= n ; i++){ //0으로 채운 삼각형 이중배열 
        arrs.push(new Array(i).fill(0))
    }
    for(let i = 0 ; i < n ; i++){ //이동규칙 1,2,3용
        for(let j = 0 ; j < n-i ; j++){ // 움직일 횟수
            if(i%3 === 0){ //이 함수로 이동규칙에 따라 움직인다.
                a += 1    //아래 이동이므로 a(행)에 1씩 더하며 now를 올린다
                arrs[a][b] = now
                now++
            }
            else if(i%3 === 1){ // 우측 이동
                b += 1 //b(열)에 1씩 더하며 now를 올린다
                arrs[a][b] = now
                now++
            }
            else{ //왼쪽 위 대각선이동
                a -= 1 //행,열 모두에 1씩 감소시켜 왼쪽위로 이동시킨다.
                b -= 1
                arrs[a][b] = now
                now++
            }
        }
    }
    for(let i = 0 ; i < arrs.length ; i++){ //만들어진 배열을 행, 열순으로 결과에 push
        for(let j = 0 ; j < arrs[i].length ; j++){
            answer.push(arrs[i][j])
        }
    }
    return answer;
}

CT(7).프로그래머스 [카카오 인턴] 수식 최대화 문제는 각 기호의 계산 순서에 따라 나올 수 있는 최대값을 구하는 문제였다.
간단히 *,-,+ 세 가지의 조합 6가지를 전부 넣어준 다음 그 순서로 계산하는 함수를 만들어 max값을 출력했다.

function solution(expression) {
    let arr = expression.split('+').join(' + ').split('*').join(' * ').split('-').join(' - ').split(' ') // 문자열 숫자, 기호로 분리
    let answer = [] //값들이 들어갈 배열 선언
    let strs = ["+-*","+*-","*-+","*+-","-*+","-+*"] // 기호 순서 6가지
    for(let i = 0 ; i < strs.length ; i++){ //각 기호로 계산한 값 6가지 answer에 넣기
        answer.push(Math.abs(computing(arr,strs[i])))
    }
    return Math.max(...answer) //answer중 큰 값 출력
}
function computing(arr, str){ 
    let one = [Number(arr[0])] //1,2,3번 기호에 따라 게산
    for(let i = 2 ; i < arr.length ; i+=2){ //첫번째 값은 넣어두고 시작 *(i+2)
        if(arr[i-1] === str[0]){ 만약 이전값이 해당 기호라면 현재값을 기호대로 처리
            one[one.length-1] = eval(`${one[one.length-1]}${str[0]}${arr[i]}`)
        }
        else{ //아닌 경우 기호 및 숫자 넣어주기
            one.push(arr[i-1])
            one.push(Number(arr[i]))
        }
    }
    
    let two = [one[0]] //위와 같은 방식
    for(let i = 2 ; i < one.length ; i+=2){
        if(one[i-1] === str[1]){
            two[two.length-1] = eval(`${two[two.length-1]}${str[1]}${one[i]}`)
        }
        else{
            two.push(one[i-1])
            two.push(Number(one[i]))
        }
    }
    
    let three = [two[0]] //위와 같은 방식
    for(let i = 2 ; i < two.length ; i+=2){
        if(two[i-1] === str[2]){
            three[three.length-1] = eval(`${three[three.length-1]}${str[2]}${two[i]}`)
        }
        else{
            three.push(two[i-1])
            three.push(Number(two[i]))
        }
    }
    
    return three[0] //게산된 결과값 배열 해제해주기
}

CT(8).프로그래머스 숫자 블록 문제는 상단히 난해한 문제였다.
예시를 보고 간단한 의사코드를 작성했는데
  1.소수인 경우 1 
  2.소수가 아닌 경우 나눠지는 가장 큰 몫(가장 큰 인수)가 결과
  3.천만이 넘을 경우 0 처리(아님)
위의 3번과 같은 오류를 시작할 때 넘어가버렸다.
처음에는 천만번까지만 타일을 깔았다고 인식했기 때문인데
이 부분의 코드를 수정하지 않고 테스트케이스를 추가해보며 계산하다가 한참 후 0이 아닌 1을 리턴해야 한다는 사실을 알게되었다.
억울함의 의사코드 재작성을 하던 중 문제점을 발견한 것인데
역시 문제가 해결되지 않을 때는 처음으로 돌아가 다시 의사코드를 작성하는 것도 방법인 것 같다.

function solution(begin, end) { //시작, 끝 idx
    var answer = [];
    for(let i = begin ; i <= end ; i++){ 
        if(i === 1 ){ //1번은 0으로 시작
            answer.push(0)
        }
        else if(i < 10000000 && isPrime(i)){ //천만번 이하 중 소수는 1
            answer.push(1)
        }
        else {
            answer.push(calculate(i)) //소수가 아닌 경우 최대약수 찾기
        }
    }
    return answer; 
}

function calculate(num){
    for(let i = 2 ; i <= Math.sqrt(num) ; i++){ //약수 찾아나가기 
    //천만 이하 소수와 소수의 곱으로 최대 3137까지밖에 계산하지 않는다.
        if(num % i === 0 && num/i <= 10000000){
            return num/i //천만 이하로 나눠진 순간 배출
        }
    }
    return 1 //위에서 리턴처리가 되지 않으면 1을 내보낸다
}

function isPrime(num) {
  let result = 0;

  for(n = 1; n < num; n++){
    if(num % n === 0){
      result = result + n
    }
  }
  
  return result === 1 && num !== 1
}