알고리즘

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

문제 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개의 코스 요리중 가장 많이 주문한 경우와 같이 각 코스종류마다 답을 구하도록 수정했다. 풀이를 보고나서 다시 문제를 보니, 이 부분..

[프로그래머스] PCCP 기출문제 4번 / 수레 움직이기 자바 풀이

문제 https://school.programmers.co.kr/learn/courses/30/lessons/250134?language=java 풀이 처음 실패한 풀이 빨간 수레와 파란 수레를 각각 다르게 DFS를 수행하고 이동 여부를 체크하여 따로 수레를 이동시키게끔 구현 했으나, 턴 카운팅 하는 과정에서 어려움을 느껴 포기했다. 이후 다른 풀이를 보고, 빨간 수레와 파란 수레 각각 4개의 경우로 이동 시키므로 4X4개의 경우로 한번에 이동시키게끔 하는 풀이로 수정 했다. 또한, 각각의 수레마다 이동한 위치로 다시 돌아갈 수 없으며, 서로 이동한 위치로는 이동이 가능하다. 따라서 이를 위해 각각 visited 배열을 활용했다. 코드 class Solution { static int EMPTY_SPAC..

[백준] 1091 카드 섞기 자바 풀이

문제 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 2792 1210 897 47.335% 문제 지민이는 카지노의 딜러이고, 지금 3명의 플레이어(0, 1, 2)가 있다. 이 게임은 N개의 카드를 이용한다. (0 ~ N-1번) 일단 지민이는 카드를 몇 번 섞은 다음에, 그것을 플레이어들에게 나누어 준다. 0번째 위치에 있던 카드가 플레이어 0에게 가고, 1번째 위치에 있던 카드는 플레이어 1에게 가고, 2번째 위치에 있던 카드는 플레이어 2에게 가고, 3번째 위치에 있던 카드는 플레이어 0에게 가고, 이런식으로 카드를 나누어 준다. 하지만, 지민이는 약간 사기를 치려고 한다. 지민이는 처음에 카드를 섞기 전에 카드의 순서를 알고 있고, 이 정보를 이용해 각 카드가 특정한 플레..

[백준] 1360번 되돌리기 자바 풀이

문제 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 1515 457 365 33.610% 문제 민식이는 다음과 같이 두 개의 명령만 지원하는 새로운 텍스트 에디터를 만들었다. “type c" : 현재 글의 가장 뒤에 문자 c를 추가한다. “undo t" : 이전 t초동안 수행된 작업을 역순으로 되돌린다. 처음 텍스트 에디터는 비어있다. 예를 들어, 다음과 같은 명령을 진행했다고 하자. 1초 : type a 2초 : type b 3초 : type c 5초 : undo 3 3초가 끝날 때, 텍스트는 "abc"이다. 5초때, 이전 3초동안 한 작업을 역순으로 되돌려야 한다. c는 지워지고, b도 지워질 것이다. 따라서 a만 남는다. 되돌리기가 되돌리기 될 수도 있다. 예를 들어 1..

[백준] 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로 표시된 모든 치즈 격자는 한 시간 후에 사라진다. 와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것..