Algorithm -Greedy(Gas Station, Largest Number, Remove Duplicate Letters)

다용도리모콘·2021년 7월 31일

CodingTest

목록 보기

31/34

Gas Station

문제

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.
Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique

코드

function canCompleteCircuit
(gas: number[], cost: number[]): number {

let gasStation = -1;
for(let index = 0; index < gas.length; index++) {
    let gasOfStatioin = gas[index];
    if (gasOfStatioin >= cost[index]) {
        let currentGas = gasOfStatioin;
        let canTravel = true;
        let currentIndex = index;
        let nextIndex = index + 1;
        for(let i = 1; i <= gas.length; i++) {
            if (nextIndex == gas.length) {
                nextIndex = 
                  nextIndex - gas.length;
            }
            currentGas = 
              currentGas - cost[currentIndex];
            
            if (currentGas < 0) {
                canTravel = false;
                break;
            }

            currentGas = 
              currentGas + gas[nextIndex];

            currentIndex = nextIndex;
            nextIndex = nextIndex + 1;
        }
        if (canTravel) {
            gasStation = index;
            break;
        }
    }
}
return gasStation;
};

function canCompleteCircuit
(gas: number[], cost: number[]): number {
    let n = gas.length;
    let total_surplus = 0 , surplus = 0, S = 0;
    
    for(let i = 0;i<gas.length;i++){
        total_surplus += gas[i]-cost[i];
        surplus += gas[i]-cost[i];
        if(surplus<0){
            surplus = 0;
            S= i+1;
        }
    }
    return total_surplus < 0 ? -1 :S;
    
};

회고

이중 반복문을 쓰지 않고 풀어보려고 하다가 결국은 1.5개? 느낌으로 써버렸는데 제출하고 나서 보니 안쓰고도 해결할 수 있는 방법이 있었다. 전체 필요 가스보다 전체 스테이션 가스 총량이 크다면 무조건 순환이 성립된다는 것과 루프를 진행하다가 마이너스가 되면 그 이전의 경로는 모두 실패라고 판단할 수 있다는 사실을 알아채야 하는데 전혀 눈치채지 못했다;;;

Largest Number

문제

Given a list of non-negative integers nums, arrange them such that they form the largest number.
Note: The result may be very large, so you need to return a string instead of an integer.

코드

function largestNumber(nums: number[]): string {
let answer = [];
nums.forEach((value) => {
    answer.push(value.toString())
});

answer.sort((a, b) => {
    return (b+a) - (a+b);
});

if (answer[0] == "0") return "0"

return answer.reduce((pre, cur) => pre + cur);

};

회고

어떻게 정렬해야하는지만 알면 그냥 sort 함수를 커스터마이징 하는 것으로 간단하게 풀 수 있는 문제. 문자열 사이의 크기 비교 기준을 모른다면 좀 헤멜수도 있을 것 같다.

Remove Duplicate Letters

문제

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

코드

function removeDuplicateLetters(s: string) {
    let lastIndex={}
    let seen={}
    let answer=[]
    
    for(let i=0;i<s.length;i++){
        lastIndex[s[i]]=i
    }
    
    for(let str of s){
        seen[str]=false;
    }
    
    for(let i=0;i<s.length;i++){
         if(seen[s[i]]){
             continue;
         }

         while(answer.length>0 && 
            answer[answer.length-1]>s[i] && 
            i<lastIndex[answer[answer.length-1]]){
              seen[answer.pop()]=false
         }
        answer.push(s[i])
          seen[s[i]]=true
    }
    return answer.join('')
    
};