Part of your World

https://school.programmers.co.kr/learn/courses/30/lessons/138476

문제 설명

경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다.

예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소일 때입니다.

경화가 한 상자에 담으려는 귤의 개수 k와 귤의 크기를 담은 배열 tangerine이 매개변수로 주어집니다. 경화가 귤 k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 1 ≤ k ≤ tangerine의 길이 ≤ 100,000
• 1 ≤ tangerine의 원소 ≤ 10,000,000

입출력 예

k tangerine result

입출력 예 설명

입출력 예 #1

• 본문에서 설명한 예시입니다.

입출력 예 #2

• 경화는 크기가 2인 귤 2개와 3인 귤 2개 또는 2인 귤 2개와 5인 귤 2개 또는 3인 귤 2개와 5인 귤 2개로 귤을 판매할 수 있습니다. 이때의 크기 종류는 2가지로 이 값이 최소가 됩니다.

입출력 예 #3

• 경화는 크기가 1인 귤 2개를 판매하거나 2인 귤 2개를 판매할 수 있습니다. 이때의 크기 종류는 1가지로, 이 값이 최소가 됩니다.

import java.util.*;

public class Solution {
    public int solution(int k, int[] tangerine) {
        // Count the frequency of each tangerine size
        Map<Integer, Integer> count = new HashMap<>();
        for (int size : tangerine) {
            count.put(size, count.getOrDefault(size, 0) + 1);
        }

        List<Integer> sizes = new ArrayList<>(count.keySet());
        Collections.sort(sizes, (a, b) -> count.get(b) - count.get(a));

        int chosen = 0;
        int types = 0;
        for (int size : sizes) {
            int freq = count.get(size);
            if (chosen + freq <= k) {
                chosen += freq;
                types++;
            } else {
                types++;
                break;
            }
        }

        return types;
    }
}

테스트 1
입력값 〉	6, [1, 3, 2, 5, 4, 5, 2, 3]
기댓값 〉	3
실행 결과 〉	실행한 결괏값 4이 기댓값 3과 다릅니다.
테스트 2
입력값 〉	4, [1, 3, 2, 5, 4, 5, 2, 3]
기댓값 〉	2
실행 결과 〉	실행한 결괏값 3이 기댓값 2과 다릅니다.
테스트 3
입력값 〉	2, [1, 1, 1, 1, 2, 2, 2, 3]
기댓값 〉	1
실행 결과 〉	테스트를 통과하였습니다.

고유한 종류의 최솟값을 구하는 것이 아니라 귤 'k'개를 고를 때 크기가 서로 다른 종류의 수의 최솟값을 구해야하기 때문에 틀린거 같다.

2차

import java.util.*;

public class Solution {
    public int solution(int k, int[] tangerine) {
        Arrays.sort(tangerine);
        Map<Integer, Integer> freqMap = new HashMap<>();
        int distinct = 0, minDistinct = Integer.MAX_VALUE;
        
        for (int i = 0, j = 0; i < tangerine.length; i++) {
            freqMap.put(tangerine[i], freqMap.getOrDefault(tangerine[i], 0) + 1);
            if (freqMap.get(tangerine[i]) == 1) distinct++;
                       while (i - j + 1 > k) {
                freqMap.put(tangerine[j], freqMap.get(tangerine[j]) - 1);
                if (freqMap.get(tangerine[j]) == 0) distinct--;
                j++;
            }
            
            if (i - j + 1 == k) minDistinct = Math.min(minDistinct, distinct);
        }
        
        return minDistinct;
    }
}

테스트 1
입력값 〉	6, [1, 3, 2, 5, 4, 5, 2, 3]
기댓값 〉	3
실행 결과 〉	실행한 결괏값 4이 기댓값 3과 다릅니다.
테스트 2
입력값 〉	4, [1, 3, 2, 5, 4, 5, 2, 3]
기댓값 〉	2
실행 결과 〉	테스트를 통과하였습니다.
테스트 3
입력값 〉	2, [1, 1, 1, 1, 2, 2, 2, 3]
기댓값 〉	1
실행 결과 〉	테스트를 통과하였습니다.

테스트 1을 통과하지 못하였다면, 입력 값이 윈도우 크기와 동일한 경우에 대한 처리가 잘못되었을 가능성이 있다.

문제부터 다시 파악하기!!

개의 귤 중에서 크기가 서로 다른 종류의 수가 최소가 되는 경우를 찾는 것!! 이를 위해선 우선 귤의 크기를 기록하고, 가장 많이 등장하는 귤의 크기부터 k개를 선택하면 된다. 우선순위 큐를 활용하면 효율적으로 해결할 수 있다. 우선순위 큐는 빈도수에 따라 귤의 크기를 정렬하며, 가장 많이 등장하는 귤의 크기부터 선택한다.

package LV2;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class H138476 {
    public int solution(int k, int[] tangerines) {
        // HashMap을 사용하여 각 귤의 크기와 그 개수를 저장
        Map<Integer, Integer> map = new HashMap<>();
        for (int tangerine : tangerines) {
            map.put(tangerine, map.getOrDefault(tangerine, 0) + 1);
        }

        // 우선순위 큐를 사용하여 빈도수가 많은 귤의 크기를 우선적으로 꺼낼 수 있도록 한다.
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> o2[1] - o1[1]);
        for (int key : map.keySet()) {
            queue.add(new int[]{key, map.get(key)});
        }

        // count는 서로 다른 크기의 귤의 종류 수를 나타낸다.
        int count = 0;
        while (k > 0) {
            // 우선순위 큐에서 가장 빈도수가 높은 귤의 크기를 꺼낸다.
            int[] curr = queue.poll();
            if (curr[1] <= k) {
                // 현재 꺼낸 귤의 크기의 개수가 k보다 작거나 같다면, 모두 선택할 수 있으므로
                // k에서 그 개수를 빼주고, 선택한 귤의 크기의 종류 수를 1 늘린다.
                k -= curr[1];
                count++;
            } else {
                // 현재 꺼낸 귤의 크기의 개수가 k보다 크다면, 남은 귤을 모두 같은 크기로 선택할 수 있으므로
                // 현재까지 선택한 귤의 크기의 종류 수에 1을 더해서 반환한다.
                return count + 1;
            }
        }

        // k개의 귤을 모두 선택했다면, 현재까지 선택한 귤의 크기의 종류 수를 그대로 반환
        return count;
    }
}

먼저 모든 귤의 크기를 Map에 기록한다. 그런 다음, 우선순위 큐를 사용하여 가장 많이 등장하는 귤의 크기부터 선택하며, k개의 귤을 선택할 때까지 큐에서 귤의 크기를 꺼내서 k에서 빼준다. 만약 현재 꺼낸 귤의 크기의 개수가 k보다 크다면, 남은 귤을 모두 같은 크기로 선택할 수 있으므로, 현재까지 선택한 귤의 크기의 종류 수에 1을 더해서 반환한다. k개의 귤을 모두 선택했다면, 현재까지 선택한 귤의 크기의 종류 수를 그대로 반환

그전에 못푼 문제 풀었는데.. 오늘 일찍 일어났길래.. 문제를 푸는데..... 왜 오래걸렸을까요.. 나름 빨리 풀 수 있겠다는 생각으로 했는데,,, 결국 러닝을 못 갔습니다 ㅠㅠㅠ

문제 설명

각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다.

• 빛이 "S"가 써진 칸에 도달한 경우, 직진합니다.
• 빛이 "L"이 써진 칸에 도달한 경우, 좌회전을 합니다.
• 빛이 "R"이 써진 칸에 도달한 경우, 우회전을 합니다.
• 빛이 격자의 끝을 넘어갈 경우, 반대쪽 끝으로 다시 돌아옵니다. 예를 들어, 빛이 1행에서 행이 줄어드는 방향으로 이동할 경우, 같은 열의 반대쪽 끝 행으로 다시 돌아옵니다.

당신은 이 격자 내에서 빛이 이동할 수 있는 경로 사이클이 몇 개 있고, 각 사이클의 길이가 얼마인지 알고 싶습니다. 경로 사이클이란, 빛이 이동하는 순환 경로를 의미합니다.

예를 들어, 다음 그림은 격자 ["SL","LR"]에서 1행 1열에서 2행 1열 방향으로 빛을 쏠 경우, 해당 빛이 이동하는 경로 사이클을 표현한 것입니다.

!https://grepp-programmers.s3.ap-northeast-2.amazonaws.com/files/production/f3c02c50-f82e-45d0-b633-ad3ecadba316/ex1.png

이 격자에는 길이가 16인 사이클 1개가 있으며, 다른 사이클은 존재하지 않습니다.

격자의 정보를 나타내는 1차원 문자열 배열 grid가 매개변수로 주어집니다. 주어진 격자를 통해 만들어지는 빛의 경로 사이클의 모든 길이들을 배열에 담아 오름차순으로 정렬하여 return 하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ grid의 길이 ≤ 500
  • 1 ≤ grid의 각 문자열의 길이 ≤ 500
  • grid의 모든 문자열의 길이는 서로 같습니다.
  • grid의 모든 문자열은 'L', 'R', 'S'로 이루어져 있습니다.

입출력 예

grid result

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.
• 길이가 16인 사이클이 하나 존재하므로(다른 사이클은 없습니다.), [16]을 return 해야 합니다.

입출력 예 #2

• 주어진 격자를 통해 만들 수 있는 사이클들은 다음 그림과 같습니다.

!https://grepp-programmers.s3.ap-northeast-2.amazonaws.com/files/production/88a2717d-14ab-4297-af06-00baab718080/ex2.png

• 4개의 사이클의 길이가 모두 1이므로, [1,1,1,1]을 return 해야 합니다.

입출력 예 #3

• 주어진 격자를 통해 만들 수 있는 사이클들은 다음 그림과 같습니다.

!https://grepp-programmers.s3.ap-northeast-2.amazonaws.com/files/production/076dbe07-2b33-414e-b6db-1e73ae2055f3/ex3.png

• 2개의 사이클의 길이가 모두 4이므로, [4,4]를 return 해야 합니다.

package LV2;

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

public class H86052 {
	int[] dr = {-1, 0, 1, 0}; // up, right, down, left
	int[] dc = {0, 1, 0, -1}; // up, right, down, left
	int[][][] visited; // grid 상태를 기록하는 배열
	int[][][] moveCount; // 각 점에서의 이동 수를 저장하는 배열
	String[] grid;
	int n, m;

	public int[] solution(String[] grid) {
		this.grid = grid;
		n = grid.length;
		m = grid[0].length();
		visited = new int[n][m][4];
		moveCount = new int[n][m][4];
		List<Integer> cycles = new ArrayList<>();

		int count = 0;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				for (int k = 0; k < 4; k++)
					if (visited[i][j][k] == 0)
						DFS(i, j, k, ++count, 1, cycles);

		Collections.sort(cycles);
		return cycles.stream().mapToInt(i -> i).toArray();
	}

	private void DFS(int row, int col, int dir, int count, int moves, List<Integer> cycles) {
		if (visited[row][col][dir] != 0) {
			if (visited[row][col][dir] == count)
				cycles.add(moves - moveCount[row][col][dir]);
			return;
		}

		visited[row][col][dir] = count;
		moveCount[row][col][dir] = moves;

		if (grid[row].charAt(col) == 'L') dir = (dir + 3) % 4;
		else if (grid[row].charAt(col) == 'R') dir = (dir + 1) % 4;

		int nrow = (row + dr[dir] + n) % n;
		int ncol = (col + dc[dir] + m) % m;

		DFS(nrow, ncol, dir, count, moves + 1, cycles);
	}
}

테스트 7 번 런타임 에러

로직은 동일하지만, DFS 알고리즘을 재귀 대신 스택을 사용한 반복적인 방법으로 바꾸었다. 이렇게 함으로써 잠재적인 스택 오버플로우 문제를 피할 수 있다. 각 시작점에서 DFS를 실행하여 사이클을 찾고, 해당 사이클의 크기를 계산하여 리스트에 추가한다. 이후 리스트를 오름차순으로 정렬한 뒤, 정수 배열로 변환하여 반환

package LV2;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

public class H86052 {
	// 상, 우, 하, 좌로 움직이는데 필요한 델타값
	int[] dr = {-1, 0, 1, 0}; // 상, 우, 하, 좌
	int[] dc = {0, 1, 0, -1}; // 상, 우, 하, 좌
	// 각 위치와 방향에 대한 방문 상태를 기록하는 배열
	int[][][] visited;
	// 각 위치와 방향에서의 이동 횟수를 저장하는 배열
	int[][][] moveCount;
	// 입력으로 받은 격자
	String[] grid;
	// 격자의 행과 열의 개수
	int n, m;

	// 위치와 방향, 그리고 이동 횟수 등을 표현하는 클래스
	class Point {
		int row, col, dir, count, moves;

		Point(int row, int col, int dir, int count, int moves) {
			this.row = row;
			this.col = col;
			this.dir = dir;
			this.count = count;
			this.moves = moves;
		}
	}

	public int[] solution(String[] grid) {
		this.grid = grid;
		n = grid.length;
		m = grid[0].length();
		visited = new int[n][m][4];
		moveCount = new int[n][m][4];
		List<Integer> cycles = new ArrayList<>();

		int count = 0;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				for (int k = 0; k < 4; k++)
					// 만약 방문하지 않은 위치라면, DFS를 시작한다.
					if (visited[i][j][k] == 0) {
						Stack<Point> stack = new Stack<>();
						// 시작 위치를 스택에 넣는다.
						stack.push(new Point(i, j, k, ++count, 1));
						while (!stack.isEmpty()) {
							Point p = stack.pop();

							// 이미 방문한 위치라면, 사이클을 확인한다.
							if (visited[p.row][p.col][p.dir] != 0) {
								// 사이클이라면, 사이클의 길이를 저장한다.
								if (visited[p.row][p.col][p.dir] == p.count)
									cycles.add(p.moves - moveCount[p.row][p.col][p.dir]);
								continue;
							}

							// 방문하지 않았다면, 방문 표시를 하고 이동 횟수를 기록한다.
							visited[p.row][p.col][p.dir] = p.count;
							moveCount[p.row][p.col][p.dir] = p.moves;

							// 해당 위치가 L이나 R이라면, 방향을 바꾼다.
							if (grid[p.row].charAt(p.col) == 'L') p.dir = (p.dir + 3) % 4;
							else if (grid[p.row].charAt(p.col) == 'R') p.dir = (p.dir + 1) % 4;

							// 다음 위치를 계산하고, 범위를 벗어나지 않도록 조정한다.
							int nrow = (p.row + dr[p.dir] + n) % n;
							int ncol = (p.col + dc[p.dir] + m) % m;

							// 다음 위치를 스택에 넣는다.
							stack.push(new Point(nrow, ncol, p.dir, p.count, p.moves + 1));
						}
					}

		// 사이클의 길이를 오름차순으로 정렬한다.
		Collections.sort(cycles);
		// 리스트를 정수 배열로 변환하여 반환한다.
		return cycles.stream().mapToInt(i -> i).toArray();
	}
}

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.

전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
  • 각 전화번호의 길이는 1 이상 20 이하입니다.
  • 같은 전화번호가 중복해서 들어있지 않습니다.

입출력 예제

phone_book return

입출력 예 설명

입출력 예 #1

앞에서 설명한 예와 같습니다.

입출력 예 #2

한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3

첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

https://school.programmers.co.kr/learn/courses/30/lessons/42577

해시맵을 사용

각 전화번호를 해시맵에 추가하기 전에 그 전화번호가 다른 번호의 접두사인지 확인

package LV2;

import java.util.HashMap;

public class H42577 {
    public boolean solution(String[] phone_book) {
        boolean answer = true;  // 결과를 저장할 변수 초기화
        HashMap<String, Integer> map = new HashMap<>();  // 전화번호를 저장할 해시맵 초기화

        // 전화번호들을 해시맵에 저장. 전화번호는 key로, 해당 인덱스는 value로 사용
        for(int i = 0; i < phone_book.length; i++){
            map.put(phone_book[i], i);
        }

        // phone_book 배열을 다시 반복하면서 각 전화번호의 접두사를 확인
        for(int i = 0; i < phone_book.length; i++) {
            // 각 전화번호의 접두사를 생성
            for(int j = 1; j < phone_book[i].length(); j++) {
                // 생성한 접두사가 해시맵에 있는지 확인
                if(map.containsKey(phone_book[i].substring(0, j))) {
                    // 만약 접두사가 해시맵에 있다면, 해당 접두사는 다른 전화번호의 접두사이므로 결과를 false로 설정하고 반환
                    answer = false;
                    return answer;
                }
            }
        }
        // 모든 전화번호를 확인한 후에도 접두사가 없다면, 결과는 true
        return answer;
    }
}

1. 주어진 phone_book 배열의 모든 전화번호를 해시맵에 추가한다. 이때 전화번호가 key로 사용되고 해당 인덱스가 value로 사용된다.
2. 그 다음, phone_book 배열을 다시 반복하면서 각 전화번호의 부분 문자열을 생성한다. 이 부분 문자열은 각 전화번호의 접두사를 나타낸다.
3. 각 접두사에 대해, 그 접두사가 해시맵에 있는지 확인한다. 만약 해시맵에 접두사가 존재한다면, 그 접두사는 다른 전화번호의 접두사이므로 false를 반환한다.
4. phone_book의 모든 전화번호에 대해 위의 과정을 반복한 후에도 접두사가 발견되지 않으면, true를 반환한다.