오늘 진행한 것들 🤔

• 알고리즘 3문제 풀이 (정렬,그리디)

• 토이프로젝트 개발
  • 계정 엔티티 모델링 후 스프링 시큐리티 적용, 리액트 적용

오늘의 배운 점 🤔

• 오랜만에 정렬 문제들을 다시 풀어보았습니다.
  • 전보다 정렬에 대한 이해도가 더 높아진것 같습니다.
  • 조금 더 신경쓰면 좋을것은 정렬을 직접 구현할 수 있는 문제가 나온다면 힘들어할것 같다는 생각이 들었습니다.
  • 단순히 comparator 를 이용한 정렬은 이제 어느정도 감이 익은것 같습니다.
• 토이프로젝트를 진행했습니다.
  • 리액트를 처음으로 활용해보았습니다.
    • 전부터 배워보고싶었던 리액트를 사용해보았습니다.
    • 타임리프로 구현했던 뷰와 다르게 리액트를 활용하니 모든 상황에서 데이터를 파싱하여 사용해야하는구나 를 느끼게 되었습니다.
    • 하지만 제이쿼리와 타임리프를 활용해 구현했던것과 다르게 확실히 모듈화라는게 얼마나 좋은것인지 다시 한번 느끼게 되었습니다.
    • 프론트엔드를 객체지향방식처럼 짤 수 있으면 굉장히 효율적이겠다라는 생각을 했었는데 정말 머지않았구나.. 라는 생각이 듭니다.
  • 계정 로그인 관련 기능들을 구현했습니다.
    • 단순히 백엔드쪽에서 로그인을 할떄는 신경쓸게 없었는데, 프론트와 백을 완전히 분리시켜버리니 로그인을 어떻게 해야할까에 대한 고민이 생겼습니다.
    • 이전에 쿠키에 JWT토큰을 저장하는 방식으로 로그인을 구현했었는데, 이번에도 고민을 해봐야할것같습니다.

문제

남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 차가 최소가 되게 하려 한다.

통나무 건너뛰기의 난이도는 인접한 두 통나무 간의 높이의 차의 최댓값으로 결정된다. 높이가 {2, 4, 5, 7, 9}인 통나무들을 세우려 한다고 가정하자. 이를 [2, 9, 7, 4, 5]의 순서로 세웠다면, 가장 첫 통나무와 가장 마지막 통나무 역시 인접해 있다. 즉, 높이가 2인 것과 높이가 5인 것도 서로 인접해 있다. 배열 [2, 9, 7, 4, 5]의 난이도는 |2-9| = 7이다. 우리는 더 나은 배열 [2, 5, 9, 7, 4]를 만들 수 있으며 이 배열의 난이도는 |5-9| = 4이다. 이 배열보다 난이도가 낮은 배열은 만들 수 없으므로 이 배열이 남규가 찾는 답이 된다.

입력

입력은 T개의 테스트 케이스로 이루어져 있다. 첫 줄에 T가 주어진다.

이어지는 각 줄마다 첫 줄에 통나무의 개수를 나타내는 정수 N(5 ≤ N ≤ 10,000), 둘째 줄에 각 통나무의 높이를 나타내는 정수 Li가 주어진다. (1 ≤ Li ≤ 100,000)

출력

각 테스트 케이스마다 한 줄에 주어진 통나무들로 만들 수 있는 최소 난이도를 출력하시오.

예제 입력 1 복사

3
7
13 10 12 11 10 11 12
5
2 4 5 7 9
8
6 6 6 6 6 6 6 6

예제 출력 1 복사

1
4
0

풀이

문제를 읽다보면 힌트가 나와있다.

2 4 5 7 9 로 입력받을때

2 5 9 7 4 에서 9-5 를 해서 난이도가 4가 나온다고 굉장히 친절하게 알려주고있다.

단순히 이것을 응용해서 입력받은 배열을 가장 큰 수가 중앙에 오고 그 다음으로 큰수가 중앙의 오른쪽, 그다음으로 큰수가 왼쪽으로 오게 만들면된다.

우선순위 큐를 활용해서 가장 큰 순서대로 정렬받은 배열을 먼저 만들고,

새로 정렬할 배열을 생성해준 후 왼쪽과 오른쪽 인덱스를 만들어주고 while 문으로 2개씩 poll해서 삽입해주면 된다.

그러면 배열의 순서상으론 맨 처음값과 맨 끝 값이 원래의 오름차순으로 데이터가 들어가있을건데,

이 두개를 뺀 값의 절대값을 max 변수에 대입해주고 배열을 처음부터 비교해서 더 큰 값이 나온다면 max를 바꿔주는 식으로 풀이하면 된다. (통나무 높이를 뺐을때 가장 큰 값이 난이도가 된다고 문제에 나와있다.)

package baekjoon.a11497;


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class a11497 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for(int i=0; i<T;i++){
            int N = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2-o1);
            int[] arr = new int[N];
            for(int j=0; j<N;j++){
                queue.add(Integer.valueOf(st.nextToken()));
            }
            arr[N/2]=queue.poll();
            int left = N/2-1;
            int right = N/2+1;
            while(!queue.isEmpty()){
                if(right<N){
                arr[right++]=queue.poll();}
                if(!queue.isEmpty()){
                arr[left--]=queue.poll();}
            }
            int max = Math.abs(arr[0]-arr[N-1]);
            for(int j=1; j<N;j++){
               max = Math.max(max,Math.abs(arr[j]-arr[j-1]));
            }
            System.out.println(max);
        }
    }

}

5
ABCD
145C
A
A910
Z321

A
ABCD
Z321
145C
A910

2
Z19
Z20

Z20
Z19

4
34H2BJS6N
PIM12MD7RCOLWW09
PYF1J14TF
FIPJOTEA5

FIPJOTEA5
PYF1J14TF
34H2BJS6N
PIM12MD7RCOLWW09

5
ABCDE
BCDEF
ABCDA
BAAAA
ACAAA

ABCDA
ABCDE
ACAAA
BAAAA
BCDEF

풀이

굉장히 친절한 문제이다

문제에 어떻게 정렬을 하라고 다 알려주고 있다.

1 -> A와 B의 길이가 다르다면 짧은것이 먼저 온다.

단순히 조건문으로 A와 B의 길이를 비교해 정렬하면 된다.

2 -> A와 B의 길이가 같다면 문자열 내 모든 숫자의 합 순으로 정렬한다.

마찬가지로 조건문안에 반복문을 삽입하면 된다.

3 -> 두 방법으로도 정렬이 안된다면 단순 사전순으로 정렬한다.

3번째 방법이 문제이다.

두 방법으로도 정렬이 안된다면? 이 어떤 상황일까?

단순하다. A와 B의 길이도 같은데 문자열 내 모든 숫자의 합마저 같다면 이라는 조건이 되어버린다.

단순히 2번의 조건문 안에 숫자의 합을 비교하는 조건문을 추가해주면 된다.

package baekjoon.a1431;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class a1431 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        List<String> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            list.add(br.readLine());
        }
        list.sort((o1, o2) -> {
            if (o1.length() != o2.length()) {
                return o1.length() - o2.length();
            } else {
                int a = 0;
                int b = 0;
                for (int i = 0; i < o1.length(); i++) {
                    int num1 = o1.charAt(i) - '0';
                    int num2 = o2.charAt(i) - '0';
                    if (num1 > 0 && num1 < 10) {
                        a += num1;
                    }
                    if (num2 > 0 && num2 < 10) {
                        b += num2;
                    }
                }
                if (a == b) {
                    return o1.compareToIgnoreCase(o2);
                }
                return a - b;
            }
        });
        list.forEach(System.out::println);
    }
}

2
5
3 2
1 4
4 1
2 3
5 5
7
3 6
7 3
4 2
1 4
5 7
2 5
6 1

풀이

해당 문제는 정렬과 그리디 알고리즘을 활용한 문제이다.

그리디 알고리즘은 배우지 않았지만 대충 탐욕 이라는 뜻을 가진다는걸 알고있기는 하다..

단순하다. 문제의 조건 자체가 다른 지원자보다 하나라도 점수가 낮다면 탈락이 되고, 최대의 합격자수를 가져와주길 바라고 있다.

최대 를 가지려면 일단 생각해봐야 할것이 남들보다 두 점수 모두가 높은 사람들을 탈락시키고 적절한 비율로 합격을 시킬것인지, 아닌지 를 생각해보면 좋다.

하지만 문제 자체는 정렬을 이용해 풀라고 알려주고 있다.

단순히 배열에 값을 입력받아서 서류심사 성적 순으로 정렬하고, 첫번째 지원자의 면접심사 점수보다 낮은 사람이 존재한다면 낮은 사람의 점수를 기억한후 카운트를 ++ 하는식으로 돌리면 된다.

package baekjoon.a1946;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class a1946 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            List<int[]> list = new ArrayList<>();
            int N = Integer.parseInt(br.readLine());
            for (int j = 0; j < N; j++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                list.add(new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())});
            }
            list.sort(Comparator.comparingInt(o -> o[0]));
            int count =1;
             int min = list.get(0)[1];
             for(int k=1; k<list.size();k++){
                 if(min>list.get(k)[1]){
                     min = list.get(k)[1];
                     count++;
                 }
             }
            System.out.println(count);
        }
    }
}

가장 일반적인 풀이방법이라 생각한다.

오늘 진행한 것들 🤔

• 토이프로젝트 설계
  • 외부 API를 활용한 커뮤니티 서비스를 클론코딩 하기로 맘을 먹었다.

• 알고리즘 문제풀이
  • 동적 계획법, 해시테이블, 깊이우선탐색 (?) 프로그래머스 / 백준 문제풀이

오늘의 배운 점 🤔

• 토이프로젝트를 설계했습니다.
  • 추억을 살려서 어렸을때 많이 플레이 했었던 던전앤 파이터의 API를 활용한 프로젝트를 진행해보기로 했습니다.
  • ERD를 설계하는데 왜이렇게 테이블이 적지,, 라고 생각했던 순간 외부 API를 쓰기때문에라는 생각이 스쳐지나갔습니다....
  • 이미 만들어져있는걸 얼마나 잘 활용하느냐도 능력이라고 생각하기때문에.. 어떻게 잘 찜쪄먹을지를 많이 고민해봐야겠습니다.
  • 요즘 헤이해지고있다고 생각했었는데 새로운 시작이라고 느껴집니다.
• 알고리즘 문제풀이
  • 동적계획법 문제를 풀이했습니다.
    • 동적계획법은 풀어도 풀어도 어떠한 조건을 설정해서 풀어나가야할지가 가장 큰 고민거리인것 같습니다..
    • 이번에도 다른 유형의 문제를 맞닥트렸을때 매번 어떻게 조건을 설정할지를 못정해서 틀리기 일수였습니다.
    • 문제를 풀때 마음을 급하게 먹지 말아야하는데.. 그게 잘안되는것 같습니다 ㅜ.ㅠ
  • 프로그래머스 2레벨 문제를 풀이했습니다.
    • 처음으로 2레벨 문제들을 풀이를 안보고 풀어보았습니다..
    • 확실히 실력이 늘고있긴 한가봅니다.
    • 마찬가지로 여러 유형중에 학습하지 못했던 알고리즘문제들은 도전조차 못해보는게 아까웠습니다.
    • 이제 새로 프로젝트도 시작했으니 진짜 하루에 2문제만 풀어보아야겠습니다.

문제 설명

풀이

해당 문제는 반례가 존재한다.

만약에 수가 555, 85 같은 경우에

일반적이라면 85-5, 80+20, 100-100

해서 8번이 걸릴수도 있겠다고 생각할 수 있지만

85+5,90+10,100-100 을 하면 7번인것처럼 예외도 생각해주어야한다.

따라서 조건문으로 해당 자릿수가 첫번째 자리가 아니고 해당 자리수의 숫자가 5이고 그 이전 자릿수의 숫자가 5보다 크거나 같다면 뺴주는게 아니라 숫자를 더해주는게 나을것이다.

    public static int solution(int storey) {
        int answer = 0;
        List<Integer> arr = Arrays.stream(String.valueOf(storey).split("")).map(Integer::parseInt).collect(Collectors.toList());
        int len = String.valueOf(storey).length();
        for (int i = len - 1; 0 <= i; i--) {
            int a = arr.get(i);
            if (5 < a) {
                if (i > 0) {
                    answer += 10 - a;
                    arr.set(i - 1, arr.get(i - 1) + 1);
                } else {
                    answer += 11 - a;
                }
            } else if (i > 0 && a == 5 && arr.get(i - 1) >= 5) {
                answer += 5;
                arr.set(i - 1, arr.get(i - 1) + 1);
            } else {
                answer += a;
            }
        }
        return answer;
    }

문제 설명

풀이

해당 문제는 단순히 정렬을 이용해 풀이하면 된다.

귤의 갯수를 따로 저장하고 갯수별로 정렬을 한 뒤에 같은 크기의 귤의 갯수가 k 보다 크거나 같으면 answer 을 ++ 하여 리턴하고

작다면 k에서 귤의 갯수만큼 뺀 후 다음 크기의 갯수를 비교하면 된다. 

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

class Solution {
    public static int solution(int k,int[] t){
        int answer=0;
       HashMap<Integer,Integer> map = new HashMap<>();
       for(int i=0;i<t.length; i++){
           map.put(t[i],map.getOrDefault(t[i],0)+1);
       }
       List<Map.Entry<Integer,Integer>> list = map.entrySet().stream().sorted(((o1, o2) -> o2.getValue()-o1.getValue())).collect(Collectors.toList());
       for(Map.Entry<Integer,Integer> key : list){
           if(k<=key.getValue()){
               answer++;
               return answer;
           }else{
                k-= key.getValue();
                answer++;
           }
       }return answer;
    }
}

오늘 진행한 것들 🤔

• 알고리즘 풀데이

등 몇문제

오늘의 배운 점 🤔

• 오늘은 알게모르게 알고리즘 문제가 풀고싶어서 풀데이로 진행해보았습니다.
• 동적계획법과 분할정복을 활용해 문제풀이를 진행했습니다.
• 오늘의 수확은 그래도 어제보다 동적계획법을 활용하는법을 익힌것 같다는 것입니다.
  • 동적계획법 문제는 대부분 일정한 패턴으로 반복되는 문제가 많았습니다. 
  • 단순히 하루이틀전까지만 해도 문제를 계속 쳐다봐도 이해가 되지 않았는데 오늘은 풀이를 안보고 제출한 문제도 있어서 뿌듯했습니다.
  • 하지만 안풀린 문제들도 많았습니다. 제출까지 했으나 정리조차도 이해가 안가서 올리지 못한 문제들이 존재합니다.
  • 확실히 풀데이는 잘풀릴때는 괜찮지만 안풀리는 문제가 생기기 시작하면 그떄부터 멘탈이 흔들리는것 같습니다.
  • 내일부터는 절대 이렇게 하지 않고 두문제 이상 풀이하지 않으리라.. 다짐을 하게 됐습니다

목표를 지키지 않으니 세우지 않겠습니다.. 🫠