알고리즘 스터디 6일차 - 문제 풀이(Javascript)

아래 2개의 문제에 대해 문제 풀이를 작성하였습니다.

프로그래머스 - 월간 코드 챌린지 시즌3 - 나머지가 1이 되는 수 찾기
프로그래머스 - 탐욕법(Greedy) - 체육복

---

1. 나머지가 1이 되는 수 찾기 (q46)

---

문제 설명

자연수 n이 매개변수로 주어집니다. n을 x로 나눈 나머지가 1이 되도록 하는 가장 작은 자연수 x를 return 하도록 solution 함수를 완성해주세요. 답이 항상 존재함은 증명될 수 있습니다.

제한 조건

3 ≤ n ≤ 1,000,000

예시

입/출력

• 입력 n=10 , 출력 result=3
• 입력 n=12, 출력 result=11

입출력 예 #1
10을 3으로 나눈 나머지가 1이고, 3보다 작은 자연수 중에서 문제의 조건을 만족하는 수가 없으므로, 3을 return 해야 합니다.

입출력 예 #2
12를 11로 나눈 나머지가 1이고, 11보다 작은 자연수 중에서 문제의 조건을 만족하는 수가 없으므로, 11을 return 해야 합니다.

---

나의 풀이

function solution(n) {
    var answer = 0;
    let x = 0;
    // 0으로 나누었을때는 mod 연산자 값이 0, 
    // 1로 나누면 자기 자신이 되는 케이스를 제외하고 2부터 시작
    for (let i = 2; i < n; i++){ 
        if (n%i === 1){
            x = i;
            return x;
        }
    }
    answer = x;
    return answer;
}

주어진 조건대로 작성하면 되는 문제라 크게 어렵지 않았다. 다만, n은 3이상의 수로 지정되었으므로 for문을 돌기 위한 i값 설정 시 2부터 시작하도록 설정하였다.

2. 체육복 (q49)

---

문제 설명

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

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

제한 조건

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

예시

n=5, lost = [2, 4], reserve = [1, 3, 5], return = 5
n=5, lost = [2, 4], reserve = [3], return = 4
n=3, lost = [3], reserve = [1], return = 2

---

나의 풀이

function solution(n, lost, reserve) {
    var answer = n;
    let lostnum = 0; // 체육복을 도난당한 학생 번호를 저장할 변수 lostnum
    let reserve_flag = 0; // 도난당한 학생에게 빌려줄 체육복이 있는 경우를 셀 수 있는 flag. 1은 있음, 0은 없음
    lost.sort((a,b) =>a-b);
    reserve.sort((a,b) => a-b);
    
    // 이중 for문을 돌며, lost 배열과 reserve 배열 내 동일한 값이 있는지 체크. 
    // 여벌 체육복을 가져온 학생이 체육복을 도난당한 케이스 미리 제거
    for (let i = 0; i <lost.length; i++){
        for (let j = 0; j < reserve.length; j++){
            if (lost[i] === reserve[j]){
                reserve.splice(j,1);
                lost.splice(i,1);
                j--;
                i--;
            }
        }
    }
    
    for (let i = 0; i < lost.length; i++){
        reserve_flag = 0;
        lostnum = lost[i];
        for (let j = 0; j < reserve.length; j++){
            if (lostnum === reserve[j]){
                reserve_flag = 1;
                reserve.splice(j, 1);
                break;
            } else if (lostnum === reserve[j+1]){
                reserve_flag = 1;
                reserve.splice(j+1, 1);
                break;
            }
            if((lostnum === reserve[j] - 1) || (lostnum === reserve[j] + 1)){
                reserve_flag = 1;
                reserve.splice(j, 1); // 여분 체육복을 빌려준 효과를 내도록 현재 reserve[j] 에 있는값을 제거
                break; // 현재 for문을 탈출
            }
        }
        if (reserve_flag === 0){
            answer--;
        }
    
    }
    return answer;
}

n의 값이 그리 크지않아 이중 for문을 돌아도 부담은 없지만 그걸 두 번이나 돌리는건 좀 양심에 가책이 있다..
채점 시 배열이 정렬되지 않은 케이스가 있어, Array.sort() 를 사용하여 오름차순 배열을 먼저 진행했다.
우선 여벌 체육복을 가져온 학생이 체육복을 도난 당한 케이스 => 해당 값이 lost, reserve 배열에 모두 있는 케이스를 찾아 두 배열에서 모두 빼버린다.
이후, lost[i] 값을 대상으로 reserve[j], reserve[j+1] 값을 비교하며 빌릴 체육복이 있는지를 탐색한다. 다 검색해봤는데도 빌릴 수 없을 경우 reserve_flag 값이 변하지 않게 설정하여, answer 값을 하나 줄여 학생 수를 줄이고 그 값을 리턴한다.

참고 URL

1. 나머지가 1이 되는 수 찾기

   MDN - Array.prototype.push()

2. 체육복