yeosang0508 님의 블로그

문제정리

현재 피로도를 k, 2차원 배열 dungeons에 최소 필요 피로도, 소모 피로도가 담긴 값을 주어진다.
유저가 탐험할 수 있는 최대 던전 수를 반환

처음 해결하려고 생각해본건.. 일단 소모 피로도를 정렬해서 작은 수를 대입, 던전을 도는 방법을 선택하려고 했다가 최소 피로도가 높아서 못들어가면 어쩌나 하는 고민이 또 생김.. 그렇다면 모든 조건을 대입해서 값을 내야할 것 같은데 어떻게..? 대입해야하는 걸까... ??

생각하다가.. 도저히 해결법을 생각해낼 수 없어 구글링해서 해결했다.. 내일 한번 더 풀어봐야지

최종코드

class Solution {
    private static int answer;
    private static boolean[] visit;

    public int solution(int k, int[][] dungeons) {
       int depth = 0;
       visit = new boolean[dungeons.length];

       dfs(depth, k, dungeons);

       return answer;
    }

    private  static  void dfs(int depth, int k, int[][] dungeons){
        for(int i = 0; i < dungeons.length; i++){
            if(!visit[i] && k >= dungeons[i][0]) { // 방문하지 않았고, 최소 피로도 조건 충족
                visit[i] = true; // 방문 처리
                dfs(depth + 1, k - dungeons[i][1], dungeons); // 피로도 감소 & 다음 탐색
                visit[i] = false; // 원상 복구 (백트래킹)
            }
        }

        answer = Math.max(answer,depth);
    }
}

이 방법을 보고 왜 for문인데 모든 경우를 탐색할 수 있는걸까..? 라는 생각이 들었는데, 각 dfs() 호출마다 for문이 실행되므로, 그때마다 새로운 던전을 선택할 수 있다!
재귀 호출 후 visit[i] = false;를 수행하여 던전을 취소하고 다른 경우를 탐색할 수 있다!!
이렇게 모든 경우를 탐색할 수 있음..

해결확인 후 다시 풀어봤을때 시간

내일 한번 더 풀어보자 !

문제정리

정수가 담긴 배열 numbers의 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return

처음 작성한 코드

class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        ArrayList<Integer> list = new ArrayList<>();
        int num;

        for (int i = 0; i < numbers.length; i++) {
            String str = "" + numbers[i];

            for (int j = 0; j < numbers.length ; j++) {
                if (i == j) {
                    continue;
                }
                str = str + numbers[j];
            }
            num = Integer.parseInt(str);

            list.add(num);

        }

        Collections.sort(list);

        answer = "" + list.get(list.size()-1);

        return answer;
    }
}

처음에는 위와같이 짰는데 이유는.. 순서대로 정수 위치시키고 오름차순으로 정렬.. 근데 문제는 6, 10, 2 배열이라면 6102, 6210... 이런 식으로 되어야 하는데 위 코드는 6210 같은 숫자를 고려하지 않은 점..
시간은

class Solution {
    public String solution(int[] numbers) {
        String[] arr = new String[numbers.length];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = String.valueOf(numbers[i]);
        }

        Arrays.sort(arr, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));
        
        if (arr[0].equals("0")) {
           return "0";
        }

        StringBuilder answer = new StringBuilder();

        for (int i = 0; i < arr.length; i++) {
            answer.append(arr[i]);
        }


        return answer.toString();
    }
}

문제정리

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수 반환
commands 배열에 [i,j,k] 원소로 가진 2차원 배열 매개변수로 주어짐
배열을 순서대로 새면 0부터 시작하지만 i가 1이면 0번째가 1로 시작한다고 생각해야함

작성 코드

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];

        for(int i = 0; i < commands.length; i++){
            int start = commands[i][0] - 1;
            int end = commands[i][1] - 1;
            int k = commands[i][2] - 1;

            int count = end - start + 1;
            int[] arr = new int[count];
            for( int j = start; j < end; j++){
                arr[count - 1] = array[j];

                count--;
            }
            Arrays.sort(arr);
            answer[i] = arr[k];
        }

        return answer;
    }
}

for문으로 일단 해결하긴했는데, 좀 더 분명 간략한 방법이 있을 듯

Arrays.copyOfRange() 메소드 사용

class Solution {
	public int[] solution(int[] array, int[][] commands) {
		int[] answer = new int[commands.length];

		for (int i = 0; i < commands.length; i++) {
			int[] temp = Arrays.copyOfRange(array, commands[i][0] - 1, commands[i][1]); 
            					  
			Arrays.sort(temp);
			answer[i] = temp[commands[i][2] - 1];
		}
		return answer;
	}
}

Arrays.copyOfRange(array, start, end)

start는 배열에서 복사를 시작할 인덱스, end는 복사를 끝낼 인덱스로 end 직전 인덱스까지만 복사된다고 함!

문제정리

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses
각 작업의 개발 속도가 적힌 정수 배열 speeds
배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정

처음 작성한 코드

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        int a = 1;

        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < progresses.length; i++) {
            int num = 100 - progresses[i];

            int count = num / speeds[i];

            list.add(count);
        }

        int count = 0;

        List<Integer> list2 = new ArrayList<>();

        for (int i = 1; i < list.size(); i++) {

            if (list.get(count) >= list.get(i)) {
                a++;
                continue;
            } else {
                count = i;
                list2.add(a);
                a = 1;
            }
        }
        list2.add(a);
        return list2.stream().mapToInt(i -> i).toArray();
    }
}

list에는 각각 기능 작업이 몇 일간 작업 후 배포가 가능한지 들어가게 하였고, 그 아래 list를 비교하여 기간보다 작거나 같을 경우를 카운트하여 다시 list2에 넣을 수 있도록 하였는데 결과는... 실패

뭐가 문제일까..
.
.

int count = num / speeds[i]; 와 이거 할 때 왜 올림된다고 생각한거지..?
Math.ceil을 사용해서 올림 처리해야지...!

수정 코드

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        List<Integer> days = new ArrayList<>();
        
        // 각 작업이 완료되기까지 걸리는 날짜 계산
        for (int i = 0; i < progresses.length; i++) {
            int remain = 100 - progresses[i];
            int day = (int) Math.ceil((double) remain / speeds[i]);
            days.add(day);
        }

        List<Integer> result = new ArrayList<>();
        int maxDay = days.get(0); // 첫 번째 작업이 기준
        int count = 1;

        for (int i = 1; i < days.size(); i++) {
            if (days.get(i) <= maxDay) {
                count++; // 같은 배포일에 포함
            } else {
                result.add(count);
                maxDay = days.get(i); // 새로운 기준 업데이트
                count = 1;
            }
        }

        result.add(count); // 마지막 배포 그룹 추가
        return result.stream().mapToInt(i -> i).toArray();
    }
}

변수명도 좀 더 알아보기 쉽게 변경, 반올림 처리했고, 인덱스를 비교하여 값을 냈는데 해당 날 자체를 비교할 수 있도록 변경하였다.

시간은..

큐로 해결하는 방법

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        ArrayList<Integer> list = new ArrayList<>();
        Queue<Integer> q = new LinkedList<>();

        // 1. 각 기능이 완료되기까지 걸리는 날짜를 큐에 저장
        for (int i = 0; i < progresses.length; i++) {
            int remain = 100 - progresses[i];
            int day = (remain % speeds[i] == 0) ? (remain / speeds[i]) : (remain / speeds[i] + 1);
            q.add(day);
        }

        // 2. 배포 그룹 계산
        int x = q.poll();
        int count = 1;
        while (!q.isEmpty()) {
            if (x >= q.peek()) {
                count++;
                q.poll();
            } else {
                list.add(count);
                count = 1;
                x = q.poll();
            }
        }
        list.add(count);

        // 3. 결과 배열로 변환
        return list.stream().mapToInt(i -> i).toArray();
    }
}

일단 큐 사용은 아직 어색한데...
큐는 FIFO로 먼저 들어온 것이 먼저 나가는 자료구조

add()와 offer() 동일하게 데이터를 추가하는 방법을 말한다.
(add()는 큐가 꽉 차 있으면 예외 발생하고, offer()은 false를 반환)

peek()는 큐에서 맨 앞에 있는 데이터를 확인 큐가 비어있으면 null을 반환

poll()은 큐에서 맨 앞에 있는 데이터를 꺼내면서 동시에 삭제! 비어있으면 null을 반환
remove()도 poll()과 동일하게 맨 앞 데이터를 꺼내면서 삭제! 하지만 큐가 비어 있으면 예외 발생

문제정리

배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하고, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 한다.
해당 남은 수들을 return

작성한 코드

class Solution {
    public int[] solution(int[] arr) {
        List<Integer> list = new ArrayList<>();
        list.add(arr[0]);

        for(int i = 1; i < arr.length; i++){
            if(arr[i-1] == arr[i]){
                continue;
            }else {
                list.add(arr[i]);
            }
        }

        int[] answer = new int[list.size()];

        for(int i = 0; i < list.size(); i++){
            answer[i] = list.get(i);
        }
        return answer;
    }
}

연속적으로 나타나는 숫자를 하나만 남기고 전부 제거해야 해야하는데 if(arr[i-1] == arr[i]) 이걸로 해결 하고, int[]에 해당 값을 넣어서 반환시켰는데 뭔가 저 반환하는 값을 다르게 표현할 수 있지 않을까?

일단 시간은..

다른 사람의 코드

import java.util.List;
import java.util.ArrayList;

public class Solution {
    public int[] solution(int[] arr) {
        List<Integer> list = new ArrayList<>();
        list.add(arr[0]);

        for (int i = 1; i < arr.length; i++) {
            if (arr[i - 1] == arr[i]) {
                 continue;
            } else { 
                 list.add(arr[i]);
            }
        }

        return list.stream().mapToInt(i -> i).toArray();
    }
}

list.stream().mapToInt(i -> i).toArray();
Stream을 활용하면 내부적으로 최적화되어 for문을 사용하는 것보다 코드가 더 간결하고 가독성이 좋아진다. 성능 차이는 거의 없음! 하지만 아주 큰 데이터에서는 for 문이 더 빠를 수도 있다!

근데.. Integer과 int의 차이는 뭐지... mapToInt(i -> i)로 Integer에서 int로 변환한다는 건데 왜..

Integer은 객체..! int는 기본형..! (이거 기본이잖아ㅠ 또....)
Integer은 객체이고, null값을 가질 수 있다. 참조형 데이터 타입이라 메모리에 객체로 저장되며 연산을 수행할 때 속도가 느릴 수 있음
int는 기본 자료형, 값 자체를 저장하고 있어서 연산 속도가 빠름

List<Integer>에서 int[] 배열로 변환하려면, 객체를 기본형으로 변환해야하기에..!!

스택으로 해결

import java.util.Stack;

public class Solution {
    public int[] solution(int[] arr) {
        // 스택 생성
        Stack<Integer> stack = new Stack<>();

        // arr 순회
        for (int i : arr) {
            // 스택이 비어있거나 i가 스택의 마지막 요소와 다르면 push
            if (stack.empty() || !stack.peek().equals(i)) {
                stack.push(i);
            }
        }

        // stack을 배열(int[])로 변환
        return stack.stream().mapToInt(i -> i).toArray();
    }
}

중복 제거 로직이 스택의 특성 (LIFO, Last-IN First-Out)을 활용하여 간결
peek() 로 바로 직전 요소를 확인할 수 있다. 맨 위 코드에서 arr[i-1]와 같은 의미

문제정리

각 종류별로 최대 1가지 의상만 착용할 수 있다. 
clothes 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있으며, 같은 이름을 가진 의상은 존재하지 않고 알파벳 소문자 또는 _로만 이루어져 있다. 

처음 작성한 코드

class Solution {
    public int solution(String[][] clothes) {
        int answer = clothes.length;

        Map<String, Integer> type = new HashMap<>();

        for(int i = 0; i < clothes.length; i++){
            type.put(clothes[i][1],type.getOrDefault(clothes[i][1],0) + 1);
        }

        for(int i = 0; i < clothes.length; i++){
            if(type.size() == 1){
                break;
            }

            while(!type.containsValue(0)){
                type.put(clothes[i][1], type.getOrDefault(clothes[i][1], 0) - 1);
                answer++;
            }
        }

        return answer;
    }
}

위와같이 코드를 작성한 이유는 일단 map에 headgear, eyewear와 같이 의상의 종류를 넣고 getOrDefault를 사용하여 종류의 개수를 value 값으로 들어갈 수 있게 지정
아래 코드는 type.size()가 1인 경우에는 의상의 종류가 하나이기에 break를 하여 배열 개수가 반환하게 하였고, while 문은 의상의 종류의 개수가 동일한 값 만큼 개수를 더하게 만들어서 반환되게 하도록 만든건데..
결과는 실패..

진짜 너무 단순하게 생각했던 것 같음 각 경우의 수를 생각을 하고 계산을 했어야 했는데;;

최종코드

class Solution {
    public int solution(String[][] clothes) {
        Map<String, Integer> type = new HashMap<>();

        // 의상 종류별 개수 카운트
        for (String[] cloth : clothes) {
            type.put(cloth[1], type.getOrDefault(cloth[1], 0) + 1);
        }

        int answer = 1;

        // (각 종류별 개수 + 1) 곱하기
        for (int count : type.values()) {
            answer *= (count + 1);
        }

        // 모든 의상을 입지 않는 경우(1) 제외
        return answer - 1;
    }
}

type.values()는 HashMap<String, Integer>에 지정된 각 의상 종류별 개수를 가져오는 역할을 한다. { "headgear":2, "eyewear":1 } 이면 type.values()는 [2, 1] 을 반환하게 된다.

그래도 잘 생각했던 부분은 getOrDefault를 생각해낸 점? 몇일전까지만 해도 저걸 사용해야겠다는 생각을 못했는데.. 굿..

시간은

문제정리

전화번호를 담은 배열 phone_book이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        Map<String, Integer> map = new HashMap<>();

        for(int i = 0; i < phone_book.length; i++){
            map.put(phone_book[i], i);
        }

        for(int i = 0; i < map.size(); i++){
            for(int j = 0; j < phone_book[i].length(); j++){
                if(map.containsKey(phone_book[i].substring(0, j))){
                    return false;
                }
            }
        }


        return answer;
    }
}

phone_book를 hashmap에 값을 넣고, 반복문을 이용해서 폰번호 길이만큼 포함하는지 반환할 수 있도록

containsKey(key) -> 맵에서 인자로 보낸 키가 있으면 true 없으면 false를 반환

containsValue(value) -> 맵에서 인자로 보낸 값이 있으면 true 없으면 false를 반환

HashSet

• 중복을 허용하지 않는 데이터 저장소
• HashMap을 내부적으로 사용하여 데이터를 관리 (값을 HashMap의 key로 저장)
• 순서 보장 X

HashMap

• (Key, Value) 형태로 데이터를 저장 / Key는 중복 불가능, Value는 중복 가능

HashSet은 중복된 값을 허용하지 않고 고유한 값들만 저장해야 할 때, 데이터의 존재 여부만 확인하면 될 때 (contains()로 빠른 탐색 가능) / HashMap은 Key-Value 쌍으로 데이터를 저장해야할 때, 특정 Key에 대해 빠르게 Value를 가져와야 할 때 (get(), put())

문제정리

참여한 선수들의 이름이 담긴 배열 participant, 완주한 선수들의 이름이 담긴 배열 completion
완주하지 못한 선수이름은 return
이름은 알파벳 소문자로 이루어져 있으며, 참가자 중에는 동명이인 존재

이 문제의 포인트 중 하나는 completion의 길이는 participant의 길이보다 1 작다 라는 부분인 것 같다. 그러면 무조건 완주하지 못한 선수가 1명이라는 뜻이기에 그걸 처음에 잡아내지 못함

처음 작성한 코드

import java.util.Arrays;

class Solution {
    public String solution(String[] participant, String[] completion) {
        Arrays.sort(participant);
        Arrays.sort(completion);

        int i = 0;
        for(i=0;i<completion.length;i++)
            if(!participant[i].equals(completion[i]))
                break;

        return participant[i];
    }
}

두 배열을 전부 오름차순으로 정렬해주어 이름이 동일한 위치 오게끔 해주었고, 각 위치에 동일한 이름이 들어있지 않을 시 바로 break 하여 반복문을 종료하고 해당 위치에 있는 참가자를 반환시켰다.

시간은

HashMap 구현

import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        HashMap<String, Integer> map = new HashMap<>();

        // 참가자 명단을 HashMap에 저장 (이름별 개수 카운트)
        for (String p : participant) {
            map.put(p, map.getOrDefault(p, 0) + 1);
        }

        // 완주자 명단을 확인하면서 참가자 명단에서 제거
        for (String c : completion) {
            map.put(c, map.get(c) - 1);
        }

        // value가 1인 참가자가 완주하지 못한 사람
        for (String key : map.keySet()) {
            if (map.get(key) > 0) {
                return key;
            }
        }

        return ""; // 정상적으로 동작하면 여기에 도달하지 않음
    }
}

HashMap은 Key-Value의 Pair를 관리하는 클래스로,
HashMap<String,Integer>로 지정하면 Key는 String, Value는 Integer 형태로 정의하는 것이다.

map.getOrDefault(p, 0) -> HashMap에 값이 있으면 기존 값 반환하고, 없으면 기본값 0을 반환

keySet -> HashMap 에 저장된 모든 키 값들을 가져오는 메서드

이전 코드와 비교했을때 HashMap을 사용하면 정렬 없이 더 빠르게 해결 가능하며, 더 많은 참가자가 있을 경우에도 빠르게 찾을 수 있음.