백준

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

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

[백준] 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가지 방향이 가능하다. 파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. ..

[백준] 1976번 여행 계획 자바 풀이

문제 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 42619 16415 12036 37.043% 문제 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다. 도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 ..

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

문제 문제 설명 두 개의 단어 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..

[프로그래머스] 이중우선순위큐 자바 풀이

문제 문제 설명 이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다. 명령어 수신 탑(높이) I 숫자 큐에 주어진 숫자를 삽입합니다. D 1 큐에서 최댓값을 삭제합니다. D -1 큐에서 최솟값을 삭제합니다. 이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요. 제한사항 operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다. operations의 원소는 큐가 수행할 연산을 나타냅니다. 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만..