Algorithm - Programmers & LeetCode Problems 4

Programmers Problem : 짝지어 제거하기

• 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다.
  • 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다.
  • 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다.
  • 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다.
• 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요.
  • 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.
• 예를 들어, 문자열 S = baabaa 라면
  • b aa baa → bb aa → aa → 의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

제한사항

• 문자열의 길이 : 1,000,000이하의 자연수
• 문자열은 모두 소문자로 이루어져 있습니다.

Solution

function solution(s){
    if (s.length % 2 !== 0) {
        return 0;
    }
    
    let strArr = s.split('');
    const stack = [];
    
    for (let i = 0; i < strArr.length; i++) {
        if (strArr[i] === stack[stack.length -1]) {
            stack.pop();
            continue;
        }
        stack.push(strArr[i]);

        if (stack.length > strArr.length - i) {
            return 0;
        }
    }

    return 1;
}

Programmers Problem : [1차] 캐시

• 지도개발팀에서 근무하는 제이지는 지도에서 도시 이름을 검색하면 해당 도시와 관련된 맛집 게시물들을 데이터베이스에서 읽어 보여주는 서비스를 개발하고 있다.

• 이 프로그램의 테스팅 업무를 담당하고 있는 어피치는 서비스를 오픈하기 전 각 로직에 대한 성능 측정을 수행하였는데, 제이지가 작성한 부분 중 데이터베이스에서 게시물을 가져오는 부분의 실행시간이 너무 오래 걸린다는 것을 알게 되었다.

• 어피치는 제이지에게 해당 로직을 개선하라고 닦달하기 시작하였고, 제이지는 DB 캐시를 적용하여 성능 개선을 시도하고 있지만 캐시 크기를 얼마로 해야 효율적인지 몰라 난감한 상황이다.

• 어피치에게 시달리는 제이지를 도와, DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오.

입력 형식

• 캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다.
• cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30 이다.
• cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.
• 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.

출력 형식

• 입력된 도시이름 배열을 순서대로 처리할 때, "총 실행시간"을 출력한다.

조건

• 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
• cache hit일 경우 실행시간은 1이다.
• cache miss일 경우 실행시간은 5이다.

Solution

• LSU 알고리즘 설명 (참고)
• 테스트케이스 11,15,16,18,19,20을 틀려서 다른 사람 쓴 힌트를 참고함 (참고)

function solution(cacheSize, cities) {
    const cache = [];
    const answer = cities.map((city) => city.toUpperCase()).reduce((runtime, city) => {
        if (cache.includes(city)) {
            cache.splice(cache.indexOf(city), 1);
            cache.push(city);
            runtime += 1;
        } else {
            runtime += 5;
            cache.push(city);
        }
        if (cache.length > cacheSize) {
            cache.shift();
        }
        return runtime;
    }, 0);
    return answer;
}

LeetCode Problem : Number of Senior Citizens

• You are given a 0-indexed array of strings details. Each element of details provides information about a given passenger compressed into a string of length 15. The system is such that:

  • The first ten characters consist of the phone number of passengers.
  • The next character denotes the gender of the person.
  • The following two characters are used to indicate the age of the person.
  • The last two characters determine the seat allotted to that person.

• Return the number of passengers who are strictly more than 60 years old.

Constraints

• 1 <= details.length <= 100
• details[i].length == 15
• details[i] consists of digits from '0' to '9'.
• details[i][10] is either 'M' or 'F' or 'O'.
• The phone numbers and seat numbers of the passengers are distinct.

Solution

/**
 * @param {string[]} details
 * @return {number}
 */
var countSeniors = function(details) {
    return details.map((str) => Number(str.substring(11, 13))).filter((age) => age > 60).length;
};

Programmers Problem : 예상 대진표

• △△ 게임대회가 개최되었습니다.

  • 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다.
  • N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다.
  • 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N번의 참가자끼리 게임을 진행합니다.
  • 각 게임에서 이긴 사람은 다음 라운드에 진출할 수 있습니다.
    • 이때, 다음 라운드에 진출할 참가자의 번호는 다시 1번부터 N/2번을 차례대로 배정받습니다.
    • 만약 1번↔2번 끼리 겨루는 게임에서 2번이 승리했다면 다음 라운드에서 1번을 부여받고, 3번↔4번에서 겨루는 게임에서 3번이 승리했다면 다음 라운드에서 2번을 부여받게 됩니다.
  • 게임은 최종 한 명이 남을 때까지 진행됩니다.

• 이때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 궁금해졌습니다.

• 게임 참가자 수 N, 참가자 번호 A, 경쟁자 번호 B가 함수 solution의 매개변수로 주어질 때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 return 하는 solution 함수를 완성해 주세요.

  • 단, A번 참가자와 B번 참가자는 서로 붙게 되기 전까지 항상 이긴다고 가정합니다.

제한사항

• N : 2^1 이상 2^20 이하인 자연수 (2의 지수 승으로 주어지므로 부전승은 발생하지 않습니다.)
• A, B : N 이하인 자연수 (단, A ≠ B 입니다.)

입출력 예

• Input: N = 8, A = 4, B = 7
• Output: 3
• Explanation:
  • 첫 번째 라운드에서 4번 참가자는 3번 참가자와 붙게 되고, 7번 참가자는 8번 참가자와 붙게 됩니다.
    • 항상 이긴다고 가정했으므로 4번 참가자는 다음 라운드에서 2번이 되고, 7번 참가자는 4번이 됩니다.
  • 두 번째 라운드에서 2번은 1번과 붙게 되고, 4번은 3번과 붙게 됩니다.
    • 항상 이긴다고 가정했으므로 2번은 다음 라운드에서 1번이 되고, 4번은 2번이 됩니다.
  • 세 번째 라운드에서 1번과 2번으로 두 참가자가 붙게 되므로 3을 return 하면 됩니다.

Soluton

function solution(n,a,b)
{
    let answer = 0;
    while (a !== b) {
        a = Math.round(a/2);
        b = Math.round(b/2);
        answer++;
    }

    return answer;
}

Programmers Problem : 프로세스

• 운영체제의 역할 중 하나는 컴퓨터 시스템의 자원을 효율적으로 관리하는 것입니다. 이 문제에서는 운영체제가 다음 규칙에 따라 프로세스를 관리할 경우 특정 프로세스가 몇 번째로 실행되는지 알아내면 됩니다.

1. 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다.
2. 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다.
3. 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다.
   3.1 한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료됩니다.

• 예를 들어 프로세스 4개 [A, B, C, D]가 순서대로 실행 대기 큐에 들어있고, 우선순위가 [2, 1, 3, 2]라면 [C, D, A, B] 순으로 실행하게 됩니다.

• 현재 실행 대기 큐(Queue)에 있는 프로세스의 중요도가 순서대로 담긴 배열 priorities와, 몇 번째로 실행되는지 알고싶은 프로세스의 위치를 알려주는 location이 매개변수로 주어질 때, 해당 프로세스가 몇 번째로 실행되는지 return 하도록 solution 함수를 작성해주세요.

제한사항

• priorities의 길이는 1 이상 100 이하입니다.
• priorities의 원소는 1 이상 9 이하의 정수입니다.
• priorities의 원소는 우선순위를 나타내며 숫자가 클 수록 우선순위가 높습니다.
• location은 0 이상 (대기 큐에 있는 프로세스 수 - 1) 이하의 값을 가집니다.
• priorities의 가장 앞에 있으면 0, 두 번째에 있으면 1 … 과 같이 표현합니다.

입출력 예

• 입력 : priorities = [1,1,9,1,1], location = 0
• 출력 : 5
• 설명 : 6개의 프로세스 [A, B, C, D, E, F]가 대기 큐에 있고 중요도가 [1, 1, 9, 1, 1, 1] 이므로 [C, D, E, F, A, B] 순으로 실행됩니다. 따라서 A는 5번째로 실행됩니다.

Solution

function solution(priorities, location) {
    let answer = 0;
    let sortedQueue = [];
    const queue = priorities.map((priority, index) => { 
        return {priority, index}; 
    });
    
   sortQueueByPriority(queue, sortedQueue);
    
    for (let i = 0; i < sortedQueue.length; i++) {
        if (sortedQueue[i].index === location) {
            answer = i + 1;
            break;
        }
    }
    return answer;
}

function sortQueueByPriority(queue, sortedQueue) {
    if (queue.length === 0) {
        return sortedQueue;
    }
    const currProcess = queue.shift();
    const higherPriorityCount = queue.filter(process => process.priority > currProcess.priority).length;
    if (higherPriorityCount > 0) {
        queue.push(currProcess);
    } else {
        sortedQueue.push(currProcess);
    }
    return sortQueueByPriority(queue, sortedQueue);
}