[13주차] 5/20 ~ 5/26

모각독 13주차 5/20 ~ 5/26

 

큐

선입 선출
먼저 줄 선 사람이 먼저 나감(First In First Out = FIFO)
삽입은 Enquere(Add)
꺼내는건 Dequeue(Poll)

 

 

 

---

요세푸스 문제

N명의 사람이 원 형태로 서있음
각 사람은 1부터 N까지 번호표를 가짐
임의의 숫자 K가 주어졌을 때, K번째 사람을 제거

 

1) 기준: 1번 -> 인덱스 [0] -> 얘를 기준으로 K번째 사람을 없앰(인덱스니까 K-1)

2) 다음 기준: 없앤 사람의 다음 사람(인덱스는 동일하게 K-1)

3) 마지막 살아있는 사람의 번호 반환(1명 남을때까지 반복)

 

=> 원형 연결 리스트인가? JS에 원형 연결리스트가 없는데 어떻게 해결할 수 있을까

 

 

 

var n = 5;

var people = [];

var k = 2;

for(let i = 0; i < n; i++){

  people.push(i + 1);

}

console.log('시작:', people);

while(people.length >= 1){

  //1. 기준 1번[0]부터 k번인 사람 제거

  people.splice(k - 1, 1);   //걍 기준이 첫번째면 두번째 사람 없애란겨...즉 바로 다음사람 ^_^

  console.log('제거된 후:', people);

 

  //2. k-1 여기서부터 다시 시작할거니까 이거 앞에값은 뒤로 보내야함

  let first = people.shift();

  people.push(first);

  console.log('순서 정렬: ',people);

 

  if(people.length === 1){

    break;

  }

}

 

문제풀이용으로 답 한개에 딱 맞춘거라

범용성이 떨어지기에 좋은 코드는 아니다.

 

일단 k번째 사람을 제거한 뒤, 그 다음 사람이 새로운 기준이 되었고

원형으로 서있다는 설정이므로 새 기준 앞의 값들을 전부 뒤로 보내줘야 한다.

 

이걸 1명이 나올때까지 반복한다.

 

 

결과값은 이렇게 나온다.

 

 

 

 

카드뭉치

프로그래머스

영어단어 카드뭉치 2개, A뭉치, B뭉치
한장씩 사용
한번 사용한건 다시 X (배열에서 제거)
카드 사용하지 않고 다음 카드로 넘어갈 수 X
기존에 주어진 카드뭉치 순서 바꿀 수 X (순서 중요)

 

스택이 2개라고 생각하고 품

1) goal에서 하나씩 꺼내서 지우기
2) 순서대로 한개씩 꺼내서 판별(어차피 각 뭉치당 [0]번째 값으로 판별할 것)

 

var cards1 = ["i", "drink", "water"];

var cards2 = ["want", "to"];

var goal = ["i", "want", "to", "drink", "water"];

var answer = 'Yes';

//테스트 케이스 3개 통과못함 -> 값 0일때 체크해줬더니 통과

for(let i = 0; i < goal.length; i++){

  let target = goal[i];

 

  // if(cards1[0] === target){

  if(cards1.length > 0 && cards1[0] === target){ //값 0아닌지 체크

    cards1.shift(); //첫번째 값 삭제

    console.log('cards1:',cards1);

  }else if(cards2.length > 0 && cards2[0] === target){

    cards2.shift(); //첫번째 값 삭제

    console.log('cards2:',cards2);

  }else{

    answer = 'No';

  }

}

console.log(answer);

 

 

3) goal에서 꺼낸 값과 카드뭉치의 0번째 값이 같으면 삭제(맞는값이 없으면 No 반환)

4) 값이 0일때를 체크 안해줬더니 테스트 케이스 3개를 통과 못하길래 추가해줌

 

 

결과값은 이렇다.

 

 

 

 

기능개발

프로그래머스

이 문제를 보는데 갑자기 운영체제 스케줄링이 생각났다...ㅎ

각 기능 개발 속도는 모두 다름
뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 O
But, 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됨
배포는 하루에 한번만 가능

progresses: 작업 진도 적힌 정수 배열
speeds: 작업 개발 속도 정수 배열

각 배포마다 몇개의 기능이 배포되는지 return

 

1) 100 - progresses[0] = n  -> 무조건 길이 같음

2) n % speeds[0] = 0   -> 일수 구하기(Days배열 하나 만들어야 함)

    0이면 몫, 0이 아니면 몫 +1   

3) Days배열에 각 기능당 얼마나 걸리는지 구해서 넣기(일수)

 

 

var progresses = [93, 30, 55];

var speeds = [1, 30, 5];

var days = [];

var dayCnt = 0;

var answer = [];

var start = 0;

//1. 100 - progresses[0] = n

for(let i = 0; i < progresses.length; i++){

  let n = 100 - progresses[i];

  console.log('n은:' , n);

 

  //2.n % needs[0] === 0 -> 몫이 0 or not

  n % speeds[i] === 0 ? days.push(Math.floor(n/speeds[i])) : days.push(Math.floor((n/speeds[i]) + 1));

  /*=> 이 코드는 이렇게 변경 가능 

  let daysToComplete = Math.ceil(n / speeds[i]); // 올림 처리

  days.push(daysToComplete);

  */

 

  console.log('days: ', days);

}

//3. 배포그룹 처리  --> 기준 days[0]

start = days[0];

dayCnt = 1;

for(let i = 1; i < days.length; i++){

  if(start < days[i]){

    answer.push(dayCnt);

    dayCnt = 1; //초기화

    start = days[i];

  }else{

    dayCnt++;

  }

}

answer.push(dayCnt); //마지막 배포그룹 처리

console.log(answer);

 

1+2) 일수를 구하면 [7, 3, 9]가 된다 = 7일, 3일, 9일

3-1) 일단 기능 기본(dayCnt)을 1로 두고, 

    첫번째 기능부터 시작하니까, 다음 기능이 첫번째 기능보다 빨리 완성되면

    대기했다가 첫번째 기능이랑 묶어서 같이 배포 되어야 하므로 dayCnt에 기능갯수 1 추가

 

3-2) 위의 상황에서, 다음 기능(세번째)이 첫번째 기능보다 완성되는 시간이 더 오래걸리면 

       어차피 첫번째 기능과 같이 배포가 불가능하므로, 다음 배포로 미루고

       첫번째 기능과 묶여진 뭉텅이 기능을 먼저 배포한다. 

       그러므로 첫번째 배포되는 기능은 2개, 그다음 배포되는 기능은 1개

       결과값은 [2, 1]이 나온다.

 

 

결과값은 이렇다.