외벽점검

✅ 다시풀어야할 문제

• 반시계 방향은 고려하지 않아도 된다는 점.

다음과 같다고 할 때, 3인 친구가 점검한다고 가정하자.

3인친구는 시계 방향일 때 10에서 1까지 점검할 수 있고, 반시계방향으로 점검할 때 1에서 10까지 점검할 수 있다.

즉 원이 아닌 선형으로 만들게 되면 결국 반시계로 하는 행위는 반시계로 점검하여 도달하는 마지막 점에서 시계방향으로 점검하는 것과 같은 것이다.

다음과 같은 선형 자료구조를 보자. 3인 친구를 1에 두고 반시계 방향으로 조사시키는 것은 ㅌ3인 친구를 10에 두고 시계방향으로 조사시키는 것이므로 굳이 반시계방향은 고려하지 않아도된다.

• 조합이 아닌 순열로 풀어야한다는점.

조합으로 친구 두명을 뽑는다고 가정하더라도, 첫번째 친구를 기준으로 두번째 친구위치를 둘때와 두번째 친구를 기준으로 첫번째 위치를 둘때가 다르기 때문에 순열로 계산을 해주어야한다.

그렇기 때문에 순열로 푼다.

조합인 경우 1번 2번 3번의 친구들을 뽑았다고 가정한다면 1번의 위치에서 커버리지 할 수 있는 것을 뺀 이후부터 모든 weak 원소를 2번이 시작한다고 가정하고, 또 2번이 위치를 골라 커버리지 할 수 있는 것을 뺀 이후 부터 3번이 시작한다고 생각해야하기 때문에, 순열의 과정을 또 하게 되는 것이다.

([1,5,6,10] 일 때, 1번친구가 1만 체크했다고 가정하자. 그럼 2번 친구는 5번에서 시작할 때 6에서 시작할 때 10에서 시작할 때를 계산해야하고, 마찬가지로 3번은 2번친구가 점검하지않은 것을 또 점검해야하기에 어차피 순열이 된다.)

완성코드

function getPermutation(dist){
    const result = []
    function DFS(current,visited,r){
        if( r === current.length ){
            result.push(current);
        }
        for(let i=0;i<dist.length;i++){
            if(!visited.includes(i))
            DFS([...current,dist[i]],[...visited,i],r)
        }   
        
        
    }
    for(let i=1;i<=dist.length;i++){
        DFS([],[],i);
    }
    return result;
}
function solution(n, weak, dist) {
  // [[1],[2],[3],[4],[1,2],[2,1] .... ] 모든 순열을 구한다.
    const permutationByFriends = getPermutation(dist);
  
  // 원형 -> 선형으로 바꾼다. 하나 하나를 시작점으로 두고 n보다 작은 것들은 n을 더해서 저장한다.
  // [1,5,6,10,13,17,18] 이 된다. 10인 경우를 생각하여 22를 넣을 필요는 없다. 그건 1~10을 점검하는것과 같으니깐
    let linearWeak = [...weak];
    for(let i=0;i<weak.length-1;i++){
        if(weak[i] < n) linearWeak.push(weak[i]+n)
    }
    for(let p of permutationByFriends)
      // 조합을 돌면서 친구들을 순차적으로 위치시켜 얼마나 점검할 수 있는지 체크한다.
        for(let i=0;i<weak.length;i++){
          // 조합의 첫번째 친구를 기준으로 배치시켜 배열을 얻어낸다. 6에 배치시키면 6 10 13 17 이 line이 된다.
            let line = linearWeak.slice(i,i+weak.length);
            p.forEach(friend =>{
 				// 순열의 친구들을 순회하며 점검할 수 있는 것들은 지워준다.             
                line = line.filter((d)=>d > line[0] + friend)
                                   
            })
            // 모두 지워지게 되면 해당 순열로 모든 weak을 점검한 것이므로 빠져나온다.
            if(line.length === 0) return p.length;
        }
    return -1;
}

정규표현식

{{133,2,3},{2,1},{1,2,4,3},{2}}을 배열로 만들어보세요

answer :

1. JSON.parse(string.replace(/{/gi,'[').replace(/}/gi,']'))

string.replace(/[{}]/gi, (i) => {
    if (i === "{") {
      return "[";
    }
    if (i === "}") {
      return "]";
    }
    return "";
  })

로 해도 된다. replace 함수에 replacer 함수를 넣어 대체 할 수 도있다.
2.
string.split('},{').map(i=>i.replace(/[}{]/gi,''))

3. string.match(/(\d+)(,\d+)*/gi)

4. string.match(/(\d+,)*\d+/gi)

5. 1️⃣ {(\d+,)*\d} vs 2️⃣ {(\d+,)*\d+}

1️⃣ {(\d+,)*\d} 로 하게되면
{{133,2,3},{2,1},{1,2,4,3},{2}} 를 만드는데 문제는 없으나 맨 마지막 부분이 \d+ 가 아니기때문에 {{133,2,3},{2,1},{1,2,4,3},{23}} 은 제대로 되지않는다.

2️⃣ {(\d+,)*\d+}로 해야 정상적으로 동작한다.

f-5 freedom 18fighter를 다음 조건에 맞게 파싱하세요

조건 : 처음 나오는 숫자는 파일의 번호이다. 파일의 번호 앞에 나오는 문자열이 파일명이며, 뒤에 나오는 문자열은 Tail이다

1. 처음 나오는 숫자를 기준으로 split 한다.

string.split(/(\d+)/) : 처음 나오는 숫자를 기준으로 스플릿하고, 스플릿한 본인도 남는다.

string.split(/\d+/) : 의미는 같지만 본인이 남지않는다.

2. match를 이용한다

string.match(/(\D+)(\d+)/) -> 글로벌 태그가 붙지 않았기 때문에 가장 처음 만 나오게된다(원하는 조건에 부합)

string1.match(/(\D+)(\d+)/g) -> 글로벌 태그가 붙었으므로 해당되는 것이 모두 배열에 들어가게된다.

만약 다음과 같이 그룹화를 하지 않게 되면 숫자부분은 match 배열에 그룹으로 등장하지 않는다. 둘다 그루핑해서 정보를 알 수 있으려면 위의 방식대로 해야한다.

그리디

그리디 알고리즘을 한마디로 설명한다면 그 유명한 마시멜로 실험에 비유할 수 있겠다. 그리디 알고리즘을 사용한다는 것은 지금 당장 눈 앞에 있는 마시멜로를 먹는 것이다. 하지만 이 방법을 사용하는 것은 "기다렸다가 2개를 먹는다"라는 최적해를 보장해주지 못한다.

매 선택에서 지금 이 순간 당장 최적인 답을 선택하는 알고리즘이다. 전체 문제의 최적 해결방법을 부분 문제에 대한 최적 해결 방법으로 만들어 내는것

function solution(n, lost, reserve) {
    lost.forEach((l)=>{
        if(reserve.includes(l)){
            lost = lost.filter(i=> l !== i)
            reserve = reserve.filter(i => l !== i);
        }
    })
    var answer = n - lost.length;
    // 여분의 학생이 잃어 버린사람에게 빌려주게 되면 최적의 선택이 되는 것이다.
    
    reserve.forEach(r=>{
        
        if(lost.includes(r-1)){
            answer++;
            lost = lost.filter(i=>i !== r-1);
            return ;
        }
        if(lost.includes(r+1)){
            answer++;
            lost = lost.filter(i=>i !== r+1);
            return ;
        }
    })
    return answer;
}

TIP

• match 함수를 사용할 때 안에 들어가는 정규표현식을 글로벌 태그로 작성하게 되면, 그룹화된 상세 정보는 알수없게된다.

정규표현식이랑 매치되는 것들의 배열이 되어버림

• match 함수는 인자로 오는 정규표현식과 일치하는 substring을 골라주는 것이라 이해하면 편한다

• replace함수의 두번째 인자로 replacer 함수를 줄 수 있다. 정규표현식으로 대체 해야할 문자가 두 개 이상이면 replacer함수를 이용하자

• split시 그룹화를 해주면, 스플릿의 기준 문자열도 포함되게 된다.