기록

우선순위 큐

• 우선순위가 가장 높은 요소가 가장 먼저 제거됨

힙 -> 우선순위 큐를  구현하기 위한 자료구조 

• 완전이진트리로서, 최솟값이나 최댓값을 빠르게 찾기 위해 만들어진 자료구조, 반정렬 상태 유지(부모노드값이 자식 노드의 값보다 크거나 작은 상태를 유지)
  • 최소 힙 : 부모 노드 값이 자식 노드 값보다 작거나 같음
  • 최대 힙 : 부모 노드 값이 자식 노드 값보다 크거나 같음
• 인덱스
  • 부모 : 자식 노드 값 / 2
  • 왼쪽 자식 : 부모 노드 값 * 2
  • 오른쪽자식 : 부모 노드 값 *2 + 1
• 삽입 : 가장 마지막 노드에 삽입한 후, 부모 노드와 비교하여 교환
• 삭제 : 가장 크거나 작은 노드이기 때문에 루트 삭제 후, 가장 마지막에 있는 노드를 루트로 올린 후에 자식들과 교환

class MaxHeap:
    def __init__(self):
        self.heap = []

    def push(self, value):
        self.heap.append(value)
        self._heapify_up(len(self.heap) - 1)

    def _heapify_up(self, index):
        parent = (index - 1) // 2 #오른쪽 자식의 경우는 -1을 해주고 2를 나눠줘야 부모가 올바르게 나오므로 1뺌
        if index > 0 and self.heap[index] > self.heap[parent]:
            self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
            self._heapify_up(parent)

    def pop(self):
        if len(self.heap) == 0:
            return 0
        if len(self.heap) == 1:
            return self.heap.pop() #힙에 1개만 있으면 바로 반환

        #1개 이상의요소가 있다면 최상단을 반환 후 가장 마지막에 있는 노드를 루트로 올리고 교환
        max_value = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._heapify_down(0) #자식 노드와 비교
        return max_value

    def _heapify_down(self, index):
        leftc = index * 2 + 1 #0인덱스로 넘겨서 1씩 더해줌
        rightc = index * 2 + 2
        largest = index

        #자식이 없는 경우에는 인덱스 초과하므로 앞의 길이 조건 추가
        if leftc < len(self.heap) and self.heap[leftc] > self.heap[largest]:
            largest = leftc
        if rightc < len(self.heap) and self.heap[rightc] > self.heap[largest]:
            largest = rightc

        #루트 노드가 자식노드와 변경되었다면 교환
        if index != largest:
            self.heap[index], self.heap[largest] = self.heap[largest], self.heap[index]
            self._heapify_down(largest)

heap = MaxHeap()
n = int(input())
input_list = []

for _ in range(n):
    input_list.append(int(input()))

for i in input_list:
    if i == 0:
        print(heap.pop())
    else:
        heap.push(i)

자릿수 더하기

public class Solution {
    public int solution(int n) {
        int answer = 0;
        int temp = 0;
        while (n > 0) {
            answer += n % 10;
            n /= 10; 
        }

        return answer;
    }
}

약수의 합

class Solution {
    public int solution(int n) {
        int answer = 0;
        for(int i = 1; i <= n; i++){
            if(n % i == 0){
                answer += i;
            }
        }
        return answer;
    }
}

나머지가 1이 되는 수 찾기

class Solution {
    public int solution(int n) {
        int answer = 0;
        for (int i = 1; i < 1000000; i++){
            if (n % i == 1){
                answer = i;
                break;
            }
        }
        return answer;
    }
}

x만큼 간격이 있는 n개의 숫자

• 베열 초기화 : float[] a = {1, 2,3 ,4};
• 크기를 지정하고 나중에 값을 넣을 때 : float[] a = new float[3];

class Solution {
    public long[] solution(int x, int n) {
        long[] answer = new long[n];
        answer[0] = x;
        for (int i = 1; i < n; i++){
            answer[i] = answer[i-1] + x;
        }
        return answer;
    }
}

자연수 뒤집어 배열로 만들기

• 배열의 길이 (자릿수)를 알기 위해 temp를 사용
• answer[idx++] = n % 10; 부분에서 n % 10의 값이 long이기 때문에 answer배열의 타입도 long으로 변경

class Solution {
    public long[] solution(long n) {
        int arrCount = 0;
        long temp = n;
        while (temp > 0){
            temp /= 10;
            arrCount += 1;
        }
        
        long[] answer = new long[arrCount];
        int idx = 0;
        while (n > 0){
            answer[idx++] = n % 10;
            n /= 10;
        }
        return answer;
    }
}

n = int(input()) # 사람 수
humans = [] # 덩치가 담긴 리스트
ranking = [] # 순위가 담긴 리스트
for i in range(n):
    x, y = map(int, input().split())
    humans.append([x, y])

for i in range(n):
    count = 1
    for h in humans:
        if h[0] > humans[i][0] and h[1] > humans[i][1]:
            count += 1
    ranking.append(count)

for i in ranking:
    print(i, end=" ")

각도기

class Solution {
    public int solution(int angle) {
        int answer = 0;
        
        if (0 < angle && angle < 90){
            answer = 1;
        } else if(angle == 90) {
            answer = 2;
        } else if(90 < angle && angle < 180) {
            answer = 3;
        } else if(angle == 180) {
            answer = 4;
        }
        
        return answer;
    }
}

짝수의 합

class Solution {
    public int solution(int n) {
        int answer = 0;
        for (int i = 1; i <= n; i++){
            if (i % 2 == 0){
                answer += i;
            }
        }
        return answer;
    }
}

배열의 평균값

• 배열의 길이를 조회할 때는 배열이름.length

class Solution {
    public double solution(int[] numbers) {
        double answer = 0;
        for (int i = 0; i < numbers.length; i++){
            answer += numbers[i];
        }
        answer /= numbers.length;
        return answer;
    }
}

짝수와 홀수

class Solution {
    public double solution(int[] numbers) {
        double answer = 0;
        for (int i = 0; i < numbers.length; i++){
            answer += numbers[i];
        }
        answer /= numbers.length;
        return answer;
    }
}

평균 구하기

class Solution {
    public double solution(int[] numbers) {
        double answer = 0;
        for (int i = 0; i < numbers.length; i++){
            answer += numbers[i];
        }
        answer /= numbers.length;
        return answer;
    }
}

1. 각각의 자릿수를 문자열로 바뀌서 더하기

n = int(input())
ans = 0
for i in range(n):
    num = i #자기 자신 더하기
    j = str(i)
    for k in j: #각 자리수 더하기
        num += int(k)

    if num == n: #조건에 해당된다면 값 리턴
        ans = i
        break

print(ans)

2. 각각의 자릿수를 나머지 연산을 이용하여 더하기

n = int(input())
ans = 0
for i in range(n):
    num = i #자기 자신 더하기
    current_num = i
    while current_num > 0:
        num += current_num % 10 #자릿수마다 더하기
        current_num //= 10 #더한 자릿수는 제거

    if num == n:
        ans = i
        break

print(ans)

n, m = map(int, input().split()) #카드의 개수 / 가장 가까워야 하는 수
cards = list(map(int, input().split())) #카드 리스트
result = 0

# 모든 조합의 수를 구함
for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            card_sum = cards[i] + cards[j] + cards[k]
            
            #조건에 해당되는 새로운 수가 나올 때마다 갱신
            if m >= card_sum and card_sum > result:
                result = card_sum

print(result)

• 구할 수 있는 모든 조합의 수의 카드를 구함 -> for문을 통해서 구함
• 모든 합을 다 저장해놨다가 최대를 찾아야 하나 생각함,, -> 조건에 맞는 변수를 하나 두고 새로운 값이 나올 때마다 갱신

n = int(input()) #도시의 개수
distence = list(map(int, input().split())) #도시간의 거리
city = list(map(int, input().split())) #각 도시별 주유 비용

cost = 0
min_cost = city[0]

for i in range(n-1): #거리 갯수만큼 반복

    #현재 최소 비용보다 더 작다면 갱신
    if min_cost > city[i]:
        min_cost = city[i]

    cost += min_cost * distence[i]

print(cost)

두 수의 나눗셈

• 정수만 출력하는 부분에서 부동소수점형은 (지수, 가수)로 이루어져 있고 int형은 정수형이기 때문에 가수 부분을 버려서 정수 부분만 출력되는 것

class Solution {
    public int solution(int num1, int num2) {
        int answer = 0;
        float n = (float) num1 / num2 * 1000;
        answer = (int) n;
        return answer;
    }
}

잃어버린 괄호

• 핵심은 '-' 괄호 이후에 모든 수들을 더해서 빼는 것
• 1 + 2 + 8 - 9 +7 - 8 이라면 -> 1 + 2 + 8 - (9 + 7 -8)처럼 계산되게

n = input().split('-') #-를 기준으로 리스트로 나눔 / 2 + 3 + 5 - 1 + 7 - 8

#n[0] = 2 + 3 + 5
ans = sum(map(int, n[0].split('+'))) #-이전의 값은 +를 기준으로 나눠서 더함

#- 이후의 다 더할 값들 순회 후 빼기
for i in n[1:]:
    ans -= sum(map(int, i.split('+')))

print(ans)

import java.util.Scanner;

public class 잃어버린괄호 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();

        String[] parts = input.split("-");
        int result = Integer.parseInt(parts[0]);

        for (int i = 1; i < parts.length; i++){
            result -= sum(parts[i]);
        }

        System.out.print(result);
    }

    public static int sum(String str){
        //String을 담을 수 있는 배열
        String[] numbers = str.split("\\+");
        int sum = 0;
        for (String number : numbers){
            sum += Integer.parseInt(number);
        }

        return sum;
    }
}