원 투 쓰리 포 버블버블

Java/코딩테스트

• 백준 9205 - Java

  Java/코딩테스트 2023. 6. 29. 13:31

  https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 집 - 편의점들 - 페스티벌 장소 이렇게 각각의 장소를 posInfo에 저장. 50m에 맥주 하나씩 먹으므로 맨허튼 거리로 계산했을 때 1000까지가 최대 움직일 수 있는 거리이다. 움직일 수 있는 반경에 있는 장소들을 선으로 연결해서 그래프를 만들고, 그 그래프를 탐색했을 때 페스티벌 장소에 도착할 수 있는지에 따라 결과를 출력하면 된다. DFS 한번 쭉 돈다음에 도착지점을 방문했는지 여부..

  Read More
• 프로그래머스 도둑질 - Java

  Java/코딩테스트 2023. 5. 26. 19:41

  https://school.programmers.co.kr/learn/courses/30/lessons/42897 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 로직 집이 원형으로 배치되어 있다는 것이 이 문제의 함정이다. 첫 번째 집에서 훔쳤는지 안 훔쳤는지 따라 마지막 집을 훔칠 수 있는 여부가 달라지기 때문이다. 그래서 첫 번째 집 턴 경우 / 안 턴 경우 2가지 모두 DP돌리고, 그 두가지 중 max 값 찾는 것으로 로직을 짠다. 점화식 DP[i] -> i번째 집까지 방문했을 때 얻을 수 있는 최대 금액 1) 첫 번째 집을 고른 경우에는 DP[0]..

  Read More
• 백준 7569, 2573 - Java

  Java/코딩테스트 2023. 5. 26. 17:18

  백준 7569 토마토 - 기존 BFS 방식에서 z축이 새로 생겼다고 보면 된다. 3차원 배열에 토마토 저장, 원래 BFS쓸 때 정의하는 x,y축 이동방향에 추가로 z축 이동방향(위 아래) 까지 정의해준다. - 남은 안익은 토마토 개수 left 정의해주기. 처음부터 left가 0일 수도 있다. bfs 들어가기전에 이거 먼저 걸러내기 - 익은 토마토 위치들부터 큐에 넣어준다. - 따로 방문배열 만들지 않고 3차원 배열에 저장된 값이 0이면 아직 안 방문한 안익은 토마토라는 뜻이므로 이때만 큐에 넣어준다. 3차원 배열에 익은 시점을 저장하며 업데이트 - 큐를 다 돌았는데도 안 익은게 남았다면 -1, 다 익었다면 3차원 배열을 탐색하여 max값 찾은 후 -1을 해서 정답 출력. (1초부터 시작했기 때문에!) i..

  Read More
• [ SWEA ] 1954

  Java/코딩테스트 2023. 5. 19. 18:19

  달팽이 숫자 문제 한 방향으로 쭉 -> 가고 더이상 못가면 방향을 전환하는 방법으로 푼다. isValid() 함수로 검사 + 해당 칸의 값이 0인지 확인 -> 아닐 경우 방향을 전환 이 때 isValid로 먼저 검사해야한다. map[x+dirX[dir]][y+dirY[dir]]를 먼저 조건의 앞에 넣어두면 벽 벗어나는 칸일 경우 바로 ArrayOutOfBound 뜨기 때문. 각 칸에는 1~n*n의 숫자를 채워넣기. import java.util.*; public class Solution { static int[] dirX = { 0, 1, 0, -1 }; static int[] dirY = { 1, 0, -1, 0 }; public static void main(String[] args) { Scann..

  Read More
• [ SWEA ] 1204, 1206, 9611

  Java/코딩테스트 2023. 5. 17. 17:14

  1204 : 1000명의 학생들의 점수를 보고 가장 많이 등장한 점수 꺼내기 -> HashMap 사용해서 풀었다. 학생의 점수 + 빈도 수를 key, value 값으로 넣어두기 / map은 같은 key값이 들어오면 나중에 들어온 value로 덮어씌운다. 기존에 있던 빈도 수 scores.get() + 1해서 빈도수 + 1 이때 Map을 정렬해야 하는데, 문제 조건은 2가지가 있다. 1. 가장 많이 등장한 점수 2. 빈도수가 같은 점수가 있을 경우, 더 높은쪽을 선택. Map 자료구조에서 map.entrySet() : map의 모든 Key, Value 꺼낸다. ArrayList로 꺼내도 되고 LinkedList로 꺼내도 된다. 돌려보니 ArrayList가 메모리를 더 쓰고 시간을 덜 쓰는 것 같다. Lin..

  Read More
• HackerRank - PriorityQueue

  Java/코딩테스트 2023. 5. 11. 17:00

  https://www.hackerrank.com/challenges/java-priority-queue/problem?isFullScreen=true Java Priority Queue | HackerRank Leran about Priority Queues in Java www.hackerrank.com 해당 문제에서는 Student 클래스를 PriorityQueue에 넣기 위해 Student 클래스에서 compareTo(Student o)를 구현하는 것이 관건이었던것 같다. cgpa(내림차순) -> name(알파벳 순) -> id(오름차순) 순으로 정렬하기. - cgpa 가 double 형이므로 리턴시 ?연산자로 정수 리턴해주기. 내림차순이므로 o.cgpa - this.cgpa > 0 ? 1 : -1..

  Read More
• 프로그래머스 여행경로 Java

  Java/코딩테스트 2023. 5. 4. 17:04

  🍭 필요한 로직 모든 티켓을 다 사용해야 한다 -> DFS 갈 수 있는 경로가 여러가지라면 알파벳 순으로 -> 우선순위 큐에 넣기(자동으로 정렬이 된다) / 백트래킹으로 가능한 경우의 수 탐색 티켓을 다 사용했다면 경로를 기록하기 -> 문자열 형태로 경로 저장해놨다가 꺼내는 방식을 씀 -> String path에 공백 간격을 두고 저장, 나중에 queue.poll().split(" ")로 answer 배열에 저장하면 된다. -> 우선순위 큐에서 알아서 알파벳 순서가 가장 빠른걸로 정렬해준다 🍭코드 import java.util.*; class Solution { public PriorityQueue queue; public boolean[] visited; public String[] solution(S..

  Read More
• 프로그래머스 디스크 컨트롤러 - Java (feat 우선순위 큐)

  Java/코딩테스트 2023. 4. 27. 02:41

  정리하는 김에 조금씩 공부했던 문제들 정리... 🐟우선순위 큐 - 단순 먼저들어오는 애가 먼저 나가는게 아님. 우선순위따라 자동 정렬된다. - 디폴트는 오름차순 정렬 - 정렬 기준을 커스텀 만약 아래 처럼 입력이 들어온다고 하자. queue.add(new Node("나몰빼미", 6)); queue.add(new Node("염버니", 8)); queue.add(new Node("팽도리", 4)); queue.add(new Node("피카츄", 1)); 결과는 이렇게 내림차순으로 출력하고 싶다 염버니 8 나몰빼미 6 팽도리 4 피카츄 1 방법 1 PriorityQueue queue = new PriorityQueue((Node O1, Node O2) -> O2.size - O1.size); 방법 2 (자체 ..

  Read More