[코딩테스트 javascript] 조이스틱 - Greedy ,그리디, 탐욕,DFS,깊이 탐색 알고리즘, 그래프 탐색 알고리즘

조이스틱

 

프로그래머스

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

 

풀이 1 - 59.3점

1. 알파벳을 키로, index 값을 value로 하는 map을 생성한다.

- 참고로 A~Z 까지의 알파벳 배열을 생성하기 위해서 String.fromCharCode(i+65)를 사용할 수 있다.

- "A"의 아스키코드값이 65이다.

const arr = Array.from({ length: 26 }, (v, i) => String.fromCharCode(i + 65));
console.log(arr)
/*
[
  'A', 'B', 'C', 'D', 'E', 'F',
  'G', 'H', 'I', 'J', 'K', 'L',
  'M', 'N', 'O', 'P', 'Q', 'R',
  'S', 'T', 'U', 'V', 'W', 'X',
  'Y', 'Z'
]
*/

2. 재귀함수 (str,index,합,뱡향)을 생성해준다.

- str을 name으로 변하기 위해 필요한 횟수는 map.get으로 얻는다.

- 방향을 처음에 정방향, 역방향 모두 재귀를 돌려 한쪽 방향으로만 돈다.

3. str이 name과 일치했을 때 answer에 push하여 최솟값을 출력한다.

 

function solution(name) {
    const map = new Map();
    for(let i=0;i<26;i++) {
        map.set(String.fromCharCode(i+65),i)
    }
    // console.log(map)
/*
  'A', 'B', 'C', 'D', 'E', 'F',  'G', 'H', 'I', 'J', 'K', 'L','M',     
  'N', 'O', 'P', 'Q', 'R',  'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'
*/
    let count = [];
    const originstr = "A".repeat(name.length).split('')
    const A = [];
    name.split('').forEach((v,i)=>{
        if(v==="A") A.push(i)
    })
    console.log(A)
    DFS(originstr,0,0,null);
    
    return count.sort((a,b)=>a-b)[0];
    
    function DFS(str,i,sum,dir) {
        // 1. 종료조건
        if (str.join('') == name) {
            count.push(sum); return 0;
        }
        // 2. 수행동작
        else {
            let newstr = str.slice();
            newstr[i] = name[i];
            // console.log(newstr[i])
            // console.log(newstr.join(''))
            
            const addi = i+1===name.length?   0:i+1
            const subi = i-1===-1?name.length-1:i-1
        
            const strC = map.get(str[i])
            const nameC= map.get(name[i])
            const min = Math.min((nameC - strC),(26-nameC) )
            
            let newsum =sum + min
            if (newstr.join('') == name) {
                count.push(newsum); return 0;
            }
            else {
                newsum+=1
                if (dir===null) {
                       DFS(newstr,addi,newsum,"right")
                       DFS(newstr,subi,newsum,"left")
                   }
                if (dir==="right") {
                       DFS(newstr,addi,newsum,"right")
                   }
                if (dir==="left") {
                       DFS(newstr,subi,newsum,"left")
                }
            } 
        }
    }
}

틀린 이유 

 

- 방향이 항상 일직선이 아닐 수도 있다.

 반례는 "PSAAAAP"와 같다. 

 정방향 1회 후, 역방향을 2번 해야 한다.

 

 

풀이 2 - 44점

1. 알파벳을 키로, index 값을 value로 하는 map을 생성한다.

2. 재귀함수 (str,index,합,뱡향)을 생성해준다.

- str을 name으로 변하기 위해 필요한 횟수는 map.get으로 얻는다.

- A의 개수가 한개일 때만 방향 설정이 가능한 코드이다.

 

function solution(name) {
    const map = new Map();
    for(let i=0;i<26;i++) {
        map.set(String.fromCharCode(i+65),i)
    }
    // console.log(map)
/*
  'A', 'B', 'C', 'D', 'E', 'F',  'G', 'H', 'I', 'J', 'K', 'L','M',     
  'N', 'O', 'P', 'Q', 'R',  'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'
*/
    let count = [];
    const originstr = "A".repeat(name.length).split('')
    const A = [];
    name.split('').forEach((v,i)=>{
        if(v==="A") A.push(i)
    })
    console.log(A)
    DFS(originstr,0,0,null);
    
    return count.sort((a,b)=>a-b)[0];
    
    function DFS(str,i,sum,dir) {
        // 1. 종료조건
        if (str.join('') == name) {
            count.push(sum); return 0;
        }
        // 2. 수행동작
        else {
            let newstr = str.slice();
            newstr[i] = name[i];
            // console.log(newstr[i])
            // console.log(newstr.join(''))
            
            const addi = i+1===name.length?   0:i+1
            const subi = i-1===-1?name.length-1:i-1
        
            const strC = map.get(str[i])
            const nameC= map.get(name[i])
            const min = Math.min((nameC - strC),(26-nameC) )
            
            let newsum =sum + min
            if (newstr.join('') == name) {
                count.push(newsum); return 0;
            }
            else {
                newsum+=1
                if (A.length===1) {
                   if (A.includes(addi)) {
                       DFS(newstr,subi,newsum,"left")
                   }
                   if (A.includes(subi)) {
                       DFS(newstr,addi,newsum,"right")
                   }
                   else {
                       if(dir==="right") {
                           DFS(newstr,addi,newsum,"right")
                       } 
                       else  DFS(newstr,subi,newsum,"left")
                   }
                    
                }
                else{
                    DFS(newstr,addi,newsum,"right")
                }
                
                // if (dir==="right") {
                //     DFS(newstr,addi,newsum,"right")
                //     } 
                // if (dir ==="left"){
                //     DFS(newstr,subi,newsum,"left")
                //     }
            }
           
           
            
            
        }
    }
}

 

 

풀이 3 - 다른 사람의 풀이 best

1. 각각의 string에서 name으로 바꾸기 위한 경우를 sum에 더해준다.

- 알고리즘 천재인가....? "A".repeat(name.length)를 하지 않다니....

- name의 스트링을 for문 돌면서 아스키코드 - A의 아스키코드를 돈다. 

- 단, A를 Z로 바꾸고 name으로 바꾸는 것이 빠른 경우를 생각해야 한다. (26-nameC)

- 즉, 알파벳 개수 26/2 보다 N[i] - 65인 경우는 뒤에서 제거 한다. 

for (let i = 0; i < name.length; i++) {
        let diff = name[i].charCodeAt() - 'A'.charCodeAt();
        sum += diff > 13 ? 26 - diff : diff;
    }

String.prototype.charCodeAt()
 
메서드는 주어진 인덱스에 대한 UTF-16 코드를 나타내는 0부터 65535 사이의 정수를 반환합니다.

 

 

 

2. 방향의 횟수를 sum에 더해준다.

- 최대의 방향 횟수는 string의 length -1이다.

let min = name.length-1

- A가 존재할 시, A가 연속 몇개 인지 센다.

 : var 변수를 이용해 함수 스코프를 벗어나는 구역에서도 변수를 사용한다.

for (let i = 1; i < name.length; i++) {
        if (name[i] === 'A') {
            for (var j = i + 1; j < name.length; j++) {
                if (name[j] !== 'A') {
                    break;
                }
            }

            const left = i - 1;
            const right = name.length - j;
            minMove = Math.min(minMove, left > right ? left + right * 2 : left * 2 + right);

            i = j;
        }
    }

 

 

3. sum+minMove를 리턴한다.

function solution(name) {
    let sum = 0;
    for (let i=0;i<name.length;i++){
        let min = name[i].charCodeAt()-"A".charCodeAt()
        min= min>13? 26-min:min
        sum +=min
    }
    console.log(sum)
    
    let mindir = name.length-1
    for (let i=1;i<name.length;i++){
        let j= 0
        if (name[i]==="A") {
            for (j=i+1;j<name.length;j++){
                if (name[j]!=="A") break;
            }
            const left = i -1;
            const right  = name.length-j;
            const count = left>right? left +right*2 : left*2 + right
            mindir = Math.min(mindir,count)

            i=j
        }
       
    }
    return sum+mindir;
}