Portfolio

📑 문제

✏️ 풀이

재영

저는 먼저 최적의 개수를 구했어요. 종일 O() 답만 내뱉어서 시간초과가 났기 때문에 O()만 넘지 말자는 생각이었어요!

그럼 여기서 최적의 값을 구했으니, end는 조건을 설정하여 처음으로 최적의 답안이 나오는 인덱스까지 이동할 수 있어요.

그럼 start도 최적의 답안을 보장하는 데까지 이동할 수 있게 설정해줘요.

이제 이 값을 answer과 서로 비교해줍니다.

start가 최적의 답안을 보장하는 순간까지 왔기 때문에, 다음으로 넘어가면서 gems[start]키를 삭제해줘야 해요. 따라서 start에 1을 더해주면서 넘어갔습니다.

이를 반복하면서 start와 end가 끝까지 계산해내고, 최적의 답안에서 start를 1 더해줍니다. 왜냐하면, 현재 답안은 인덱스에서 1씩 더한 상황인데 end는 이미 1 더해진 상황이며 start는 아직 더하지 않은 상황이니까요.

💡

오늘 많이 정신이 해이해졌었네요😥 앞으로 분발하고 일찍 풀겠습니다! 팀원 분들께 죄송해요!!🙏🏻🙏🏻😂


const solution = gems => {
  let answer = [-Infinity, Infinity]
  const maxCnt = [...new Set(gems)].length;
  const nowJewels = new Map();
  let [ start, end ] = [ 0, 0 ];
  
  while (start < gems.length) {
    while (maxCnt > nowJewels.size && end < gems.length) {
      nowJewels.set(gems[end], nowJewels.has(gems[end]) ? nowJewels.get(gems[end]) + 1 : 1);
      end += 1;
    }
    while (start < gems.length && nowJewels.get(gems[start]) !== 1) {
      nowJewels.set(gems[start], nowJewels.get(gems[start]) - 1);
      start += 1;
    }
    if (maxCnt === nowJewels.size && (answer[1] - answer[0] > end - start )) {
      answer = [ start, end ];
    }
    nowJewels.delete(gems[start])
    start += 1;
  }

  return [ answer[0] + 1, answer[1] ]
}

효성


function addGem(hashMap, key) {
    if(hashMap.has(key)) {
        hashMap.set(key, hashMap.get(key) + 1);
    } else {
        hashMap.set(key, 1);
    }
}
function subGem(hashMap, key) {
    const val = hashMap.get(key);
    if(val > 1) {
        hashMap.set(key, val-1);
    } else {
        hashMap.delete(key);
    }
}
function solution(gems) {
    const set = new Set(gems);
    const hashMap = new Map();
    let left = 0, right = 0;
    const minArea = [-Infinity, Infinity];
    addGem(hashMap, gems[0]);
    while(right < gems.length) {
        if(hashMap.size === set.size) {
            if(minArea[1] - minArea[0] > right - left) {
                minArea[0] = left;
                minArea[1] = right;
            }
            subGem(hashMap, gems[left]);
            left++;
        } else {
            right++;
            addGem(hashMap, gems[right]);
        }
    }
    //index가 0부터 시작한거라 1씩 더해준다.
    minArea[0]++, minArea[1]++;
    return minArea;
}

gem을 가감하는 함수를 만든다.

addGem은 gem을 더하는 함수로 key가 있다면 hashmap에 key를 추가한다. 만약 없다면 첫번째 값을 추가한다.
subGem은 gem을 빼는 함수로 key의 value 값이 1이상이라면 -1을 하고, 1이라면 해당 key를 삭제한다.

포인터 작업을 위한 Set, Map 객체를 만들고 left, right를 0으로, 최소범위를 무한대로 잡는다. 최소범위는 나중에 축소해나갈 예정.

가장 첫 번째 값을 hashMap에 넣는다.

hashMap의 크기와 gems의 길이가 같아질 때까지 right 값을 추가하며 hashMap에 key를 넣는다.

둘의 크기가 같이질 때, minArea의 범위를 right - left로 축소한다.

left 값을 줄여나가며 범위를 축소하다 크기가 달라질 때 다시 right 값을 더한다.

더 이상 더할 right 값이 없을 때 while 문을 탈출한다.

범위가 1부터 시작하기 때문에 minArea를 +1 해주고 반환한다.

🤔

왜 못풀었을까!?ㅜㅜ → Set, Map에 대한 이해 부족, minArea라는 길이를 기반으로 축소해간다는 논리를 생각해내야 함. 작을 때만 갱신한다!!

은찬


class Queue {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }

  enqueue(value) {
    this.queue[this.rear++] = value;
  }

  dequeue() {
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front++;
    return value;
  }

  peek() {
    return this.queue[this.front];
  }

  size() {
    return this.rear - this.front;
  }
}

function solution(gems) {
    const gem = new Map();
    const queue = new Queue();
    let front = 0, back = 100001, tmp = 0;
    
    
    for(const g of gems){
        gem.set(g, true);
    }
    
    const sumOfGems = gem.size;
    gem.clear();
        
    for(let i = 0; i < gems.length; i++){
        const species = gems[i];
        const gemCount = gem.get(species);
        
        if(gemCount >= 1){
            gem.set(species, gemCount + 1);
        } else{
            gem.set(species, 1);
        }
        
        queue.enqueue(species);
        
        while(true){
            const currentGem = queue.peek();
            const currentGemCount = gem.get(currentGem);
            
            if(currentGemCount > 1){
                gem.set(currentGem, currentGemCount - 1);
                queue.dequeue();
                tmp++;
            } else{
                break;
            }
        }
        
        if(gem.size === sumOfGems && back > queue.size()){
            back = queue.size();
            front = tmp;
        }
    }
    
    return [front + 1, front + back];
}

큐와 맵을 활용한 풀이입니다.

우선 모든 보석의 종류의 수를 알아야 하기 때문에 gems를 순회합니다.

map(변수명 : gem)에 보석 종류를 key로, value를 true로 하여 저장합니다.

그러면 map의 크기가 곧 모든 보석의 종류의 수가 됩니다.

보석 종류의 수를 sumOfGems에 저장한 후, gem 맵을 초기화 합니다.(다시 사용하기 위해)

이제 for문을 통해 답을 찾아가도록 합니다.

우선 현재 인덱스의 보석을 species이라고 칭합니다.

gem 맵에서 species를 key로 가지는 value(해당 보석의 개수)를 gemCount에 저장합니다.

처음 for문을 돌 때에는 gem 맵이 초기화 되었기 때문에 gemCount = undefined 일 것입니다.

만약 gemCount가 1개 이상이라면 gem 맵에서 해당 value를 gemCount + 1로 갱신합니다.

gemCount가 0 또는 undefined라면 1로 저장합니다.

큐에 species를 넣어준 후, while문으로 모든 보석이 한 개 이상 들어갔는지 확인합니다.

while문은 큐의 가장 앞에 있는 보석 종류(species)의 개수가 1개 이상이면 해당 보석의 개수를 -1로 바꿔줍니다. 이는 현재 인덱스 말고도 뒤에 같은 종류의 보석이 있다는 뜻입니다. 그러므로 현재 인덱스의 보석을 버리고, 뒤에 있는 보석이 나올 때 다시 queue에 넣도록 합니다. 마지막으로 tmp++을 하여, 보석을 쓸어 담을 진열장의 번호도 갱신해줍니다.

만약 보석 종류의 개수가 1개라면 그냥 break합니다.

while문을 빠져 나오면 gem 맵의 크기와 sumOfGems가 같은지, back의 인덱스가 queue.size()보다 큰지 확인합니다.

true라면 front와 back을 갱신합니다.

모든 for문이 끝나면 [front + 1, front + back]을 리턴합니다.

현석(놀러옴)


function solution(gems) {
    const kinds = new Set(gems);
    const numKind = kinds.size
    const maxLeng = gems.length
    let result = [];
    
    if (numKind === 1) return [1, 1]
    
    if (numKind === maxLeng) return [1, maxLeng]
    
    /*-----------------------------------------*/
    
    let startIdx = 0;
    let endIdx = numKind-1;
    let minDistance = 100001;
    
    const countOfGems = new Map()
    
    for (let i = startIdx; i <= endIdx; i++) {
        const currGem = gems[i]
        
        if (countOfGems.has(currGem)) {
            const countCurrGem = countOfGems.get(currGem) 
            countOfGems.set(currGem, countCurrGem + 1)
        } else {
          countOfGems.set(currGem, 1)
        }
    }
    
    while (startIdx < endIdx) {
      
        if (endIdx === maxLeng ) {
            break;
        }
      
        if (countOfGems.size < numKind) {
            endIdx++;
            const newGem = gems[endIdx]
            if (countOfGems.has(newGem)) {
                const countOfNewGem = countOfGems.get(newGem)
                countOfGems.set(newGem, countOfNewGem + 1)  
            } else {
                countOfGems.set(newGem, 1)
            }
            continue;
        }
      
        if (countOfGems.size === numKind){
            if ( endIdx - startIdx < minDistance) {
                minDistance = endIdx - startIdx;
                result = [startIdx + 1 , endIdx + 1]
            }
            
            const firstGem = gems[startIdx] 
            const countOfFirstGem = countOfGems.get(firstGem)
            countOfGems.set(firstGem, countOfFirstGem - 1);
                if (countOfGems.get(gems[startIdx]) === 0) countOfGems.delete(firstGem)
                startIdx++;
        }
    }
    return result
}

보석 쇼핑

📑 문제

✏️ 풀이