알고리즘

[프로그래머스] 베스트 앨범 자바 풀이

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42579?language=java 풀이 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. • 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다. 이 조건들을 위주로 생각하여 문제를 풀었다. 우선, 장르, 재생횟수, 인덱스를 저장하기 위해 Triple이라는 자료구조를 하나 만들어줬다. 또한, 장르별 재생횟수를 저장하기 위해 Pair 자료구조와 함께 HashMap을 사용했다. Triple 자료구조를 저장하는 list에 모든 데이터를 담고, 이 후 재생횟수 순서대..

[프로그래머스] 게임 맵 최단거리 자바 풀이

문제 https://school.programmers.co.kr/learn/courses/30/lessons/1844?language=java 풀이 틀린 풀이 DFS를 통해 문제를 먼저 풀었지만 효율성 테스트에서 모두 실패했다. 새로운 풀이 문제점 DFS는 다음과 같은 문제가 있기 때문에 이 문제를 해결하는 방법으로 적합하지 않다. 해가 없는 경로가 깊을 경우 탐색시간이 오래 걸릴 수 있다. 얻어진 해가 최단 경로가 된다는 보장이 없다. 따라서, BFS로 다시 문제를 풀었다. 또한 맨날 헷갈리는 부분이 다익스트라(PQ)를 사용할 것인지 인데, PQ의 경우 가중치가 다른 경우에 사용한다는 것을 다시 기억하자. 일반적인 방법의 BFS를 통해 문제를 해결할 수 있다. 코드 package com.company...

[프로그래머스] 메뉴 리뉴얼 자바 풀이

문제 https://school.programmers.co.kr/learn/courses/30/lessons/72411?language=java 풀이 소요시간 60분 틀린 풀이 조합을 통해 가능한 전체 코스의 경우의 수를 구하고, 코스가 등장한 갯수를 구하기 위해 map을 이용했다. 이후 map에서 2개 이상 등장 했으며, 코스의 길이가 orders 배열에 포함된 경우 추가하도록 했다. 문제점 코스에 만약 ABCD가 있다면, BCD, CD 와같이 ABCD 내에 포함된 경우를 제거하는 방법을 찾지 못해 풀지 못했다. 새로운 풀이 2개의 코스 요리중 가장 많이 주문한 경우, 3개의 코스 요리중 가장 많이 주문한 경우와 같이 각 코스종류마다 답을 구하도록 수정했다. 풀이를 보고나서 다시 문제를 보니, 이 부분..

[백준] 1189번 컴백홈 자바 풀이

문제 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 7011 3924 3058 55.109% 문제 한수는 캠프를 마치고 집에 돌아가려 한다. 한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있다. 그리고 한수는 집에 돌아가는 방법이 다양하다. 단, 한수는 똑똑하여 한번 지나친 곳을 다시 방문하지는 않는다. cdef ...f ..ef ..gh cdeh cdej ...f bT.. .T.e .Td. .Tfe bTfg bTfi .Tde a... abcd abc. abcd a... a.gh abc. 거리 : 6 6 6 8 8 10 6 위 예제는 한수가 집에 돌아갈 수 있는 모든 경우를 나타낸 것이다. T로 표시된 부분은 가지 못하는 부분이다. 문제는 R x C 맵에 못가는 부분이 주..

[프로그래머스] 디스크 컨트롤러 자바 풀이

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42627 풀이 우선순위 큐를 활용하여 문제를 풀었음. (정렬이 필요하므로) 정렬 작업큐 작업큐의 경우 기본적으로 작업이 들어온 순서대로 정렬되어야 한다. 또한, 같은 시간에 작업이 들어온 경우, 작업 시간이 더 짧은 작업을 먼저 처리하는것이 효율적이다. 대기큐 작업 시간이 짧은 순서대로 정렬해주자. 작업 고르기 현재 대기중인 작업이 있는 경우 대기 큐에서 작업시간이 가장 짧은 작업을 고른다. 만약 현재 시간보다 작업 큐에서 꺼낸 작업의 시작시간이 더 크다면, 시간을 꺼낸 작업의 시작시간으로 변경해준다. (새로운 작업은 현재 시간보다 100초 이후에 시작될수도 있다.) 현재 대기중인 작업이 없는 ..

[백준] 2636번 치즈 자바 풀이

문제 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 29631 16632 11947 55.129% 문제 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다. 이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. 의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 와 같이 된다. https://..

[백준] 2638번 치즈 자바 풀이

문제 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 26868 12675 9471 46.220% 문제 N×M의 모눈종이 위에 아주 얇은 치즈가 과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다. 와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것..

[백준] 파이프 옮기기 1 자바 풀이

문제 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 (추가 시간 없음) 512 MB 39509 18717 12827 46.147% 문제 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다. 파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. ..

[프로그래머스] 단어 변환 자바 풀이

문제 문제 설명 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. 예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다. 두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 targe..

[프로그래머스] 네트워크 자바 풀이

문제 문제 설명 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 제한사항 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-1인 정수로 표현합니다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 compute..