πŸ”₯[99클럽 μ½”ν…Œ μŠ€ν„°λ””] 10일차 TIL - μ΄μ€‘μš°μ„ μˆœμœ„ν

HOONSSACΒ·2024λ…„ 7μ›” 31일
1

99Club Coding Test Study

λͺ©λ‘ 보기
10/41
post-thumbnail

⏳문제

문제 μ„€λͺ…

이쀑 μš°μ„ μˆœμœ„ νλŠ” λ‹€μŒ 연산을 ν•  수 μžˆλŠ” 자료ꡬ쑰λ₯Ό λ§ν•©λ‹ˆλ‹€.

λͺ…λ Ήμ–΄μˆ˜μ‹  탑(높이)
I μˆ«μžνμ— 주어진 숫자λ₯Ό μ‚½μž…ν•©λ‹ˆλ‹€.
D 1νμ—μ„œ μ΅œλŒ“κ°’μ„ μ‚­μ œν•©λ‹ˆλ‹€.
D -1νμ—μ„œ μ΅œμ†Ÿκ°’μ„ μ‚­μ œν•©λ‹ˆλ‹€.

이쀑 μš°μ„ μˆœμœ„ 큐가 ν•  μ—°μ‚° operationsκ°€ λ§€κ°œλ³€μˆ˜λ‘œ μ£Όμ–΄μ§ˆ λ•Œ, λͺ¨λ“  연산을 μ²˜λ¦¬ν•œ ν›„ 큐가 λΉ„μ–΄μžˆμœΌλ©΄ [0,0] λΉ„μ–΄μžˆμ§€ μ•ŠμœΌλ©΄ [μ΅œλŒ“κ°’, μ΅œμ†Ÿκ°’]을 return ν•˜λ„λ‘ solution ν•¨μˆ˜λ₯Ό κ΅¬ν˜„ν•΄μ£Όμ„Έμš”.

μ œν•œ 사항

  • operationsλŠ” 길이가 1 이상 1,000,000 μ΄ν•˜μΈ λ¬Έμžμ—΄ λ°°μ—΄μž…λ‹ˆλ‹€.
  • operations의 μ›μ†ŒλŠ” 큐가 μˆ˜ν–‰ν•  연산을 λ‚˜νƒ€λƒ…λ‹ˆλ‹€.
  • μ›μ†ŒλŠ” β€œλͺ…λ Ήμ–΄ 데이터” ν˜•μ‹μœΌλ‘œ μ£Όμ–΄μ§‘λ‹ˆλ‹€.- μ΅œλŒ“κ°’/μ΅œμ†Ÿκ°’μ„ μ‚­μ œν•˜λŠ” μ—°μ‚°μ—μ„œ μ΅œλŒ“κ°’/μ΅œμ†Ÿκ°’μ΄ λ‘˜ 이상인 경우, ν•˜λ‚˜λ§Œ μ‚­μ œν•©λ‹ˆλ‹€.
  • 빈 큐에 데이터λ₯Ό μ‚­μ œν•˜λΌλŠ” 연산이 μ£Όμ–΄μ§ˆ 경우, ν•΄λ‹Ή 연산은 λ¬΄μ‹œν•©λ‹ˆλ‹€.

μž…μΆœλ ₯ 예

operationsreturn
["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"][0,0]
["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"][333, -45]

μž…μΆœλ ₯ 예 μ„€λͺ…

μž…μΆœλ ₯ 예 #1

  • 16κ³Ό -5643을 μ‚½μž…ν•©λ‹ˆλ‹€.
  • μ΅œμ†Ÿκ°’μ„ μ‚­μ œν•©λ‹ˆλ‹€. -5643이 μ‚­μ œλ˜κ³  16이 λ‚¨μ•„μžˆμŠ΅λ‹ˆλ‹€.
  • μ΅œλŒ“κ°’μ„ μ‚­μ œν•©λ‹ˆλ‹€. 16이 μ‚­μ œλ˜κ³  이쀑 μš°μ„ μˆœμœ„ νλŠ” λΉ„μ–΄μžˆμŠ΅λ‹ˆλ‹€.
  • μš°μ„ μˆœμœ„ 큐가 λΉ„μ–΄μžˆμœΌλ―€λ‘œ μ΅œλŒ“κ°’ μ‚­μ œ 연산이 λ¬΄μ‹œλ©λ‹ˆλ‹€.
  • 123을 μ‚½μž…ν•©λ‹ˆλ‹€.
  • μ΅œμ†Ÿκ°’μ„ μ‚­μ œν•©λ‹ˆλ‹€. 123이 μ‚­μ œλ˜κ³  이쀑 μš°μ„ μˆœμœ„ νλŠ” λΉ„μ–΄μžˆμŠ΅λ‹ˆλ‹€.

λ”°λΌμ„œ [0, 0]을 λ°˜ν™˜ν•©λ‹ˆλ‹€.

μž…μΆœλ ₯ 예 #2

  • -45와 653을 μ‚½μž…ν›„ μ΅œλŒ“κ°’(653)을 μ‚­μ œν•©λ‹ˆλ‹€. -45κ°€ λ‚¨μ•„μžˆμŠ΅λ‹ˆλ‹€.
  • -642, 45, 97을 μ‚½μž… ν›„ μ΅œλŒ“κ°’(97), μ΅œμ†Ÿκ°’(-642)을 μ‚­μ œν•©λ‹ˆλ‹€. -45와 45κ°€ λ‚¨μ•„μžˆμŠ΅λ‹ˆλ‹€.
  • 333을 μ‚½μž…ν•©λ‹ˆλ‹€.

이쀑 μš°μ„ μˆœμœ„ 큐에 -45, 45, 333이 λ‚¨μ•„μžˆμœΌλ―€λ‘œ, [333, -45]λ₯Ό λ°˜ν™˜ν•©λ‹ˆλ‹€.


βœοΈν’€μ΄

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = new int[2];
        
        // μ΅œμ†Œ νž™ 생성
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        // μ΅œλŒ€ νž™ 생성
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        
        for (String operation : operations) {
            // 곡백을 κΈ°μ€€μœΌλ‘œ 뢄리
            String[] temp = operation.split(" ");
            
            // λͺ…령이 "I"인 경우 각각의 μš°μ„ μˆœμœ„ 큐에 μΆ”κ°€
            if (temp[0].equals("I")) {
                minHeap.add(Integer.parseInt(temp[1]));
                maxHeap.add(Integer.parseInt(temp[1]));
            }
            
            else if (!maxHeap.isEmpty() && temp[0].equals("D") && temp[1].equals("1")) {
                int max = maxHeap.poll();
                minHeap.remove(max);
            }
            else if (!minHeap.isEmpty() && temp[0].equals("D") && temp[1].equals("-1")) {
                int min = minHeap.poll();
                maxHeap.remove(min);
            }
        }
        
        if (maxHeap.isEmpty() && minHeap.isEmpty()) {
            answer[0] = 0;
            answer[1] = 0;
        }
        
        else {
            answer[0] = maxHeap.poll();
            answer[1] = minHeap.poll();
        }
        
        return answer;
    }
}

이 λ¬Έμ œμ—μ„œλŠ” μ΅œμ†Œκ°’κ³Ό μ΅œλŒ“κ°’μ„ λ™μ‹œμ— 닀루어야 ν•˜κΈ° λ•Œλ¬Έμ—,
μš°μ„  μ΅œμ†Œ νž™κ³Ό μ΅œλŒ€ νž™μ„ 각각 생성해 μ£Όμ—ˆλ‹€.

이제 operations 배열을 μ²˜λ¦¬ν•  차둀이닀.

operationsμ—λŠ” I 숫자, D 1, D -1쀑 ν•˜λ‚˜μ˜ 값이 μš”μ†Œλ‘œ λ“€μ–΄κ°€ 있기 λ•Œλ¬Έμ—, 이에 λ”°λ₯Έ 쑰건을 뢄리해 μ£Όμ–΄μ•Ό ν•œλ‹€.

그러기 μœ„ν•΄ 곡백을 κΈ°μ€€μœΌλ‘œ 일단 λ¬Έμžμ—΄μ„ 뢄리해 μ•ž κΈ€μžκ°€ I인 경우, μ•ž κΈ€μžκ°€ D이고 λ’· κΈ€μžκ°€ 1인 경우, μ•ž κΈ€μžκ°€ D이고 λ’· κΈ€μžκ°€ -1인 경우둜 λ‚˜λˆ„μ–΄ μ£Όμ—ˆλ‹€.

μ—¬κΈ°μ„œ λ§Œμ•½ 첫 번째 쑰건으둜 λ“€μ–΄κ°€κ²Œ λ˜μ—ˆμ„ λ•Œ, 각각의 μš°μ„ μˆœμœ„ 큐에 뒀에 μ˜€λŠ” 숫자λ₯Ό μΆ”κ°€ν•΄μ£Όμ—ˆλ‹€.

λ§Œμ•½ 두 번째 쑰건으둜 λ“€μ–΄κ°€κ²Œ λ˜μ—ˆμ„ λ•Œ, 즉, μ΅œλŒ“κ°’μ„ μ‚­μ œν•΄μ•Ό ν•˜κΈ° λ•Œλ¬Έμ—, μ΅œλŒ€ νž™ maxHeapμ—μ„œ poll()ν•¨μˆ˜λ₯Ό μ‚¬μš©ν•΄ μ΅œλŒ“κ°’(루트 λ…Έλ“œ)λ₯Ό μΆ”μΆœ ν›„ μ œκ±°ν•΄ μ£Όμ—ˆλ‹€.
μ—¬κΈ°μ„œ, μ΅œμ†Œ νž™μ—λ„ ν•΄λ‹Ή 값을 μ œκ±°ν•΄ μ£Όμ–΄μ•Ό ν•˜κΈ° λ•Œλ¬Έμ—, removeν•¨μˆ˜λ₯Ό μ‚¬μš©ν•΄ μ΅œλŒ“κ°’μ„ μ œκ±°ν•΄ μ£Όμ—ˆλ‹€.

μ„Έ 번째 쑰건으둜 λ“€μ–΄κ°€κ²Œ λ˜μ—ˆμ„ λ•ŒλŠ” μ΅œμ†Ÿκ°’μ„ μ‚­μ œν•΄μ•Ό ν•˜κΈ° λ•Œλ¬Έμ—, μ΅œλŒ“κ°’μ„ μ œκ±°ν–ˆλ˜ 방식과 λ§ˆμ°¬κ°€μ§€λ‘œ μ΅œμ†Œ νž™μ—μ„œ 루트 λ…Έλ“œλ₯Ό μ œκ±°ν•˜κ³ , μ΅œλŒ€ νž™μ—λ„ ν•΄λ‹Ή 값을 μ œκ±°ν•΄ μ£Όμ—ˆλ‹€.

이제 λ§ˆμ§€λ§‰ 쑰건을 μ²˜λ¦¬ν•΄μ•Ό ν•œλ‹€.

λͺ¨λ“  연산을 μ²˜λ¦¬ν•œ ν›„ 큐가 λΉ„μ–΄μžˆμœΌλ©΄, [0, 0]을 λ°˜ν™˜ν•΄μ•Ό ν•˜κΈ° λ•Œλ¬Έμ—, ν•΄λ‹Ή 쑰건문을 λ§Œλ“€μ–΄ 처리λ₯Ό ν•΄μ£Όμ—ˆκ³ ,
큐가 λΉ„μ–΄μžˆμ§€ μ•ŠμœΌλ©΄, μ΅œμ’…μ μœΌλ‘œ μ΅œλŒ“κ°’κ³Ό μ΅œμ†Ÿκ°’μ„ 각각 λ°˜ν™˜ν•΄ μ£Όμ–΄μ•Ό ν•˜κΈ° λ•Œλ¬Έμ—,
각각의 μš°μ„ μˆœμœ„ νμ—μ„œ 루트 λ…Έλ“œλ₯Ό μΆ”μΆœν•΄ answer배열에 λ‹΄μ•„μ„œ λ°˜ν™˜ν•΄μ€ŒμœΌλ‘œμ¨ 문제λ₯Ό ν•΄κ²°ν•  수 μžˆμ—ˆλ‹€!


πŸ”—λ¬Έμ œ 링크
πŸ’»Repository

profile
ν›ˆμ‹Ήμ˜ κ°œλ°œμ—¬ν–‰

1개의 λŒ“κΈ€

comment-user-thumbnail
2024λ…„ 8μ›” 1일

πŸ‘ŠπŸ‘Šμ•„μžμ•„μž!

λ‹΅κΈ€ 달기