본문 바로가기

Tech/Problem Solving

[프로그래머스] 2022 KAKAO TECH INTERNSHIP - 두 큐 합 같게 만들기 (Java) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 큐를 이동시키기 전에 두 큐의 전체 합이 홀수이면 바로 -1을 리턴할 수 있다. 큐는 2개이지만 하나의 큐의 총합 == 전체 합 / 2 라면 원하는 값을 찾아낼 수 있기 때문에 한 개의 큐 값만 추적하면 된다. 한 가지 주의할 점이 있다면 원소를 몇 번까지 옮겨야 할 것인지에 대한 것이다. 일정 횟수를 초과하면 결국에는 반복이기 때문에 반복이 되기 전 탐색을 끊어내야 한다. 그 일정 횟수는 몇 번이어야 하는가? 1번 테스트 케이스의 실패 원인을 찾던 중 (큐의 크기) * 2 + 3 로 통과하긴 했지만, ..
[백준] 12919번 - A와 B 2 (Java) 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 풀이 S와 T의 길이가 같아질 때까지 두 연산 중 하나를 수행해보고 같은 값이 되는 경우의 수가 있는지 확인한다. 브루트포스 문제로 dfs 형태로 구현하였다. 주의할 점. S의 길이를 늘리는 방식으로 하면 시간 초과가 발생한다. T의 길이를 S만큼 줄이는 방식으로 수행해야 한다. 코드 import java.util.Scanner; public class Main { public static void main(String[]..
[프로그래머스] 2024 KAKAO WINTER INTERNSHIP - 도넛과 막대 그래프 (Java) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 문제를 보고 유니온-파인드로 그룹을 찾아야하나 싶었다. 하지만 문제에서 조건으로 주어진 임의로 생성된 정점 때문에 해당 방식으로 접근하기가 쉽지 않았다. 모든 경로를 탐색해서 그래프의 형태를 파악하지 않아도 해결할 수 있는 방법이 있었다. 각 그래프에서 특징이 되는 노드 하나만 찾아내는 방식이다. 각 그래프들을 식별할 수 있는 노드의 특징은 다음과 같다. - 임의로 생성된 정점 : 모든 그래프를 연결하는 정점이기 때문에 들어오는 간선이 없고 나가는 간선만 존재한다. 문제에서 그래프 갯수는 2개 이상이라 ..
[프로그래머스] 2023 KAKAO BLIND RECRUITMENT - 택배 배달과 수거하기 (Java) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 핵심은 트럭 하나로 모든 배달과 수거를 마치고 돌아오는 최소 이동 거리를 구하는 것 트럭이 최소 이동 거리로 움직이려면 최대한 멀리 떨어진 집의 배달과 수거를 먼저 완료시켜, 멀리 올 일이 없게 만들어야 한다. - 주어진 배열을 뒤에서부터 찾도록 For문을 거꾸로 돌린다. - 먼 집부터 방문 시, 해당 집에 배달/수거할 박스가 없다면 다음으로 넘어가도 좋다. 트럭의 cap에 따라 한 집에 배달/수거 양을 한 번만에 수행할 수 없을 수도 있고, 오히려 트럭에 공간이 남을 수도 있다. - 여러 번 왔다갔다 ..
[프로그래머스] PCCP 기출문제 - 아날로그 시계 (Java) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 시작하는 시간부터 끝나는 시간동안 초침이 몇 번 분침과 시침을 지나치는지에 대한 문제다. (1) 시작시간과 끝시간 사이를 간격에서 횟수를 구하는 것 보다는 (0시0분0초~끝나는 시간동안 마주친 횟수)에 (0시0분0초~시작하는 시간동안 마주친 횟수)를 빼는 방법을 이용하면 문제를 훨씬 단순하게 해결할 수 있다. 주의할 점은 이렇게 차이를 계산하는 방법은 시작시간 자체가 알람이 울리는 시간이라면 이 횟수까지 제외해버린다. 때문에 마지막에 현재 시간 또한 알람이 울릴 수 있는지 체크해서 횟수에 반영해줘야 한다..
[알고리즘] Java로 정렬 알고리즘 구현해보기 선택 정렬 [알고리즘] 선택 정렬(selection sort)이란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io // 선택 정렬 private static int[] selectionSort(int[] numbers) { // 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 두 번째 데이터와 바꾸는 과정을 반복 // 시간복잡도 O(n^2) // 공간복잡도 O(1) for (int i = 0; i < numbers.length; i++) { int minIndex = i; for (int j = i + 1; j < numbers.length; j++) { if (numbers[..
[프로그래머스] 2021 Dev-Matching: 웹 백엔드 개발자(상반기) - 헤비 유저가 소유한 장소 (MySQL) 코딩테스트 연습 - 헤비 유저가 소유한 장소 PLACES 테이블은 공간 임대 서비스에 등록된 공간의 정보를 담은 테이블입니다. PLACES 테이블의 구조는 다음과 같으며 ID, NAME, HOST_ID는 각각 공간의 아이디, 이름, 공간을 소유한 유저의 아이디를 programmers.co.kr 문제 설명 PLACES 테이블은 공간 임대 서비스에 등록된 공간의 정보를 담은 테이블입니다. PLACES 테이블의 구조는 다음과 같으며 ID, NAME, HOST_ID는 각각 공간의 아이디, 이름, 공간을 소유한 유저의 아이디를 나타냅니다. ID는 기본키입니다. NAME TYPE ID INT NAME VARCHAR HOST_ID INT 문제 이 서비스에서는 공간을 둘 이상 등록한 사람을 "헤비 유저"라고 부릅니다...
[프로그래머스] Summer/Winter Coding(2019) - 우유와 요거트가 담긴 장바구니 (MySQL) 코딩테스트 연습 - 우유와 요거트가 담긴 장바구니 CART_PRODUCTS 테이블은 장바구니에 담긴 상품 정보를 담은 테이블입니다. CART_PRODUCTS 테이블의 구조는 다음과 같으며, ID, CART_ID, NAME, PRICE는 각각 테이블의 아이디, 장바구니의 아이디, 상품 종류, 가 programmers.co.kr 문제 설명 CART_PRODUCTS 테이블은 장바구니에 담긴 상품 정보를 담은 테이블입니다. CART_PRODUCTS 테이블의 구조는 다음과 같으며, ID, CART_ID, NAME, PRICE는 각각 테이블의 아이디, 장바구니의 아이디, 상품 종류, 가격을 나타냅니다. NAME TYPE ID INT CART_ID INT NAME VARCHAR PRICE INT 데이터 분석 팀에서는..