알고리즘
-
[프로그래머스] 호텔 방 배정 / 2019 카카오 개발자 겨울 인턴십 - JAVA알고리즘/프로그래머스 2021. 9. 4. 15:14
🖇️ 문제 링크 코딩테스트 연습 - 호텔 방 배정 "스노우타운"에서 호텔을 운영하고 있는 "스카피"는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 k개 있으며, 각각의 방은 1번부터 k번까지 번호로 구분하고 있습니다. 처음에는 모든 방이 비어 있으며 "스카피"는 다음과 같은 규칙에 따라 고객에게 방을 배정하려고 합니다. 한 번에 한 명씩 신청한 순서대로 방을 배정합니다. 고객은 투숙하기 원하는 방 번호를 제출합니다. https://programmers.co.kr/learn/courses/30/lessons/64063 📝 문제 분석 처음에는 Set에 배정이 된 방 번호를 넣어두고, 원하는 방이 Set에 없을 때까지 + 1하는 방식으로 했었는데 효율성에서 시간초과가 났다. 시간을 줄..
-
[프로그래머스] 불량 사용자 / 2019 카카오 개발자 겨울 인턴십 - JAVA알고리즘/프로그래머스 2021. 9. 4. 15:14
🖇️ 문제 링크 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 사용자라는 이름으로 목록을 만들어서 당첨 처리 시 제외하도록 이벤트 당첨자 담당자인 "프로도" 에게 전달하려고 합니다. 이 때 개인정보 보호을 위해 사용자 아이디 중 일부 문자를 '*' 문자로 가려서 전달했습니다. https://programmers.co.kr/learn/courses/30/lessons/64064 📝 문제 분석 불량 사용자 목록에 매칭되는 유저들의 조합의 개수를 찾는 문제입니다. 비트마스킹으로 조합 중복 체크를 하고, 정규식을 사용해서 유저 아이디가 패턴과 매..
-
[프로그래머스] 튜플 / 2019 카카오 개발자 겨울 인턴십 - JAVA알고리즘/프로그래머스 2021. 9. 4. 15:14
🖇️ 문제 링크 코딩테스트 연습 - 튜플 https://programmers.co.kr/learn/courses/30/lessons/64065# 📝 문제 분석 실제로 사용할 숫자만 남기기 위해 { 와 }를 제거합니다. ','를 기준으로 숫자를 나누고 숫자들의 개수가 많을 수록 튜플의 앞부분에 위치하기 때문에, 숫자 개수 내림차순으로 정렬하여 출력합니다. ⌨️ 코드 import java.util.*; class Solution { public int[] solution(String s) { Map hm = new HashMap(); s = s.replaceAll("[{]|[}]", ""); for(String str : s.split(",")) { int n = Integer.parseInt(str); h..
-
[프로그래머스] 크레인 인형뽑기 게임 / 2019 카카오 개발자 겨울 인턴십 - JAVA알고리즘/프로그래머스 2021. 9. 4. 15:14
🖇️ 문제 링크 코딩테스트 연습 - 크레인 인형뽑기 게임 게임개발자인 "죠르디"는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다. "죠르디"는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다. 게임 화면은 "1 x 1" 크기의 칸들로 이루어진 "N x N" 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 "5 x 5" 크기의 예시입니다). https://programmers.co.kr/learn/courses/30/lessons/64061 📝 문제 분석 열마다 하나씩 스택을 만들어서 인형들을 넣어주었다. 바구니가 위에서 쌓이는 구조이기 때문에 스택 자료구조를 이용했다. 바구니에 인형을 넣을 때 가장 위에 있는 인형..
-
[백준] 17953. 디저트 - Java알고리즘/백준 2021. 9. 4. 15:14
🖇️ 문제 링크 17953번: 디저트 창호는 매일 점심마다 디저트를 먹는다. 그런데 같은 디저트라도 매일 느끼는 맛이 달라진다. 어떤 날에는 마카롱을 먹고 매우 행복함을 느끼는 반면 어떤 날에는 '차라리 케이크를 먹는게 나았지 않았을까' 하는 식이다. 이럴 때 케이크를 다시 먹으면 좋겠지만, 창호는 건강을 위해 디저트는 하루에 한 가지만 먹기로 정해 놓았다. 어느 날 창호는 이런 '만족감'에 패턴이 있는 것을 알아냈다. https://www.acmicpc.net/problem/17953 💡 문제 분석 💡 dp(day, prev) = 전날에 prev번째 디저트를 먹었을 때, day일 이후 얻을 수 있는 만족도 전 날에 먹은 디저트가 무엇인가에 따라 다음날 만족도가 바뀌기 때문에, 전날 먹은 디저트를 함께 ..
-
[백준] 17471. 게리맨더링 - Java알고리즘/백준 2021. 9. 4. 15:14
🖇️ 문제 링크 17471번: 게리맨더링 문제 백준시의 시장 최백준은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 최백준은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 백준시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다. 백준시는 N개의 구역으로 나누어져 있고, 구역은 1번부터 N번까지 번호가 매겨져 있다. https://www.acmicpc.net/problem/17471 💡 문제 분석 각 구역을 두 개의 선거구로 나눕니다. 총 N개의 구역이 있다면, (1, N - 1), (2, N - 2) ... (N/ 2, N/2) 형태로 나눕니다. 두 개로 나눈 선거구가 각각 연결되어 있는지 그래프 탐색으로 확인합니다. 만약 ..
-
[백준] 17070. 파이프 옮기기 - Java알고리즘/백준 2021. 9. 4. 15:14
🖇️ 문제 링크 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. https://www.acmicpc.net/problem/17070 💡 문제 분석 💡 dfs(y, x, d) = 현재 파이프가 (y, x) 위치이고 방향이 d일 때 목표 지점에 갈 수 있는 경우의 수 파이프의 위치와 방향에 따라 경우의 수를 계산하며, 다이내믹 프로그래밍을 진행합니다. ⌨️ 코드 import java...
-
[백준] 16973. 직사각형 탈출 - Java알고리즘/백준 2021. 9. 4. 15:14
🖇️ 문제 링크 16973번: 직사각형 탈출 https://www.acmicpc.net/problem/16973 💡 문제 분석 직사각형의 가장 왼쪽 위칸(Sr, Sc)를 기준으로 4방향으로 BFS를 진행합니다. 4방향을 탐색할 때, H * W 크기의 직사각형 중 한칸이라도 벽에 부딪힌다면 continue. (Fr, Fc) 좌표를 찾아낸다면 종료합니다. ⌨️ 코드 import java.io.*; import java.util.*; public class Q16973 { static int N, M, H, W, sy, sx, fy, fx; static int[][] map, dist; static int[] dy = {-1, 0, 1, 0}, dx = {0, 1, 0, -1}; public static vo..