2023.04.21.FRI

[ 프로그래머스 ]

• 예산
  : 정답률 73%. 가장 많은 부서를 지원해줘야하니까, 보자마자 정렬해서 예산 작은 부서부터 빼줘야겠다고 생각함.

import java.util.*;

class Solution {
    public int solution(int[] d, int budget) {
        Arrays.sort(d);
        int answer = 0;
        for(int i=0; i<d.length; i++){
            budget -= d[i];
            if(budget < 0) return answer;
            answer++;
        }
        return answer;
    }
}

• 숫자 문자열과 영단어
  : 정답률 68%.

import java.util.*;

class Solution {
    public int solution(String s) {
        String[] alpha = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
        String[] nums = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"};

        for(int i=0; i<10; i++){
            if(s.contains(alpha[i])) s=s.replaceAll(alpha[i], nums[i]);
        }
        return Integer.parseInt(s);
    }
}

• 추억 점수
  : 정답률 60%. 다른 사람들 풀이 보니까 삼중 포문 쓴 사람도 있고, Map 쓴 사람도 있었다. 나도 처음에는 Map 쓰려다가 굳이 Map 안 만들어도 될 것 같아서 indexOf()로 풀었음.

import java.util.*;

class Solution {
    public int[] solution(String[] name, int[] yearning, String[][] photo) {
        int[] answer = new int[photo.length];

        for(int i=0; i<photo.length; i++){
            int count = 0;
            for(int j=0; j<photo[i].length; j++){
                if(Arrays.asList(name).indexOf(photo[i][j])>=0) count+=yearning[Arrays.asList(name).indexOf(photo[i][j])];
            }
            answer[i] = count;
        }
        return answer;
    }
}

[ 자료구조와 함께 배우는 알고리즘 입문 ]

: 공부의 필요성을 알고는 있었지만 외면하고 있었던 자료구조...
자료구조 모르고 알고리즘 풀면 안 된다는 조언에 따라 자료구조 공부를 시작하기로 했습니다..
책이랑 유튜브 강의로 공부할 예정.
https://www.youtube.com/watch?v=h2_Lc8a8Ffw&list=PLG7te9eYUi7tAQygBknaTciy8wzLCe-Ll&index=13

• 버블 정렬
  : 양방향 버블 정렬도 있는지 처음 알았음.
  홀수 번째 패스는 가장 작은 걸 맨 앞으로, 짝수 번째 패스는 가장 큰 걸 맨 뒤로.
• 선택 정렬
  : 시간복잡도 N제곱에, 구현도 버블 정렬보다 까다롭고, 최솟값/최댓값으로 떨어져있는 요소를 비교하므로 안정성도 높지 않으므로 실제로 코딩테스트에 잘 사용하지는 않음.
• 삽입 정렬
  : 선택 정렬보다 더 별로임,,
  비교하고 적당한 위치에 삽입해야하는데, 매번 배열 복사할 거 아닌 이상,,
  비교는 이진 탐색으로 시간 복잡도 줄일 수 있음.
  -> 셸 정렬
• 퀵 정렬 ???
• 병합 정렬
  : O(nlogn), 투 포인터
• 힙 정렬
  : 부모 노드가 자식 노드보다 항상 크거나 항상 작은 일정한 관계를 갖는 완전이진트리를 이용한 정렬
• 도수 정렬 ???

[ 유어클래스 다시 읽기 ]

• section1
  • 객체지향 프로그래밍 심화
    • 캡상추다
    • 단일 상속(single inheritance)
    • 포함(composite) 관계
    • Object 클래스
    • 접근 제어자(only once) / 기타 제어자
    • final : 클래스 상속 불가, 메서드 오버라이딩 불가, 변수 값 변경 불가
    • 인터페이스

[ 느낀 점 ]

자료구조랑 알고리즘 진짜 모르겠다😣🥲😱🤯🔫
주말에 놀 계획과 놀 마음이 가득한데, 밤에는 잠깐씩 자료구조 읽어보기라도 하기..

정답률 70%, 60%대의 문제들에 지레 겁먹었는데, 생각보다 할만해서 다음에는 50%대 도전해볼 것.