140번 유사 칸토어 비트열
/*
문제 분석
1. 정보
- 수학에서 칸토어 집합은 0과 1 사이의 실수로 이루어진 집합으로, [0,1]부터 시작하여 각 구간을 3등분 하여 가운데 구간을 반복적으로 제외하는 방식으로 만들어짐.
- 남아는 칸토어 집합을 조금 변형하여 유사 칸토어 비트열을 만들음
- 유사 칸토어 비트열은 다음과 같이 정의됨
- 0번째 유사 칸토어 비트열은 "1"
- n번쨰 유사 칸토어 비트열은 n - 1번째 유사 칸토어 비트열에서의 1을 11011로 치환하고 0을 00000으로 치환하여 만듬
- 남아는 n번째 유사 칸토어 비트열에서 특정 구간 내의 1의 개수가 몇 개인지 궁금해짐
2. 목표
- n과 1의 개수가 몇 개인지 알고 싶은 구간을 나타내는 l, r이 주어졌을 때 그 구간 내의 1의 개수를 return
3. 제약 조건
- 1 ≤ n ≤ 20
- 1 ≤ l, r ≤ 5n
- l ≤ r < l + 10,000,000
- l과 r은 비트열에서의 인덱스(1-base)이며 폐구간 [l, r]을 나타냄.
풀이
1. 아이디어
- n번째 자리 도달할 때 까지 DFS 하기
- 해당 자리의 다음 번째 범위
- (i - 1) * 5 + 1 ~ i * 5
- 위 범위중 1,2,4,5 에만 1이 해당되므로 해당 인덱스만 다시 DFS
- 만약 해당 인덱스가 구하려는 범위 안에 있지 않으면, DFS 하지 않음
- 범위는 l / 5^(남은 깊이), r / 5^(남은 깊이) 하고, 올림 하여 사용
- 만약 해당 인덱스가 [l,r] 사이에 존재하지 않는다면
- 더 이상 깊이 들어갈 필요가 없으므로 return
- 존재한다면 깊이 + 1 로 더 들어감
- 만약 n번째에 도달하였다면
- 해당 숫자의 인덱스가 l과 r 사이에 있고 1이라면 1의 개수++
- return
*/
class Solution {
int answer = 0;
int N;
public int solution(int n, long l, long r) {
N = n;
compute(0, l, r, 1L, 1);
return answer;
}
private void compute(int n, long l, long r, long idx, int cur) {
if (n == N) {
if (l <= idx && idx <= r) {
if (cur == 1) {
answer++;
}
}
return;
}
long left = (long) Math.ceil(l / Math.pow(5, N - (n + 1)));
long right = (long) Math.ceil(r / Math.pow(5, N - (n + 1)));
for (long i = (idx - 1) * 5 + 1; i <= idx * 5; i++) {
if (i < left || right < i) {
continue;
}
if (i != idx * 5 - 2) {
compute(n + 1, l, r, i, 1);
}
}
}
}141번 당구 연습
/*
문제 분석
1. 정보
- 당구 학원에 나온 머쓱이에게 당구 선생님이 "원쿠션" 연습을 하라면서 당구공의 위치가 담긴 리스트를 건네줌.
- 리스트에는 머쓱이가 맞춰야하는 공들의 위치가 담겨 있음. 머쓱이는 리스트에 담긴 각 위치에 순서대로 공을 놓아 가며 "원쿠션" 연습을 하면 됨. 이때 머쓱이는 항상 같은 위치에 공을 놓고 쳐서 리스트에 담긴 위치에 놓인 공을 맞춤.
- 당구대의 가로 길이 m, 세로 길이 n과 머쓱이가 쳐야하는 공이 놓인 위치 좌표를 나타내는 두 정수 startX, startY, 그리고 매 회마다 목표로 해야하는 공들의 위치 좌표를 나타내는 정수 쌍들이 들어있는 2차우너 정수 배열 balls가 주어진다.
- 단 머쓱이가 친 공이 벽에 부딪힐 때 진행 방향은 항상 입사각과 반사각이 동일하며, 만약 꼭짓점에 부딪힐 경우 진입 방향의 반대방향으로 공이 진행됨.
- 공의 크기는 무시하고, 두 공의 좌표가 정확히 일치하는 경우에만 두 공이 서로 맞았다고 판단.
- 공이 목표 공에 맞기 전에 멈추는 경우는 존재하지 않고, 목표 공에 맞으면 바루 멈춘다고 가정.
2. 목표
- "원쿠션" 연습을 위해 머쓱이가 공을 적어도 벽에 한 번은 맞춘 후 목표 공에 맞힌다고 할 때, 각 회마다 머쓱이가 친 공이 굴러간 거리의 최솟값의 제곱을 배열에 담아 return
3. 제약 조건
풀이
1. 아이디어
- 해당 당구판을 기준으로 4면 + 각 대각선에 거울처럼 판을 생성한다 생각하면 됨.
- 생성하는 이유 : 최소 "원쿠션"을 해야하기 때문.
- 원쿠션을 하기 위해선, 벽을 반드시 지나가야되기 때문에, 거울처럼 생성한 반대쪽에 공을 위치시키고 해당 좌표와 공의 좌표에 대한 길이를 구하면 해당 길이가 최솟값이 됨.
- 치려는 공의 좌표를 [x,y], 이라 가정
- [x,y] 좌표를 다음과 같이 생성
- 좌측 벽 반사 : [-x,y]
- 우측 벽 반사 : [2m-x,y]
- 상단 벽 반사 : [x,2n-y]
- 하단 벽 반사 : [x,-y]
- 총 8개의 좌표를 구하고, 당구공이 놓인 위치와의 길이를 구한 뒤, 가장 최소인 길이를 저장.
- 모든 공을 위 방식으로 길이를 저장한 뒤 반환.
- 주의점
- 공의 y좌표가 같을 경우 : 좌측 벽 또는 우측 벽 반사 불가능
- 공의 x좌표가 같을 경우 : 삳단 벽 또는 하단 벽 반사 불가능
*/
class Solution {
public int[] solution(int m, int n, int startX, int startY, int[][] balls) {
int[] answer = new int[balls.length];
int idx = 0;
for (int[] ball : balls) {
int minLen = Integer.MAX_VALUE;
int hitX = ball[0];
int hitY = ball[1];
int[][] reflections = {
{-hitX, hitY},
{2 * m - hitX, hitY},
{hitX, -hitY},
{hitX, 2 * n - hitY}
};
for (int[] ref : reflections) {
int reflectX = ref[0];
int reflectY = ref[1];
if (!isBlocked(startX, startY, hitX, hitY, reflectX, reflectY)) {
int distSquared = (int) (Math.pow(startX - reflectX, 2) + Math.pow(startY - reflectY, 2));
minLen = Math.min(minLen, distSquared);
}
}
answer[idx++] = minLen;
}
return answer;
}
private boolean isBlocked(int startX, int startY, int hitX, int hitY, int reflectX, int reflectY) {
if (startX == hitX && startX == reflectX) {
return (startY < hitY && startY < reflectY) || (startY > hitY && startY > reflectY);
}
if (startY == hitY && startY == reflectY) {
return (startX < hitX && startX < reflectX) || (startX > hitX && startX > reflectX);
}
return false;
}
}142번 빛의 경로 사이클
/*
문제 분석
1. 정보
- 각 칸마다 S, L 또는 R이 써져 있는 격자가 있음. 격자에서 빛을 쏘고자 하는데, 격자의 각 칸에는 다음과 같은 특이한 성질이 존재.
- 빛이 "S"가 써진 칸에 도달한 경우, 직진
- 빛이 "L"이 써진 칸에 도달한 경우, 좌회전
- 빛이 "R"이 써진 칸에 도달한 경우, 우회전
- 빛이 격자의 끝을 넘어갈 경우, 반대쪽 끝으로 다시 돌아옴
- 빛이 1행에서 행이 줄어드는 방향으로 이동할 경우, 같은 열의 반대쪽 끝 행으로 다시 돌아옴
- 이 격자 내에서 빛이 이동할 수 있는 경로 사이클이 몇 개 있고, 각 사이클의 길이가 얼마인지 알고 싶음. 경로 사이클이란, 빛이 이동하는 순환 경로를 의미.
2. 목표
- 격자의 정보를 나타내는 1차원 문자열 배열 grid가 매개변수로 주어질 때, 주어진 격자를 통해 만들어지는 빛의 경로 사이클의 모든 길이들을 배열에 담아 오름차순으로 정렬하여 return
3. 제약 조건
- 1 ≤ grid의 길이 ≤ 500
- 1 ≤ grid의 각 문자열의 길이 ≤ 500
- grid의 모든 문자열의 길이는 서로 같음
- grid의 모든 문자열은 'L', 'R', 'S'로 이루어져 있음.
풀이
1. 아이디어
- 사이클을 완성하기 위해선, 시작점 = 도착점 뿐만 아니라, 시작점에서의 출발 방향 = 도착점 도착 이후의 출발 방향 이어야 함.
- 또한 한 빛에서 이미 존재하는 사이클을 통과할 경우, 해당 사이클은 중복이기 때문에 제외해야 함.
- 따라서 각 빛마다 [4]배열을 만들어 상, 하, 좌, 우 방향으로 빛이 통과했는지 여부를 저장하여 중복을 방지해야 할듯.
- 길이는 최대 500 * 500 이므로 250000 * 4 = 100만임
- 3중 for문을 사용하여 모든 경우의 수를 탐색
- 이미 지난(visited[][][] 가 true라면) 건너 뜀
- 지나지 않았다면, 해당 방향으로 부터 시작. (시작한 위치와 방향은 저장)
- 사이클을 돌다가 visited가 true인곳 지나면 바로 return
- 시작점과 시작 방향을 지난다면 cnt를 배열에 저장하고 return
- 모든 경우의 수를 구하였다면 answer 배열 오름차순 정렬 후 return
*/
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
List<Integer> ans = new ArrayList<>();
int x = 0;
int y = 0;
boolean[][][] visited;
// 상 우 하 좌 순서
int[] dx = {-1, 0, 1, 0};
int[] dy = {0, 1, 0, -1};
public int[] solution(String[] grid) {
x = grid.length;
y = grid[0].length();
visited = new boolean[x][y][4];
for (int i = 0; i < x; i++) {
for (int j = 0; j < y; j++) {
for (int k = 0; k < 4; k++) {
if (!visited[i][j][k]) {
compute(grid, i, j, k);
}
}
}
}
int[] answer = new int[ans.size()];
for (int i = 0; i < ans.size(); i++) {
answer[i] = ans.get(i);
}
Arrays.sort(answer);
return answer;
}
private void compute(String[] grid, int sx, int sy, int k) {
int rows = grid.length;
int cols = grid[0].length();
int x = sx;
int y = sy;
int dir = k;
int length = 0;
while (!visited[x][y][dir]) {
visited[x][y][dir] = true;
length++;
char command = grid[x].charAt(y);
if (command == 'L') {
dir = (dir + 3) % 4;
} else if (command == 'R') {
dir = (dir + 1) % 4;
}
x = (x + dx[dir] + rows) % rows;
y = (y + dy[dir] + cols) % cols;
// 시작점으로 돌아오면 사이클 완성
if (x == sx && y == sy && dir == k) {
if (length > 0) {
ans.add(length);
return;
}
}
}
}
}143번 이중우선순위큐
/*
문제 분석
1. 정보
- 이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말함.
- I 숫자 : 큐에 주어진 숫자를 삽입
- D 1 : 큐에서 최댓값을 삭제
- D -1 : 큐에서 최솟값을 삭제
2. 목표
- 이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return
3. 제약 조건
- 1 <= operations의 길이 <= 1000000
- operations의 원소는 큐가 수행할 연산을 나타냅니다.
- 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
- 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.
풀이
1. 아이디어
- minHeap과 maxHeap 두가지를 Priority Queue로 생성
- minHeap은 최솟값을 뽑을 수 있게(오름차순), maxHeap은 최댓값을 뽑을 수 있도록 설정(내림차순)
- I 명령 들어올 경우
- minHeap과 maxHeap에 해당 값을 넣음.
- D 명령 들어올 경우
- 두 큐가 다 비어있다면, 무시하고 다음 명령으로 넘어감.
- D 1 명령 들어올 경우
- maxHeap에서 poll을 하고, poll한 값을 minHeap에서도 제거
- D -1 명령 들어올 경우
- minHeap에서 poll을 하고, poll한 값을 maxHeap에서도 제거
- 모든 명령 실행 이후
- 큐가 비어있다면 [0,0] 반환
- 비어있지 않다면, minHeap에서 뽑은 값과 maxHeap에서 뽑은 값을 반환
*/
import java.util.Comparator;
import java.util.PriorityQueue;
class Solution {
public int[] solution(String[] operations) {
int[] answer = new int[2];
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
for (String operation : operations) {
String[] oper = operation.split(" ");
if (oper[0].equals("I")) {
minHeap.add(Integer.parseInt(oper[1]));
maxHeap.add(Integer.parseInt(oper[1]));
} else if (oper[0].equals("D")) {
if (minHeap.isEmpty() || maxHeap.isEmpty()) {
continue;
}
if (oper[1].equals("1")) {
int remove = maxHeap.poll();
minHeap.remove(remove);
}else{
int remove = minHeap.poll();
maxHeap.remove(remove);
}
}
}
if (minHeap.isEmpty() || maxHeap.isEmpty()) {
answer[0] = 0;
answer[1] = 0;
}else{
answer[0] = maxHeap.poll();
answer[1] = minHeap.poll();
}
return answer;
}
}144번 네트워크
/*
문제 분석
1. 정보
- 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미
- 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어 있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있음.
- 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있음.
2. 목표
- 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return
3. 제약 조건
- 1 <= n <= 200
- 각 컴퓨터는 0부터 n - 1 인 정수로 표현
- i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현
- computer[i][i]는 항상 1
풀이
1. 아이디어
- BFS를 사용하여 문제 풀이
- visited[] 를 만들어 해당 네트워크가 이미 지나갔는지 확인
- 0 ~ n - 1까지 visited하지 않았다면, 해당 네트워크에서 BFS 사용하여 연결된 모든 네트워크를 visited = true 처리함
- 해당 연결에 대한 모든 컴퓨터를 탐색했으면 answer++
- 전체를 탐색한 후 answer 를 return
*/
import java.util.LinkedList;
import java.util.Queue;
class Solution {
public int solution(int n, int[][] computers) {
int answer = 0;
boolean[] visited = new boolean[n];
for (int i = 0; i < n; i++) {
if (!visited[i]) {
Queue<Integer> q = new LinkedList<>();
q.add(i);
visited[i] = true;
while (!q.isEmpty()) {
int cur = q.poll();
for (int j = 0; j < n; j++) {
if (!visited[j] && computers[cur][j] == 1) {
q.add(j);
visited[j] = true;
}
}
}
answer++;
}
}
return answer;
}
}145번 단어 변환
/*
문제 분석
1. 정보
- 두 개의 단어 begin, target과 단어의 집합 words가 있음.
- 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 함.
- 1. 한 번에 한 개의 알파벳만 바꿀 수 있음.
- 2. words의 있는 단어로만 변환할 수 있음.
2. 목표
- 두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단개의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return
3. 제약 조건
- 각 단어는 알파벳 소문자로 이루어짐
- 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같음
- words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없음
- begin과 target은 같지 않음
- 변환할 수 없는 경우에는 0을 return
풀이
1. 아이디어
- 일단 words에 target이 들어있지 않다. -> 바로 0 return
- BFS 사용
- 시작 단어를 큐에 넣고 시작
- 큐에서 뽑고 해당 단어와 words의 단어를 비교하며 한개의 알파벳만 다른 단어들을 큐에 집어넣음. 이때, 변환 횟수도 같이 저장해야함.
- 단어 비교 방법
- 단어의 길이는 같으므로, 처음부터 끝까지 비교
- 다르다면 count + 1 해줌
- 만약 count가 1이라면 visited true 하고 큐에 저장
- target 단어와 일치한다면, 해당 변환 횟수 return
*/
import java.util.LinkedList;
import java.util.Queue;
class Solution {
class Node{
String word;
int cnt;
public Node(String word, int cnt) {
this.word = word;
this.cnt = cnt;
}
}
public int solution(String begin, String target, String[] words) {
boolean flag = false;
for (String word : words) {
if (target.equals(word)) {
flag = true;
break;
}
}
if(!flag) return 0;
boolean[] visited = new boolean[words.length];
Queue<Node> q = new LinkedList<>();
q.add(new Node(begin, 0));
while (!q.isEmpty()) {
Node cur = q.poll();
if (cur.word.equals(target)) {
return cur.cnt;
}
for (int i = 0; i < words.length; i++) {
if (!visited[i]) {
int count = 0;
for (int j = 0; j < words[i].length(); j++) {
if (cur.word.charAt(j) != words[i].charAt(j)) {
count++;
}
}
if (count == 1) {
q.add(new Node(words[i], cur.cnt + 1));
visited[i] = true;
}
}
}
}
return 0;
}
}
문제 해결을 좋아하는 개발자 입니다 :)