https://school.programmers.co.kr/learn/courses/30/lessons/258707
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
코딩테스트 연습 > 2024 KAKAO WINTER INTERNSHIP > n + 1 카드게임
간단한 문제 설명
1~n 사이의 수가 적힌 카드가 하나씩 있는 카드 뭉치와 동전 coin개를 이용한 게임을 한다.
처음에 카드 뭉치에서 카드 n/3장을 뽑아 모두 가집니다. (n은 6의 배수입니다.) 카드와 교환 가능한 동전 coin개를 가지고 있습니다.
게임은 1라운드부터 시작되며, 각 라운드가 시작할 때 카드를 두 장 뽑습니다. 카드 뭉치에 남은 카드가 없다면 게임을 종료합니다. 뽑은 카드는 카드 한 장당 동전 하나를 소모해 가지거나, 동전을 소모하지 않고 버릴 수 있습니다.
카드에 적힌 수의 합이 n+1이 되도록 카드 두 장을 내고 다음 라운드로 진행할 수 있습니다. 만약 카드 두 장을 낼 수 없다면 게임을 종료합니다.
ex)
n = 12, coin = 4 cards = [3, 6, 7, 2, 1, 10, 5, 9, 8, 12, 11, 4]
다음 라운드를 진행하기 위해 내야하는 카드의 합 = n + 1 = 13
처음 n/3 = 4 카드 4장, coin 4개를 가지고 시작
3,6,7,2
문제 접근
그리디 + 구현 문제
라운드를 정의
[3, 6, 7, 2, 1, 10, 5, 9, 8, 12, 11, 4]
[3,6,7,2] 0라운드
[1,10] 1라운드
[5,9] 2라운드
[8,12] 3라운드
[11,4] 4라운드
만약 4라운드에서까지 카드 2장을 내고 통과를 하면 5라운드는 보너스라고 생각하자.
즉 12개의 카드는 총 1~4라운드 + 1로 최대가 5이다.
n = 12 니까 각 라운드에서 내야 하는 카드의 합은 13이다.
각 카드의 숫자는 중복이 없다 즉 pair(짝)이 항상 정해져 있다.
ex) [12,1], [6,7], [10,3] ....
카드는 항상 순서대로 뽑는다.
즉 각 라운드에서 얻을 수 있는 카드는 정해져 있고 한번 카드를 포기하면 다신 얻을 수 없다.
하지만 우리는 항상 순서대로 뽑는다는 규칙으로 pair가 언제 만들어 지는지, 또한 coin을 얼마나 사용하는지 알 수 있다.
coin은 n/3까지의 숫자들은 coin 소비 x 나머지는 항상 coin을 1개씩 소비해야 얻을 수 있다.
2차원 배열 memo에 이러한 정보를 기록 (나중에 그리디 하게 해당 숫자를 버릴 것인지 가지고 갈 것인지 판단용)
memo의 행은 숫자를 의미
열은 [0]: 짝이 맞춰지는데 필요한 동전의 개수 [1]: 짝이 맞춰지는 라운드 [2]: 해당 숫자 동전 사용 여부
int [][] memo = new int [n+1][3];
for(int i = 0; i < n; i++){
int cur = cards[i];
if(i >= n/3){ // 동전 사용 여부 기록
memo[cur][2] = 1;
memo[cur][0]++;
memo[target-cur][0]++;
}
for(int j = 0; j < n; j++){
if(i == j) continue;
if(cur + cards[j] == target){
if(i >= j){
if(i >= n/3){
memo[cur][1] = (i - n/3)/2 + 1;
}
}
else{
if(j >= n/3){
memo[cur][1] = (j - n/3)/2 + 1;
}
}
break;
}
}
}
Set<Integer> set = new HashSet<>();
현재 내가 가지고 있는 동전을 보관하는 set
n/3 까지 coin을 소비하지 않고 set에 넣어준다.
for(int i = 0; i < n/3; i++){
set.add(cards[i]);
}
PriorityQueue 우선순위 큐 pair
pair는 합쳐서 n + 1이 되는 int [] 배열(size = 2)이 들어간다.
ex) pair({12,1}, {10,3} ...)
우선순위 큐의 정렬 순서는 2개의 숫자 동전 소비량을 기준으로 오름차순이다.
최대한 게임을 길게 하고 싶으면 각 라운드에서 동전을 적게 사용해야 한다.
memo[12][0] == memo[1][0]
PriorityQueue<int[]> pair = new PriorityQueue<>((o1,o2)->{
return memo[o1[0]][0] - memo[o2[0]][0];
});
boolean global = true;
라운드에서 성공적으로 카드 2장을 내고 coin 사용도 제한만큼만 사용했으면 true & 다음 라운드 아니라면 false & break
Set<Integer> delete = new HashSet<>();
현재 내가 가지고 있다가 버린 동전을 기록하는 set
★ ★
핵심사항: delete set에 숫자가 들어간다는 것은 해당 숫자와 파트너인 숫자는 게임이 끝날 때까지 무쓸모이다
핵심 로직 시작
round++
라운드 증가
이번 라운드 카드 받기
if(!delete.contains(target - cards[i])){
set.add(cards[i]);
coin--;
}
if(!delete.contains(target - cards[i+1])){
set.add(cards[i+1]);
coin--;
}
핵심사항이라고 설명했던 부분이다.
Pair 찾기
조건에 target - next < next 있는 이유는 중복 pair를 넣지 않기 위해서이다.
ex) new int[]{12,1} 추가 & new int[]{1,12} 추가
Iterator<Integer> it = set.iterator();
while(it.hasNext()){
int next = it.next();
if(set.contains(target - next) && target - next < next){
pair.add(new int[]{target - next, next});
}
}
Pair 사용하기
이번 로직의 관심사는 Pair 사용이다. 현재 동전 사용량은 궁금하지 않다.
다음 로직에서 생각한다.
아직 설명하지 않은 로직은 동전 소비가 제한보다 많이 사용했을 때 pair에 있는 숫자를 삭제해야 하는데
해당 로직에서는 pair와의 동기화를 하지 않는다. (너무 복잡해서)
대신 delete에 넣어서 삭제했다는 걸 알 수 있게 한다.
그래서 해당 숫자가 delete에 contain 한다면 pair에서 빼주는 방식이다.
만약 delete에 contain 하지 않는다면 정상적인 pair 니까 set에서 삭제 + delete에 넣어준다.
그리고 flag = true로 바꾸고 로직을 종료
이때 pair는 현재 라운드에서 가지고 있는 가장 동전을 적게 쓰는 정상 조합인 점이 핵심이다.
만약 flag가 false이면 global 또한 false로 바꾸고 전체 로직에서 탈출한다.
boolean flag = false;
while(!pair.isEmpty()){
int [] tmp = pair.poll();
if(delete.contains(tmp[0])) continue;
set.remove(tmp[0]);
set.remove(tmp[1]);
delete.add(tmp[0]);
delete.add(tmp[1]);
flag = true;
break;
}
if(!flag){
global = false;
break;
}
이제 마지막이다.
현재 coin 사용량이 음수 즉 제한보다 많이 사용했다면 삭제를 해줘야 한다.
set에서 stream으로 바꾸고 기준에 따라서 정렬을 한다.
정렬 이후 Collectors.toList() 사용하여 List 반환으로 스트림 최종연산을 마친다.
정렬 기준 ★ ★ ★
1. 숫자가 pair가 되기 위해서 사용하는 coin 개수 내림차순
2. 1번 조건에서 같다면 짝이 맞춰지는 라운드 내림차순
우린 coin을 적게 쓰고 싶고 1라운드라도 빠르게 pair가 되는 숫자를 원한다.
삭제 로직
가장 쓸모없는 순서대로 정렬을 했으니 이제 coin이 0이상 즉 제한을 넘기지 않도록 맞춰준다.
하지만 0 이상이 되는순간 끝내준다. 언제가 필요할 수도 있으니까 최소한의 삭제를 하는 게 핵심이다.
여기서 중요한점은 만약 pair에 있는 숫자를 삭제한다고 하면 그럼 파트너 숫자는 당연히 무쓸모이다.
그래서 같이 삭제한다.
삭제 대상을 delete에 넣는다.
delete , set 동기화 하면 마무리
if(coin < 0){
List<Integer> list = set.stream().sorted((o1,o2) -> {
if(memo[o1][0] != memo[o2][0]) return memo[o2][0] - memo[o1][0]; // 사용 coin
return memo[o2][1] - memo[o1][1]; // 라운드
}).collect(Collectors.toList());
int size = list.size();
for(int j = 0; j < size; j++){
if(coin >= 0) break;
int cur = list.get(j);
if(set.contains(target - cur)){
if(!delete.contains(cur)){
delete.add(cur);
if(memo[cur][2] == 1) coin++;
}
if(!delete.contains(target - cur)){
delete.add(target - cur);
if(memo[target - cur][2] == 1) coin++;
}
}
else{
delete.add(cur);
if(memo[cur][2] == 1) coin++;
}
}
}
it = delete.iterator();
while(it.hasNext()){
int next = it.next();
if(set.contains(next)){
set.remove(next);
}
}
return round + (global == true ? 1 : 0);
더 이상 뽑을 카드가 없어서 라운드가 끝난 거라면 + 1을 해준다.
전체 코드
import java.util.*;
import java.util.stream.*;
class Solution {
public int solution(int coin, int[] cards) {
int n = cards.length;
int target = n + 1;
// 0: 짝이 맞춰지는데 필요한 동전 개수 1: 짝이 맞춰지는 라운드 2: 사용 여부
int [][] memo = new int [n+1][3];
for(int i = 0; i < n; i++){
int cur = cards[i];
if(i >= n/3){ // 동전 사용 여부 기록
memo[cur][2] = 1;
memo[cur][0]++;
memo[target-cur][0]++;
}
for(int j = 0; j < n; j++){
if(i == j) continue;
if(cur + cards[j] == target){
if(i >= j){
if(i >= n/3){
memo[cur][1] = (i - n/3)/2 + 1;
}
}
else{
if(j >= n/3){
memo[cur][1] = (j - n/3)/2 + 1;
}
}
break;
}
}
}
Set<Integer> set = new HashSet<>();
for(int i = 0; i < n/3; i++){
set.add(cards[i]);
}
PriorityQueue<int[]> pair = new PriorityQueue<>((o1,o2)->{
return memo[o1[0]][0] - memo[o2[0]][0];
});
boolean global = true;
Set<Integer> delete = new HashSet<>();
int round = 0;
for(int i = n/3; i < n; i++){
round++;
if(!delete.contains(target - cards[i])){
set.add(cards[i]);
coin--;
}
if(!delete.contains(target - cards[i+1])){
set.add(cards[i+1]);
coin--;
}
// pair 찾기
Iterator<Integer> it = set.iterator();
while(it.hasNext()){
int next = it.next();
if(set.contains(target - next) && target - next < next){
pair.add(new int[]{target - next, next});
}
}
boolean flag = false;
while(!pair.isEmpty()){
int [] tmp = pair.poll();
if(delete.contains(tmp[0])) continue;
set.remove(tmp[0]);
set.remove(tmp[1]);
delete.add(tmp[0]);
delete.add(tmp[1]);
flag = true;
break;
}
if(!flag){
global = false;
break;
}
if(coin < 0){
List<Integer> list = set.stream().sorted((o1,o2) -> {
if(memo[o1][0] != memo[o2][0]) return memo[o2][0] - memo[o1][0]; // 사용 coin
return memo[o2][1] - memo[o1][1]; // 라운드
}).collect(Collectors.toList());
int size = list.size();
for(int j = 0; j < size; j++){
if(coin >= 0) break;
int cur = list.get(j);
if(set.contains(target - cur)){
if(!delete.contains(cur)){
delete.add(cur);
if(memo[cur][2] == 1) coin++;
}
if(!delete.contains(target - cur)){
delete.add(target - cur);
if(memo[target - cur][2] == 1) coin++;
}
}
else{
delete.add(cur);
if(memo[cur][2] == 1) coin++;
}
}
}
it = delete.iterator();
while(it.hasNext()){
int next = it.next();
if(set.contains(next)){
set.remove(next);
}
}
if(coin < 0){
global = false;
break;
}
i++;
}
return round + (global == true ? 1 : 0);
}
}- 전체 코드n + 1 카드게임
- n + 1 카드게임
- n + 1 카드게
'Algorithm > Programmers Java' 카테고리의 다른 글
| [JAVA] 프로그래머스 level2 연속된 부분 수열의 합 (0) | 2024.06.26 |
|---|---|
| [JAVA] 프로그래머스 level2 광물 캐기 (0) | 2024.06.24 |
| [JAVA] 프로그래머스 level3 상담원 인원 (0) | 2024.06.22 |
| [JAVA] 프로그래머스 level2 [PCCP 기출문제] 2번 / 석유 시추 (0) | 2024.06.21 |
| [JAVA] 프로그래머스 level3 주사위 고르기 (0) | 2024.06.19 |