Java
-
[프로그래머스]자물쇠와 열쇠 - JAVA문제풀이/프로그래머스 2021. 2. 23. 15:39
[프로그래머스]자물쇠와 열쇠 programmers.co.kr/learn/courses/30/lessons/60059 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 풀이 특별한 알고리즘을 사용하지않는 구현, 시뮬레이션 문제이다. 그러나 어떻게 풀어야 할지 아이디어를 생각해 내기 어려웠던 문제라고 생각이 든다. 문제를 푸는 핵심 아이디어는 아래 와 같다. 1. lock를 확장한다. 2. key를 회전한다. 3. key가 lock에 맞는지 확인힌다. 하나씩 차근차근 살펴보쟝. 1. lock를 확장한다. 확장하는 이유는 키의 일부가 자물쇠의 영역을 벗어나도 키로 ..
-
[백준]2573: 빙산 - JAVA문제풀이/백준 2021. 2. 22. 16:34
[백준]2573: 빙산 www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 풀이 탐색을 하면서 빙산의 개수를 세고, 탐색을 하면서 빙하를 녹이는 문제이다. 빙산의 개수가 2개 이상이되는 순간 탐색을 멈추고 그 때의 year값을 반환한다. 빙산의 개수가 0이되버리면 2개 이상이 될 수 없으므로 0을 반환한다. 빙하가 녹을때 주의해야 할 점이 있다. 아래와 같은 경우이다. 0 0 0 0 2 -> 0 5 0 0 0 이때 가운데 칸의 빙하가 녹고 나면 2에서 0으..
-
[프로그래머스]디스크 컨트롤러 - JAVA문제풀이/프로그래머스 2021. 2. 22. 14:31
[프로그래머스]디스크 컨트롤러 programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr 풀이 이 문제의 개념은 CPU스케줄링의 비전섬 기법중 SJH스케줄링 기법이랑 완전히 동일하다. ReadyQueue에 있는 작업 중에 실행시간이 짧은 작업에게 먼저 CPU를 할당한다. ReadyQueue는 우선순위 큐를 사용하여 실행시간이 짧은 순서대로 정렬되게 해주었고, 기존의 jobs는 시작시간 순서대로 정렬해 주었다. 반복문을 사용하여 ..
-
[백준]14502: 연구소 - JAVA문제풀이/백준 2021. 2. 21. 17:41
[백준]14502: 연구소 www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 조합 + 탐색문제이다. 조합을 사용하는 이유는 벽의 위치를 뽑을 때 순서가 상관없기 때문에 조합을 사용했다. 조합을 구현할 때 다음에 뽑을 벽의 위치를 부분이 까다로웠다. 이전의 뽑은 벽의 위치보다 이후의 위치에서 벽을 선택해야 했는데 입력받은 node는 이차원 배열로 되어있어 y값을 어떻게 처리해야 할지 고민이 되었다. 처음에는 다음과 같이 구현하였다. for(int i = x; i < n..
-
[백준]1937: 욕심쟁이 판다 -JAVA문제풀이/백준 2021. 2. 21. 15:02
[백준]1937: 욕심쟁이 판다 www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 풀이 처음에는 DFS만 사용해서 풀었더니 시간초과가 났다! DP와 DFS를사용해 메모이제이션 하면서 풀어야 한다. dp에 저장되는 값은 다른 위치에서 현재 위치까지 이동할 수 있는 거리 중 최대값을 의미한다. 그러므로 이동하면서 계속 갱신해 주어야 한다. 즉 현재위치가 x, y이고 이동할 위치가 nx, ny라고 할 때 dp[x][y] = dp[nx][ny] + 1과 dp..
-
[프로그래머스]징검다리 건너기 - JAVA문제풀이/프로그래머스 2021. 2. 21. 13:41
[프로그래머스]징검다리 건너기 programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 풀이 이분탐색 문제이다! 이분탐색을 하지 않고 풀면 시간초과가 날 것이다! 전형적인 이분탐색의 유형으로 최소값, 최대값을 건널 수 있는 프렌즈의 수 범위로 둔다. 처음에는 min을 0, max를 건널 수 있는 프렌즈의 최대값으로 둔 다음, mid이상의 프렌즈가 건널 수 있다면 min을 mid + 1로, mid이상의 프렌즈가 건널 수 없다면 max를 mid - 1로 변경하여 또 탐색한다. 이때 건널 수 있는지 없는지 판단하는 방법은 간단하다. stones의 각 ..
-
[백준]5052: 전화번호 목록 - JAVA문제풀이/백준 2021. 2. 20. 17:18
[백준]5052: 전화번호 목록 www.acmicpc.net/problem/5052 풀이 이 문제는 문자열 관련한 새로운 지식을 많이 쌓을 수 있었던 문제였다. 우선, 숫자를 String으로 입력받고 Arrays.sort()를 사용해 정렬을 하면 기존의 숫자 정렬과는 결과가 다르다. 기존의 숫자 정렬은 1, 9, 10, 44, 34, 4로 입력되었을때 정렬 결과가 1, 4, 9, 10, 34, 44가 된다. 그러나 이를 String으로 입력하고 정렬하면 결과가 1, 10, 34, 4, 44이 된다. 그 이유는 프로그램은 숫자가 아닌 문자로 인식해서 오름차순 정렬을 하기 때문이다. ( ex) 다 가나 다라 나 가 -> 가 가나 나 다 다라 순서로 정렬되듯이.) 이해가 잘 되는 예시는 다음과 같다. 입력) ..
-
[프로그래머스]등굣길 - JAVA문제풀이/프로그래머스 2021. 2. 20. 14:42
[프로그래머스]등굣길 programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 풀이 문제 설명이 조금 이상하긴 한데 그림을 보면 m이 세로 행의 개수이고, n이 가로 열의 개수이다. 그러므로 board를 만들때 boar[n][m]으로 만들어 주었다. 이에 따라 puddles의 위치 좌표도 [y, x]좌표로 입력이 되어있다고 생각했다. 그런데 또 문제 설명에서 오른쪽 아래 학교의 좌표는 m, n이라고 한다. 배열로 생각하고..