호텔 대실
문1) 호텔을 운영 중인 코니는 최소한의 객실만을 사용하여 예약 손님들을 받으려고 합니다. 한 번 사용한 객실은 퇴실 시간을 기준으로 10분간 청소를 하고 다음 손님들이 사용할 수 있습니다.
예약 시각이 문자열 형태로 담긴 2차원 배열 book_time이 매개변수로 주어질 때, 코니에게 필요한 최소 객실의 수를 return 하는 solution 함수를 완성해주세요.
제한사항
- 1 ≤ book_time의 길이 ≤ 1,000
- book_time[i]는 ["HH:MM", "HH:MM"]의 형태로 이루어진 배열입니다
- [대실 시작 시각, 대실 종료 시각] 형태입니다.
- 시각은 HH:MM 형태로 24시간 표기법을 따르며, "00:00" 부터 "23:59" 까지로 주어집니다.
- 예약 시각이 자정을 넘어가는 경우는 없습니다.
- 시작 시각은 항상 종료 시각보다 빠릅니다.
- book_time[i]는 ["HH:MM", "HH:MM"]의 형태로 이루어진 배열입니다
입출력 예
| book_time | result |
|---|---|
[["15:00", "17:00"], ["16:40", "18:20"], ["14:20", "15:20"], ["14:10", "19:20"], ["18:20", "21:20"]] | 3 |
[["09:10", "10:10"], ["10:20", "12:20"]] | 1 |
[["10:20", "12:30"], ["10:20", "12:30"], ["10:20", "12:30"]] | 3 |
입출력 예 설명
입출력 예 #1
입출력 예 #2
첫 번째 손님이 10시 10분에 퇴실 후 10분간 청소한 뒤 두 번째 손님이 10시 20분에 입실하여 사용할 수 있으므로 방은 1개만 필요합니다.
입출력 예 #3
세 손님 모두 동일한 시간대를 예약했기 때문에 3개의 방이 필요합니다.
나의 풀이
package programmers;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
public class HotelReservation {
static class Reservation {
int start, end;
public Reservation(int start, int end) {
this.start = start;
this.end = end;
}
@Override
public String toString() {
return "[" + start + ", " + end + "]";
}
}
public static int solution(String[][] book_time) {
List<Reservation> reservations = new ArrayList<>();
for(String[] times : book_time) {
int start = Integer.parseInt(times[0].split(":")[0]) * 60 + Integer.parseInt(times[0].split(":")[1]);
int end = Integer.parseInt(times[1].split(":")[0]) * 60 + Integer.parseInt(times[1].split(":")[1]) + 10;
reservations.add(new Reservation(start, end));
}
//System.out.println("before sort: "+reservations.toString());
reservations.sort((r1,r2) -> r1.start - r2.start);
System.out.println("after sort: " + reservations.toString());
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(Reservation r : reservations) {
if(!pq.isEmpty() && pq.peek() <= r.start) {
pq.poll();
}
pq.add(r.end);
System.out.println(pq);
}
return pq.size();
}
public static void main(String[] args) {
String[][] book_time = {{"15:00", "17:00"},{"16:40", "18:20"},{"14:20", "15:20"},{"14:10", "19:20"},{"18:20", "21:20"}};
solution(book_time);
}
}
나의 생각
문제에 주어진 매개변수 `String[][] book_time = {{"15:00", "17:00"},{"16:40", "18:20"},{"14:20", "15:20"},{"14:10", "19:20"},{"18:20", "21:20"}}를 내가 필요로 정보로 가공하기 위해 필요한 작업을 먼저 진행하였다.
for(String[] times : book_time) {
int start = Integer.parseInt(times[0].split(":")[0]) * 60 + Integer.parseInt(times[0].split(":")[1]);
int end = Integer.parseInt(times[1].split(":")[0]) * 60 + Integer.parseInt(times[1].split(":")[1]) + 10;
reservations.add(new Reservation(start, end));
}
int start = 15 : 00 라고 하면,
int start = Integer.parseInt(times[0].split(":")[0]) * 60 + Integer.parseInt(times[0].split(":")[1]);
[ : ] :를 기준으로 왼쪽 편을 [0], 오른쪽 편을 [1]라고 하는데, 왼쪽 편 String 형"15" 을 Integer.parseInt로 int형인 15가 되고 * 60 과정으로 900이 된다. 마찬가지로,
오른쪽 편 String 형 "00"은 int형인 0이 되고, 900 + 0 이므로 결과적으로 900이 된다.
위와 동일하게,
int end 역시 17 : 00 은 int형으로 시간을 분으로 나타내면, 1020이 되는데, 청소시간 10분을 포함하여 1030이 된다.
Reservation 클래스
- Reservation 이라는 내부 클래스를 정의
- 이 클래스는 시작 시간(start)과 종료 시간(end)을 저장하는 두 개의 필드가 있음
- 생성자를 통해 이 두 필드의 값을 초기화할 수 있음
- toString 메서드를 오버라이드하여, 해당 객체를 문자열로 출력할 때 [start, end] 형식으로 출력되도록 함
- reservations 라는 ArrayList를 생성하는데, 이 리스트는 Reseravaion 타입의 객체들을 저장
- reservations.add() 호출될 때마다, Reservation 객체를 생성하고, reservations을 리스트에 추가함따라서, book_time을 순회한 결과는 다음과 같다.
하지만 List reservations 를 바로 사용할 수 없다. 그 이유는 리스트 안에 들어 있는 값들이 정렬이 되어있지 않기때문이다. 따라서, start를 기준으로 정렬을 해줘야한다.
reservations.sort((r1,r2) -> r1.start - r2.start)
(r1, r2) -> r1.start - r2. start
람다 표현식으로 Comparator의 compare 메서드이 구현을 람다로 제공한 것
- r1과 r2는 reservations 리스트의 Reservation 타입의 두 객체를 나타냄
- r1.start - r2.start : 두 예약의 시작 시간을 비교하여 정수 값을 반환
- 양수 : r1의 시작 시간이 r2보다 뒤에 있음 (r1이 r2 보다 큼)
- 0 : 두 예약의 시작 시간이 동일함
- 음수 : r1의 시작 시간이 r2 보다 앞에 있음 (r1이 r2보다 작음)
이 코드를 통해 reservations 리스트는 각 예약의 시작 시간을 기주으로 오름차순으로 정렬
일련의 과정을 거치면, 매개변수로 주어졌던 데이터를 내가 필요로 하는 데이터로 정제가 완료가 되었음을 알 수 있다.
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(Reservation r : reservations) {
if(!pq.isEmpty() && pq.peek() <= r.start) {
pq.poll();
}
pq.add(r.end);
}위 로직에서 보면 알 수 있듯이, PiorityQueue를 사용하는데, 그 이유는 다음과 같다.
PriorityQueue 요소들이 우선순위에 따라 정렬되어 저장됨.
기본적으로 자바의 PriorityQueue는 최소 우선 순위 힙(Heap)을 구현하기 때문에 가장 작은 값이 큐의 맨 앞에 있게 됨
따라서 PriorityQueue는 청소가 끝나는 시간(end 값)을 관리하기 위해 사용되며, 가장 빠르게 청소가 끝나는 방이 pq의 원소 가장 앞에 위치하게 된다.
1. 모든 예약을 시작 시간을 기준으로 정렬함
2. 각 예약을 차례대로 순회하면서 pq에서 가장 빠른 청소 종료 시간이 현재
예약의 시작 시간보다 이전이면 해당 룸을 사용하고 그 룸의 청소 종료 시간을
큐에서 제거함
3. 해당 예약의 청소가 끝나는 시간을 pq에 추가
4. 최종적으로, pq의 크기는 동시에 필요한 룸의 최대 개수를 나타냄
마법의 엘리베이터
문2) 마법의 세계에 사는 민수는 아주 높은 탑에 살고 있습니다. 탑이 너무 높아서 걸어 다니기 힘든 민수는 마법의 엘리베이터를 만들었습니다. 마법의 엘리베이터의 버튼은 특별합니다. 마법의 엘리베이터에는 -1, +1, -10, +10, -100, +100 등과 같이 절댓값이 10c (c ≥ 0 인 정수) 형태인 정수들이 적힌 버튼이 있습니다. 마법의 엘리베이터의 버튼을 누르면 현재 층 수에 버튼에 적혀 있는 값을 더한 층으로 이동하게 됩니다. 단, 엘리베이터가 위치해 있는 층과 버튼의 값을 더한 결과가 0보다 작으면 엘리베이터는 움직이지 않습니다. 민수의 세계에서는 0층이 가장 아래층이며 엘리베이터는 현재 민수가 있는 층에 있습니다.
마법의 엘리베이터를 움직이기 위해서 버튼 한 번당 마법의 돌 한 개를 사용하게 됩니다.예를 들어, 16층에 있는 민수가 0층으로 가려면 -1이 적힌 버튼을 6번, -10이 적힌 버튼을 1번 눌러 마법의 돌 7개를 소모하여 0층으로 갈 수 있습니다. 하지만, +1이 적힌 버튼을 4번, -10이 적힌 버튼 2번을 누르면 마법의 돌 6개를 소모하여 0층으로 갈 수 있습니다.
마법의 돌을 아끼기 위해 민수는 항상 최소한의 버튼을 눌러서 이동하려고 합니다. 민수가 어떤 층에서 엘리베이터를 타고 0층으로 내려가는데 필요한 마법의 돌의 최소 개수를 알고 싶습니다. 민수와 마법의 엘리베이터가 있는 층을 나타내는 정수 storey 가 주어졌을 때, 0층으로 가기 위해 필요한 마법의 돌의 최소값을 return 하도록 solution 함수를 완성하세요.
제한사항
- 1 ≤ storey ≤ 100,000,000
입출력 예
| storey | result |
|---|---|
| 16 | 6 |
| 2554 | 16 |
입출력 예 #2
- -1, +100이 적힌 버튼을 4번, +10이 적힌 버튼을 5번, -1000이 적힌 버튼을 3번 누르면 0층에 도착 할 수 있습니다. 그러므로 16을 return 합니다.
나의 풀이
첫번째 풀이 ( 최적화 실패)
package programmers;
public class MagicElevator {
public static int solution(int storey) {
String strChange = String.valueOf(storey);
int first = Integer.parseInt(strChange.substring(0, 1));
int upperBound = (first + 1) * (int)Math.pow(10, strChange.length() - 1);
int lowerBound = first * (int)Math.pow(10, strChange.length() - 1);
int closeStorey = Math.abs(storey - lowerBound) > Math.abs(storey - upperBound) ? upperBound : lowerBound;
int difference = Math.abs(storey - closeStorey);
//System.out.println(difference);
int cnt = 0;
for(int i = 8; i >= 0; i--) {
int value = (int)Math.pow(10, i);
cnt += difference / value;
difference %= value;
}
System.out.println(cnt);
return cnt;
}
public static void main(String[] args) {
int storey = 2554;
solution(storey);
}
}
탐욕법(Greedy Algorithm)을 적용한 로직
탐욕법이란?
- 최적화 문제를 해결하는 알고리즘 중의 하나로, 각 단계에서 지금 당장 가장 좋은 것만 선택하는 방법으로 문제를 해결하려는 전략
package programmers;
public class MagicElevator {
public static int solution(int storey) {
int answer = 0;
while ( storey > 0) {
int digit = storey % 10;
storey /= 10;
if( digit == 5) {
if(storey % 10 >= 5) {
answer += (10 - digit);
storey++;
}else {
answer += digit;
}
}
else if (digit > 5) {
answer += (10 - digit);
storey++;
}else {
answer += digit;
}
}
return answer;
}
public static void main(String[] args) {
int storey = 109;
solution(storey);
}
}
나의 생각
109를 예를들어보면, 9층을 먼저 내려가고, 100층이 되면 100층을 한번에 내려갈 수 있으므로 총 10개의 마법을 돌을 소비하는 반면, 109층에서 1층을 오르고, 110층이되면 10층을 내려온 뒤, 다시 100층을 한번에 내려오면 총 3개의 마법을 돌을 소비하면서 0층까지 내려올 수 있다. 이를 로직화를 하기 위해 몇 가지 내용을 정리해보자.
1. 자릿수가 6에서 9사이의 수라면 10에서 해당 수를 뺀 값만큼 +버튼을 눌러
10을 만들고, 그 다음 자릿수를 1증가시킨다.
자릿수가 0에서 4사이의 수라면, 해당 수만큼 -버튼을 눌러 0을 만든다.
2. 자릿수가 5인 경우는 경우
- 그 다음의 자릿수(즉, 앞 자릿수)가 5보다 크거나 같으면, 10에서 5를 뺀 값인
5만큼 +버튼을 눌러 10을 만들고, 그 다음 자릿수를 1증가
- 그 다음의 자릿수(즉, 앞 자릿수)가 5보다 작으면, 5만큼 -버튼을 눌러 0을 만든다.
457과 657의 수를 예를들어 문제를 풀어보자.
- 457
- 첫 번째 자릿수 7: +3을 해서 10을 만들고, 다음 자릿수 5를 1 증가시켜 6으로 만듦
- 두 번째 자릿수 6: +4를 해서 10을 만들고, 다음 자릿수 4를 1증가시켜 5로 만듦
- 세 번째 자릿수 5: 앞 자리 수가 없으므로 5보다 작다고 가정하고, -5를 해서 0을 만듦
- 따라서 총 소비한 돌의 사용량은 3 + 4 +5 = 12
- 657
- 첫 번째 자릿수 7: +3을 해서 10을 만들고, 다음 자릿수 5를 1 증가시켜 6으로 만듦
- 두 번째 자릿수 6: +4를 해서 10을 만들고, 다음 자릿수 6을 1 증가시켜 7로 만듦
- 세 번째 자릿수 7: +3을 해서 10을 만들고, 다음 자릿수가 없으므로 멈춤
- 이제 아의 모든 자릿수는 0이 되었으므로, -1000을 하여 0층으로 만듦
- 따라서 총 소비한 돌의 사용량은 3 + 4 + 3 + 1 = 11
프렌즈4블록
문3) 블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록".
같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.
만약 판이 위와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워진다. 같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다.
블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다.
만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면 다시 지워지고 떨어지고를 반복하게 된다.
위 초기 배치를 문자로 표시하면 아래와 같다.
TTTANT
RRFACC
RRRFCC
TRRRAA
TTMMMF
TMMTTJ각 문자는 라이언(R), 무지(M), 어피치(A), 프로도(F), 네오(N), 튜브(T), 제이지(J), 콘(C)을 의미한다
입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라.
입력 형식
- 입력으로 판의 높이 m, 폭 n과 판의 배치 정보 board가 들어온다.
- 2 ≦ n, m ≦ 30
- board는 길이 n인 문자열 m개의 배열로 주어진다. 블록을 나타내는 문자는 대문자 A에서 Z가 사용된다.
출력 형식
입력으로 주어진 판 정보를 가지고 몇 개의 블록이 지워질지 출력하라.
입출력 예
| m | n | board | answer |
|---|---|---|---|
| 4 | 5 | ["CCBDE", "AAADE", "AAABF", "CCBBF"] | 14 |
| 6 | 6 | ["TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"] | 15 |
입출력 예 설명
- 입출력 예제 1의 경우, 첫 번째에는 A 블록 6개가 지워지고, 두 번째에는 B 블록 4개와 C 블록 4개가 지워져, 모두 14개의 블록이 지워진다.
- 입출력 예제 2는 본문 설명에 있는 그림을 옮긴 것이다. 11개와 4개의 블록이 차례로 지워지며, 모두 15개의 블록이 지워진다.
나의 풀이
package programmers;
import java.util.HashSet;
import java.util.Set;
public class Friends4Block {
public static int solution(int m, int n, String[] board) {
int answer = 0;
char[][] grid = new char[m][n];
for(int i = 0; i < m ; i++) {
grid[i] = board[i].toCharArray();
}
boolean canCrush = true;
while(canCrush) {
canCrush = false;
Set<String> toRemove = new HashSet<>();
for(int i = 0; i < m - 1; i++) {
for(int j = 0; j < n - 1; j++) {
if(grid[i][j] == '0') continue;
char c = grid[i][j];
if (grid[i + 1][j] == c && grid[i][j + 1] == c && grid[i + 1][j + 1] == c) {
toRemove.add(i + "," + j);
toRemove.add((i + 1) + "," + j);
toRemove.add(i + "," + (j + 1));
toRemove.add((i + 1) + "," + (j + 1));
canCrush = true;
}
}
}
for (String s : toRemove) {
String[] parts = s.split(",");
int x = Integer.parseInt(parts[0]);
int y = Integer.parseInt(parts[1]);
grid[x][y] = '0';
}
for (int j = 0; j < n; j++) {
int emptyIdx = m - 1;
for (int i = m - 1; i >= 0; i--) {
if (grid[i][j] == '0') continue;
if (i != emptyIdx) {
grid[emptyIdx][j] = grid[i][j];
grid[i][j] = '0';
}
emptyIdx--;
}
}
answer += toRemove.size();
}
System.out.println(answer);
return answer;
}
public static void main(String[] args) {
String[] board = {"TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"};
solution(6, 6, board);
}
}
메뉴 리뉴얼
문4) 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다.
기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴를 제공하기로 결정했습니다. 어떤 단품메뉴들을 조합해서 코스요리 메뉴로 구성하면 좋을 지 고민하던 "스카피"는 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다.
단, 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다. 또한, 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다.
예를 들어, 손님 6명이 주문한 단품메뉴들의 조합이 다음과 같다면,
(각 손님은 단품메뉴를 2개 이상 주문해야 하며, 각 단품메뉴는 A ~ Z의 알파벳 대문자로 표기합니다.)
| 손님 번호 | 주문한 단품메뉴 조합 |
|---|---|
| 1번 손님 | A, B, C, F, G |
| 2번 손님 | A, C |
| 3번 손님 | C, D, E |
| 4번 손님 | A, C, D, E |
| 5번 손님 | B, C, F, G |
| 6번 손님 | A, C, D, E, H |
가장 많이 함께 주문된 단품 메뉴 조합에 따라 "스카피"가 만들게 될 코스요리 메뉴 구성 후보는 다음과 같습니다.
| 코스 종류 | 메뉴 구성 | 설명 |
|---|---|---|
| 요리 2개 코스 | A,C | 1번, 2번, 4번, 6번 손님으로부터 총 4번 주문됐습니다. |
| 요리 3개 코스 | C,D,E | 3번, 4번, 6번 손님으로부터 총 3번 주문됐습니다. |
| 요리 4개 코스 | B,C,F,G | 1번, 5번 손님으로부터 총 2번 주문됐습니다. |
| 요리 4개 코스 | A,C,D,E | 4번, 6번 손님으로부터 총 2번 주문됐습니다. |
문제
각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열 orders, "스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열 course가 매개변수로 주어질 때, "스카피"가 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
제한사항
- orders 배열의 크기는 2 이상 20 이하입니다.
- orders 배열의 각 원소는 크기가 2 이상 10 이하인 문자열입니다.
- 각 문자열은 알파벳 대문자로만 이루어져 있습니다.
- 각 문자열에는 같은 알파벳이 중복해서 들어있지 않습니다.
- course 배열의 크기는 1 이상 10 이하입니다.
- course 배열의 각 원소는 2 이상 10 이하인 자연수가 오름차순으로 정렬되어 있습니다.
- course 배열에는 같은 값이 중복해서 들어있지 않습니다.
- 정답은 각 코스요리 메뉴의 구성을 문자열 형식으로 배열에 담아 사전 순으로 오름차순 정렬해서 return 해주세요.
- 배열의 각 원소에 저장된 문자열 또한 알파벳 오름차순으로 정렬되어야 합니다.
- 만약 가장 많이 함께 주문된 메뉴 구성이 여러 개라면, 모두 배열에 담아 return 하면 됩니다.
- orders와 course 매개변수는 return 하는 배열의 길이가 1 이상이 되도록 주어집니다.
입출력 예
| orders | course | result |
|---|---|---|
| ["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"] | [2,3,4] | ["AC", "ACDE", "BCFG", "CDE"] |
| ["ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"] | [2,3,5] | ["ACD", "AD", "ADE", "CD", "XYZ"] |
| ["XYZ", "XWY", "WXA"] | [2,3,4] | ["WX", "XY"] |
입출력 예 설명
입출력 예 #2
- AD가 세 번, CD가 세 번, ACD가 두 번, ADE가 두 번, XYZ 가 두 번 주문됐습니다.
요리 5개를 주문한 손님이 1명 있지만, 최소 2명 이상의 손님에게서 주문된 구성만 코스요리 후보에 들어가므로, 요리 5개로 구성된 코스요리는 새로 추가하지 않습니다.
입출력 예 #3
- WX가 두 번, XY가 두 번 주문됐습니다.
3명의 손님 모두 단품메뉴를 3개씩 주문했지만, 최소 2명 이상의 손님에게서 주문된 구성만 코스요리 후보에 들어가므로, 요리 3개로 구성된 코스요리는 새로 추가하지 않습니다.
또, 단품메뉴를 4개 이상 주문한 손님은 없으므로, 요리 4개로 구성된 코스요리 또한 새로 추가하지 않습니다.
나의 풀이
테스트 케이스만 통과한 로직
package programmers;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class MenuRenewal {
public static String[] solution(String[] orders, int[] course) {
ArrayList<String> list = new ArrayList<>();
for(int i = 0; i < orders.length - 1 ; i++) {
Set<Character> singleMenu = new HashSet<>();
for(int j = 0; j < orders[i].length(); j++) {
singleMenu.add(orders[i].charAt(j));
}
for(int j = i + 1; j < orders.length; j++) {
String sb = "";
for(int k = 0; k < orders[j].length(); k++) {
if(singleMenu.contains(orders[j].charAt(k))) {
sb += orders[j].charAt(k);
}else {
continue;
}
if(sb.length() > 1) {
list.add(sb);
}
}
}
}
Map<String, Integer> map = new HashMap<>();
for(int i = 0; i < list.size(); i++) {
map.put(list.get(i), map.getOrDefault(list.get(i), 0) + 1);
}
for (int len : course) {
int maxVal = 0;
List<String> keysOfLength = new ArrayList<>();
for (String key : map.keySet()) {
if (key.length() == len) {
keysOfLength.add(key);
maxVal = Math.max(maxVal, map.get(key));
}
}
for (String key : keysOfLength) {
if (map.get(key) != maxVal) {
map.remove(key);
}
}
}
ArrayList<String> finalList = new ArrayList<>();
for(String str : map.keySet()) {
finalList.add(str);
}
Collections.sort(finalList);
String[] answer = new String[finalList.size()];
for(int i = 0; i < finalList.size(); i++) {
answer[i] = finalList.get(i);
}
System.out.println(Arrays.toString(answer));
return answer;
}
public static void main(String[] args) {
String[] orders = {"ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"};
int[] course = {2,3,5};
solution(orders, course);
}
}
수정된 로직
package programmers;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class MenuRenewal {
static Map<String, Integer> map = new HashMap<>();
public static String[] solution(String[] orders, int[] course) {
for(String order : orders) {
char[] arr = order.toCharArray();
Arrays.sort(arr);
combination(arr, "", 0);
}
List<String> answerList = new ArrayList<>();
for(int len : course) {
int max = 0;
Map<String, Integer> temp = new HashMap<>();
for(String key : map.keySet()) {
if(map.get(key) == max && key.length() == len) {
temp.put(key, map.get(key));
} else if(map.get(key) > max && key.length() == len) {
max = map.get(key);
temp.clear();
temp.put(key, map.get(key));
}
}
for(String key : temp.keySet()) {
if(temp.get(key) >= 2) {
answerList.add(key);
}
}
}
Collections.sort(answerList);
String[] answer = new String[answerList.size()];
answerList.toArray(answer);
System.out.println(Arrays.toString(answer));
return answer;
}
public static void combination(char[] arr, String str, int index) {
if(str.length() >= 2) {
map.put(str, map.getOrDefault(str, 0) + 1);
}
for(int i = index; i < arr.length; i++) {
combination(arr, str + arr[i], i+1);
}
}
public static void main(String[] args) {
String[] orders = {"ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"};
int[] course = {2,3,5};
solution(orders, course);
}
}
시소 짝궁
문5) 어느 공원 놀이터에는 시소가 하나 설치되어 있습니다. 이 시소는 중심으로부터 2(m), 3(m), 4(m) 거리의 지점에 좌석이 하나씩 있습니다.
이 시소를 두 명이 마주 보고 탄다고 할 때, 시소가 평형인 상태에서 각각에 의해 시소에 걸리는 토크의 크기가 서로 상쇄되어 완전한 균형을 이룰 수 있다면 그 두 사람을 시소 짝꿍이라고 합니다. 즉, 탑승한 사람의 무게와 시소 축과 좌석 간의 거리의 곱이 양쪽 다 같다면 시소 짝꿍이라고 할 수 있습니다.
사람들의 몸무게 목록 weights이 주어질 때, 시소 짝꿍이 몇 쌍 존재하는지 구하여 return 하도록 solution 함수를 완성해주세요.
제한 사항
- 2 ≤ weights의 길이 ≤ 100,000
- 100 ≤ weights[i] ≤ 1,000
- 몸무게 단위는 N(뉴턴)으로 주어집니다.
- 몸무게는 모두 정수입니다.
입출력 예
| weights | result |
|---|---|
[100,180,360,100,270] | 4 |
입출력 예 설명
- {100, 100} 은 서로 같은 거리에 마주보고 앉으면 균형을 이룹니다.
- {180, 360} 은 각각 4(m), 2(m) 거리에 마주보고 앉으면 균형을 이룹니다.
- {180, 270} 은 각각 3(m), 2(m) 거리에 마주보고 앉으면 균형을 이룹니다.
- {270, 360} 은 각각 4(m), 3(m) 거리에 마주보고 앉으면 균형을 이룹니다.
나의 풀이
시간 초과로 실패한 로직
package programmers;
import java.util.ArrayList;
import java.util.List;
public class SeesawPairing {
public static long solution(int[] weights) {
long answer = 0;
List<int[]> combinations = findCombinations(weights, 0, new int[2], 0);
for(int i = 0; i < combinations.size(); i++) {
int[] pairing = combinations.get(i);
if(pairing[0] == pairing[1]) {
answer++;
} else {
for(int j = 2; j <= 4; j++) {
for(int k = 2; k <=4; k++) {
if((pairing[0] * j) == (pairing[1] * k)) {
answer++;
}
}
}
}
}
return answer;
}
public static List<int[]> findCombinations(int[] weights, int start, int[] current, int currentIndex) {
List<int[]> combinations = new ArrayList<>();
if (currentIndex == 2) {
combinations.add(current.clone());
return combinations;
}
for (int i = start; i < weights.length; i++) {
current[currentIndex] = weights[i];
combinations.addAll(findCombinations(weights, i + 1, current, currentIndex + 1));
}
return combinations;
}
public static void main(String[] args) {
int[] weights = {100,180,360,100,270};
solution(weights);
}
}
수정한 로직
package programmers;
import java.util.Arrays;
import java.util.LinkedHashMap;
import java.util.Map;
public class SeesawPairing {
public static long solution(int[] weights) {
long answer = 0;
Arrays.sort(weights);
Map<Double, Integer> map = new LinkedHashMap<>();
for(int weight : weights) {
double a = weight * 1.0;
double b = (weight * 2.0) / 3.0;
double c = (weight * 1.0) / 2.0;
double d = (weight * 3.0) / 4.0;
System.out.printf("a: %f, b: %f, c: %f, d: %f\n",a,b,c,d);
if(map.containsKey(a)) answer += map.get(a);
if(map.containsKey(b)) answer += map.get(b);
if(map.containsKey(c)) answer += map.get(c);
if(map.containsKey(d)) answer += map.get(d);
System.out.println("answer: " + answer);
map.put((double) (weight), map.getOrDefault((double)(weight), 0)+1);
System.out.println("map: "+map);
}
return answer;
}
public static void main(String[] args) {
int[] weights = {100,180,360,100,270};
solution(weights);
}
}
HW + SW = 1