nose딩

class Solution {
    static int[][] dp;
    static int N;
    public int solution(int[][] triangle) {
        int answer = 0;
        N = triangle.length;
        dp = new int[N+1][N+1];

        for(int i=1; i<=N; i++){
            dp[i][1] = dp[i-1][0] + triangle[i-1][0]; //처음
            int M = triangle[i-1].length;
            for(int j=1; j<=M-1; j++){ //중간
                dp[i][j] = Math.max(dp[i-1][j-1],dp[i-1][j]) + triangle[i-1][j-1];
            }
            dp[i][M] = dp[i-1][M-1] + triangle[i-1][M-1]; //끝
        }
        
        for(int i=1; i<=N; i++){
            answer=  Math.max(answer,dp[N][i]); //바닥에서 큰 값
        }
        
        return answer;
    }
}

다시 푸니까 헷갈리네 .. .🥲

class Solution {
    public int solution(int n, int[][] results) {
        int answer = 0;
        int[][] graph = new int[n+1][n+1];
        
        for(int[] i : results){
            graph[i[0]][i[1]]=1; //이긴 경우
        }
        //간접적 승패 업데이트 (A->B, B->C => A->C)
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                for(int z=1; z<=n; z++){
                    if(graph[j][i]==1 && graph[i][z]==1){
                        graph[j][z]=1;
                    }
                }
            }
        }
        //경기 횟수 카운트
        for(int i=1; i<=n; i++){
            int count = 0;
            for(int j=1; j<=n; j++){
                if(graph[i][j]==1 || graph[j][i]==1) count++;
            }
            if(count == n-1) answer++;
        }
        
        return answer;
    }
}

플로이드- 워셜 이용해야 하는 문제

코린이는 모르는게 넘 많습니다 ... 공부하자 아자🌱

*플로이드-워셜 : 모든 정점에서 모든 정점으로 가는 최단거리를 구할 수 있음

class Solution {
    static int[][] minDp;
    static int[][] maxDp;
    static int N;
    public int solution(String arr[]) {
        N = (arr.length/2)+1; //피연산자 개수
        minDp = new int[N][N];
        maxDp = new int[N][N];
        
        for(int i=N-1; i>=0; i--){
            for(int j=0; j<N; j++){
                if(i==j) { //피연산자 저장
                    maxDp[i][j] = minDp[i][j] = Integer.parseInt(arr[i*2]);
                }else{ 
                    maxDp[i][j] = Integer.MIN_VALUE; //초기화
                    minDp[i][j] = Integer.MAX_VALUE; //초기화
                    
                    for(int k=i; k<j; k++){ //i~j까지 계산
                        if(arr[2*k+1].equals("+")){
                            minDp[i][j] = Math.min(minDp[i][j],minDp[i][k]+minDp[k+1][j]);
                            maxDp[i][j] = Math.max(maxDp[i][j],maxDp[i][k]+maxDp[k+1][j]);
                        }else{ //'-' 경우
                            minDp[i][j] = Math.min(minDp[i][j],minDp[i][k]-maxDp[k+1][j]);
                            maxDp[i][j] = Math.max(maxDp[i][j],maxDp[i][k]-minDp[k+1][j]);
                        }
                    }
                }
            }
        }
        
        return maxDp[0][N-1];
    }
}

최댓값을 구하는 문제

=>최대가 나오기 위해선

+의 경우: 최대 + 최대

-의 경우: 최대 - 최소

따라서 최대, 최소를 다루는 각 dp 만들어주고

피연산자를 저장한다.

그외 부분은 정수 최소값, 최대값으로 초기화해준다.

완벽히 이해하고 싶다 아아아아아아 🥲

import java.util.HashSet;
import java.util.ArrayList;
import java.util.List;
import java.util.Set;
class Solution {
    public int solution(int N, int number) {
        List<Set<Integer>> result = new ArrayList<>();
        for(int i=0; i<=8; i++){
            result.add(new HashSet<>());
        }
        result.get(1).add(N); //N을 1개만 쓰는 경우
        
        for(int i=1; i<=8; i++){
            Set<Integer> set = result.get(i); //현재 set
            set.add(Integer.parseInt(String.valueOf(N).repeat(i)));
            
            for(int j=1; j<i; j++){ //이전 set들 사칙연산
                for(int left : result.get(j)){
                    for(int right : result.get(i-j)){
                        set.add(left+right);
                        set.add(left-right);
                        set.add(left*right);
                        if(right!=0) set.add(left/right);
                    }
                }
            }
            
            if(set.contains(number)) return i;   
        }
        return -1;
    }
}

전에 dfs로 풀었다가 명색이 dp 문젠데 ....라 해서 다시 풀었다.

result에 set이 들어가게되는데

index가 1인 경우가 N이 1개인 경우,

index가 2인 경우가 N이 2개인 경우 .... 

로 index를 바로 이용하기 위해 0은 빈공간으로 만들어주었다.

import java.util.HashMap;
import java.util.HashSet;
import java.util.StringTokenizer;
class Solution {
    public int[] solution(String[] id_list, String[] report, int k) {
        HashMap<String, HashSet<String>> reportPeople = new HashMap<>(); //신고 당한 사람, 신고한사람
        HashMap<String, Integer> reportCount = new HashMap<>(); //사람 별 신고 횟수
        int[] answer = new int[id_list.length];
        //map초기화
        for (int i = 0; i < id_list.length; i++) {
	        reportPeople.put(id_list[i], new HashSet<String>());
	        reportCount.put(id_list[i], 0);
        }
        StringTokenizer st;
        for(int i =0;i<report.length; i++){
            st = new StringTokenizer(report[i]," ");
            String user1 = st.nextToken();
            String user2 = st.nextToken();
            reportPeople.get(user2).add(user1);
        }
       
        for (String key : reportCount.keySet()) { 
            HashSet<String> set = reportPeople.get(key); 
                if(set.size() >= k) { 
                    for (String setKey : set) {
                        reportCount.put(setKey, reportCount.get(setKey)+1);
                    } 
                } 
        } 
        
        for (int i = 0; i < id_list.length; i++) {
            answer[i] = reportCount.get(id_list[i]); 
        }

        
        return answer;
    }
}

아 똥멍청인가 아ㅓㄹ ㅏ어아ㅓㅏ

1단계가 더 못풀겠네;; ^_ㅜ

import java.util.ArrayList;
import java.util.List;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Collections;
import java.util.HashMap;
import java.util.Collections;
class Solution {
    public int[] solution(String[] genres, int[] plays) {
        ArrayList<Integer> result = new ArrayList<>();
        
        Song[] songs = new Song[genres.length];
        HashMap<String, ArrayList<Song>> genreSongs = new HashMap<>();   //장르별 노래
        HashMap<String, Integer> genrePlays = new HashMap<>();//장르별 재생 횟수
        for(int i=0; i<genres.length; i++){
            songs[i]=new Song(i,genres[i],plays[i]);
            if(genrePlays.containsKey(genres[i])){
                genrePlays.put(genres[i],genrePlays.get(genres[i])+plays[i]);
            }else{
                genrePlays.put(genres[i],plays[i]);
            }
            if(genreSongs.containsKey(genres[i])){
                ArrayList<Song> al = genreSongs.get(genres[i]);
                al.add(songs[i]);
                genreSongs.put(genres[i],al);
            }else{
                ArrayList<Song> al = new ArrayList<>();
                al.add(songs[i]);
                genreSongs.put(genres[i],al);
            }
        }
        
        //장르 횟수 합 기준으로 정렬
        ArrayList<String> keySetList = new ArrayList<>(genrePlays.keySet());
        Collections.sort(keySetList,new Comparator<String>(){
            @Override
            public int compare(String a, String b){
                return genrePlays.get(b)-genrePlays.get(a);
            }
        });
                         
        for(String s : keySetList){ //같은 장르
           //같은 장르내에서 많이 재생된 노래 ~ 
           ArrayList<Song> al = genreSongs.get(s);
           Collections.sort(al, new Comparator<Song>(){
              @Override
               public int compare(Song s1, Song s2){
                   int temp = s2.plays-s1.plays;
                   if(temp==0){
                       temp = s1.id-s2.id;
                   }
                   return temp;
               }
           });
            //최대 두개
            int count = 1;
            for(Song so : al){
                if(count>2) break;
                result.add(so.id);
                count++;
            }
        }
        
        int answer[] = new int[result.size()];
        
        for(int i=0; i<result.size(); i++){
            answer[i]=result.get(i);
        }
        
        return answer;
    }
}
class Song{
    int id;
    String genre;
    int plays;
    public Song(int id,String genre,int plays){
        this.id=id;
        this.genre=genre;
        this.plays=plays;
    }
}

너무 더러워 더러워 흑흑

해시맵 정렬은,, keySet 정렬 이용하기 ,,, 메모 

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        int whM = brown+yellow;
        int whP = ((whM-yellow)/2)+2;
        
        for(int w=1;w<=brown; w++){
            for(int h=1; h<=w; h++){
                if(w+h==whP && w*h==whM){
                    answer[0]=w;
                    answer[1]=h;
                    break;
                }
            }
        }
        
        return answer;
    }
}

wh = brown+yellow

yellow = (w-2)*)(h-2) -> w+h = (wh+4-yellow)/2

돌면서 저 식 두개 만족하면 종료 ,,

class Solution {
    static int[][] dp;
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        int mod = 1000000007;
        dp=new int[n+1][m+1];
        //물 찬 구역 표시하기
        for(int i=0; i<puddles.length; i++){
            dp[puddles[i][1]][puddles[i][0]]=-1;
        }
        dp[1][1]=1;
        for(int i=1; i<=n; i++){
           for(int j=1; j<=m; j++){
               if(dp[i][j]==-1){
                   continue;
               }
               if(dp[i-1][j]!=-1) dp[i][j] += dp[i-1][j]%mod;
               if(dp[i][j-1]!=-1) dp[i][j] += dp[i][j-1]%mod;
           }
        }
        return (dp[n][m])%mod;
    }
}

아니 왜 안될까 하며 뭐지 했는데 내가 문제 잘못읽었다 ;;;; ;;; 어이없어 ㅠ

최단경로 개수구하는 거였는데 그냥 최단경로일때 숫자 구하는줄 알았다;;;ㅠ; 오늘의 멍청비용 ㅠ