혼자 놀기의 달인
문1) 혼자서도 잘 노는 범희는 어느 날 방구석에 있는 숫자 카드 더미를 보더니 혼자 할 수 있는 재미있는 게임을 생각해냈습니다.
숫자 카드 더미에는 카드가 총 100장 있으며, 각 카드에는 1부터 100까지 숫자가 하나씩 적혀있습니다. 2 이상 100 이하의 자연수를 하나 정해 그 수보다 작거나 같은 숫자 카드들을 준비하고, 준비한 카드의 수만큼 작은 상자를 준비하면 게임을 시작할 수 있으며 게임 방법은 다음과 같습니다.
준비된 상자에 카드를 한 장씩 넣고, 상자를 무작위로 섞어 일렬로 나열합니다. 상자가 일렬로 나열되면 상자가 나열된 순서에 따라 1번부터 순차적으로 증가하는 번호를 붙입니다.
그 다음 임의의 상자를 하나 선택하여 선택한 상자 안의 숫자 카드를 확인합니다. 다음으로 확인한 카드에 적힌 번호에 해당하는 상자를 열어 안에 담긴 카드에 적힌 숫자를 확인합니다. 마찬가지로 숫자에 해당하는 번호를 가진 상자를 계속해서 열어가며, 열어야 하는 상자가 이미 열려있을 때까지 반복합니다.
이렇게 연 상자들은 1번 상자 그룹입니다. 이제 1번 상자 그룹을 다른 상자들과 섞이지 않도록 따로 둡니다. 만약 1번 상자 그룹을 제외하고 남는 상자가 없으면 그대로 게임이 종료되며, 이때 획득하는 점수는 0점입니다.
그렇지 않다면 남은 상자 중 다시 임의의 상자 하나를 골라 같은 방식으로 이미 열려있는 상자를 만날 때까지 상자를 엽니다. 이렇게 연 상자들은 2번 상자 그룹입니다.
1번 상자 그룹에 속한 상자의 수와 2번 상자 그룹에 속한 상자의 수를 곱한 값이 게임의 점수입니다.
상자 안에 들어있는 카드 번호가 순서대로 담긴 배열 cards가 매개변수로 주어질 때, 범희가 이 게임에서 얻을 수 있는 최고 점수를 구해서 return 하도록 solution 함수를 완성해주세요.
제한사항
- 2 ≤ cards의 길이 ≤ 100
- cards의 원소는 cards의 길이 이하인 임의의 자연수입니다.
- cards에는 중복되는 원소가 존재하지 않습니다.
- cards[i]는 i + 1번 상자에 담긴 카드에 적힌 숫자를 의미합니다.
입출력 예
| cards | result |
|---|---|
[8,6,3,7,2,5,1,4] | 12 |
입출력 예 설명
- 1, 4, 7, 8이 속하는 상자의 그룹과 2, 5, 6이 속하는 상자의 그룹과 3이 속하는 상자의 그룹이 존재합니다. 따라서 3번 상자를 고르지 않았을 때, 두 번의 시행에서 3과 4를 기록하며 최고 점수 12를 얻을 수 있습니다.
나의 풀이
1. dfs를 사용한 첫 로직 (실패)
package programmers;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
public class MasterOfPlayingAlone {
static boolean[] visitedBox;
static int[] box;
static ArrayList<Integer> groupList = new ArrayList<>();
public static void dfs(int index, int N) {
visitedBox[index] = true;
int boxNumber = box[index];
int cnt = 0;
while(true) {
cnt++;
if(visitedBox[boxNumber])break;
visitedBox[boxNumber] = true;
boxNumber = box[boxNumber];
}
groupList.add(cnt);
if(!visitedBox[index+1]) {
dfs(index+1, N);
}
}
public static int solution(int[] cards) {
int N = cards.length;
box = new int[N+1];
visitedBox = new boolean[N+1];
for(int i = 1; i <= N; i++) {
box[i] = cards[i-1];
}
dfs(1,N);
Collections.sort(groupList, Collections.reverseOrder());
int answer = groupList.get(0) * groupList.get(1);
return answer;
}
public static void main(String[] args) {
int[] cards = {8,6,3,7,2,5,1,4};
solution(cards);
}
}
2. dfs를 사용한 두 번째 로직 (성공)
package programmers;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
public class MasterOfPlayingAlone {
static boolean[] visitedBox;
static int[] box;
static ArrayList<Integer> groupList = new ArrayList<>();
public static void dfs(int index) {
if(visitedBox[index]) return;
int cnt = 0;
while(!visitedBox[index]) {
visitedBox[index] = true;
cnt++;
index = box[index];
}
groupList.add(cnt);
}
public static int solution(int[] cards) {
int N = cards.length;
box = new int[N+1];
visitedBox = new boolean[N+1];
for(int i = 1; i <= N; i++) {
box[i] = cards[i-1];
}
for(int i = 1; i <= N; i++) {
dfs(i);
}
Collections.sort(groupList, Collections.reverseOrder());
if(groupList.size() < 2) return 0;
int answer = groupList.get(0) * groupList.get(1);
return answer;
}
public static void main(String[] args) {
int[] cards = {8,6,3,7,2,5,1,4};
solution(cards);
}
}
3. visited 배열을 쓰지 않는 로직 (성공)
package programmers;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
public class MasterOfPlayingAlone {
static int[] box;
static ArrayList<Integer> groupList = new ArrayList<>();
public static void dfs(int index) {
int cnt = 0;
while(box[index] != -1) {
int nextIndex = box[index];
box[index] = -1;
index = nextIndex;
cnt++;
}
if(cnt > 0) {
groupList.add(cnt);
}
}
public static int solution(int[] cards) {
int N = cards.length;
box = new int[N+1];
for(int i = 1; i <= N; i++) {
box[i] = cards[i-1];
}
for(int i = 1; i <= N; i++) {
if(box[i] != -1) {
dfs(i);
}
}
Collections.sort(groupList, Collections.reverseOrder());
if(groupList.size() < 2) return 0;
int answer = groupList.get(0) * groupList.get(1);
return answer;
}
public static void main(String[] args) {
int[] cards = {8,6,3,7,2,5,1,4};
solution(cards);
}
}
나의 생각
첫 번째 로직과 두 번째 로직의 차이를 표로 정리해보았다.
| 첫 번째 로직 | 두 번째 로직 |
|---|---|
dfs 함수가 index+1을 인자로 받아 재귀적으로 호출됨 | dfs 함수가 index만 인자로 받고, solution 함수 내에서 모든 인덱스에 대해 호출됨 |
dfs 내 if(!visitedBox[index+1]) 조건으로 다음 상자로 넘어감 | solution 내의 for 루프가 모든 상자를 순회함 |
만약 index+1 상자가 이미 방문되었으면 더 이상 dfs를 호출하지 않음 | 모든 상자가 시작점이 될 수 있도록 각 상자마다 방문 여부를 확인 후 dfs를 호출함 |
groupList에는 한 번의 DFS 실행으로 생성된 그룹만 저장될 수 있음 | groupList에는 모든 상자 그룹의 크기가 저장됨 |
| 만약 중간에 모든 상자를 방문했다면 남은 상자에 대한 그룹화를 고려하지 않음 | 모든 상자에 대해 그룹화를 고려하여 그룹화가 누락되지 않음 |
| 상자 그룹이 하나인 경우에 대한 처리가 없어 잘못된 점수를 반환할 수 있음 | 상자 그룹이 하나만 있을 경우를 고려하여 0점을 반환함으로써 정확한 점수 계산을 보장함 |
즉, 첫 번째 로직은 재귀 호출을 통해 연속적인 상자만을 방문하려고 했고, 두 번쨰 로직은 모든 상자에 대한 방문을 개별적으로 검사하여 완전한 그룹화를 수행함
이모티콘 할인행사
문2) 카카오톡에서는 이모티콘을 무제한으로 사용할 수 있는 이모티콘 플러스 서비스 가입자 수를 늘리려고 합니다.
이를 위해 카카오톡에서는 이모티콘 할인 행사를 하는데, 목표는 다음과 같습니다.
- 이모티콘 플러스 서비스 가입자를 최대한 늘리는 것.
- 이모티콘 판매액을 최대한 늘리는 것.
1번 목표가 우선이며, 2번 목표가 그 다음입니다.
이모티콘 할인 행사는 다음과 같은 방식으로 진행됩니다.
- n명의 카카오톡 사용자들에게 이모티콘 m개를 할인하여 판매합니다.
- 이모티콘마다 할인율은 다를 수 있으며, 할인율은 10%, 20%, 30%, 40% 중 하나로 설정됩니다.
카카오톡 사용자들은 다음과 같은 기준을 따라 이모티콘을 사거나, 이모티콘 플러스 서비스에 가입합니다.
- 각 사용자들은 자신의 기준에 따라 일정 비율 이상 할인하는 이모티콘을 모두 구매합니다.
- 각 사용자들은 자신의 기준에 따라 이모티콘 구매 비용의 합이 일정 가격 이상이 된다면, 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입합니다.
다음은 2명의 카카오톡 사용자와 2개의 이모티콘이 있을때의 예시입니다.
| 사용자 | 비율 | 가격 |
|---|---|---|
| 1 | 40 | 10,000 |
| 2 | 25 | 10,000 |
| 이모티콘 | 가격 |
|---|---|
| 1 | 7,000 |
| 2 | 9,000 |
1번 사용자는 40%이상 할인하는 이모티콘을 모두 구매하고, 이모티콘 구매 비용이 10,000원 이상이 되면 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입합니다.
2번 사용자는 25%이상 할인하는 이모티콘을 모두 구매하고, 이모티콘 구매 비용이 10,000원 이상이 되면 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입합니다.
1번 이모티콘의 가격은 7,000원, 2번 이모티콘의 가격은 9,000원입니다.
만약, 2개의 이모티콘을 모두 40%씩 할인한다면, 1번 사용자와 2번 사용자 모두 1,2번 이모티콘을 구매하게 되고, 결과는 다음과 같습니다.
| 사용자 | 구매한 이모티콘 | 이모티콘 구매 비용 | 이모티콘 플러스 서비스 가입 여부 |
|---|---|---|---|
| 1 | 1,2 | 9,600 | X |
| 2 | 1,2 | 9,600 | X |
이모티콘 플러스 서비스 가입자는 0명이 늘어나고 이모티콘 판매액은 19,200원이 늘어납니다.
하지만, 1번 이모티콘을 30%할인하고 2번 이모티콘을 40% 할인한다면 결과는 다음과 같습니다.
| 사용자 | 구매한 이모티콘 | 이모티콘 구매 비용 | 이모티콘 플러스 서비스 가입 여부 |
|---|---|---|---|
| 1 | 2 | 5,400 | X |
| 2 | 1,2 | 10,300 | O |
2번 사용자는 이모티콘 구매 비용을 10,000원 이상 사용하여 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입하게 됩니다.
따라서, 이모티콘 플러스 서비스 가입자는 1명이 늘어나고 이모티콘 판매액은 5,400원이 늘어나게 됩니다.
카카오톡 사용자 n명의 구매 기준을 담은 2차원 정수 배열 users, 이모티콘 m개의 정가를 담은 1차원 정수 배열 emoticons가 주어집니다. 이때, 행사 목적을 최대한으로 달성했을 때의 이모티콘 플러스 서비스 가입 수와 이모티콘 매출액을 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요.
제한사항
- 1 ≤ users의 길이 = n ≤ 100
- users의 원소는 [비율, 가격]의 형태입니다.
- users[i]는 i+1번 고객의 구매 기준을 의미합니다.
- 비율% 이상의 할인이 있는 이모티콘을 모두 구매한다는 의미입니다.
- 1 ≤ 비율 ≤ 40
- 가격이상의 돈을 이모티콘 구매에 사용한다면, 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입한다는 의미입니다.
- 100 ≤ 가격 ≤ 1,000,000
- 가격은 100의 배수입니다.
- 1 ≤ emoticons의 길이 = m ≤ 7
- emoticons[i]는 i+1번 이모티콘의 정가를 의미합니다.
- 100 ≤ emoticons의 원소 ≤ 1,000,000
- emoticons의 원소는 100의 배수입니다.
입출력 예
| users | emoticons | result |
|---|---|---|
[[40, 10000], [25, 10000]] | [7000, 9000] | [1, 5400] |
[[40, 2900], [23, 10000], [11, 5200], [5, 5900], [40, 3100], [27, 9200], [32, 6900]] | [1300, 1500, 1600, 4900] | [4, 13860] |
나의 풀이
시간초과 (최적화 실패) 로직
package programmers;
import java.util.ArrayList;
import java.util.List;
public class EmoticonDiscountEvent {
static int maxSubscriber = 0;
static int maxRevenue = 0;
static int MAX ;
static int[] discountIndex = {40, 30, 20, 10};
static int[][] users;
static int[] emoticons;
public static void getCalPrice(List<Integer> combination) {
System.out.println(combination);
int localSubscriber = 0;
int localRevenue = 0;
for(int[] user : users) {
int mindisRate = user[0];
int limit = user[1];
int totalSpend = 0;
for(int i = 0; i < emoticons.length; i++) {
int discountRate = combination.get(i);
if (discountRate >= mindisRate) {
int discountedPrice = emoticons[i] - ((emoticons[i] * discountRate) / 100);
totalSpend += discountedPrice;
}
}
if(totalSpend >= limit) {
localSubscriber++;
}else {
localRevenue += totalSpend;
}
if (localSubscriber < maxSubscriber ||
(localSubscriber == maxSubscriber && localRevenue <= maxRevenue)) {
continue;
}
maxSubscriber = localSubscriber;
maxRevenue = localRevenue;
}
}
public static void generateCombinations( List<Integer> current, int depth) {
if(depth == MAX) {
getCalPrice(current);
return;
}
for(int i = 0; i < discountIndex.length; i++) {
current.add(discountIndex[i]);
generateCombinations(current, depth + 1);
current.remove(current.size() - 1);
}
}
public static int[] solution(int[][] usersInput, int[] emoticonsPrice) {
users = usersInput;
emoticons = emoticonsPrice;
MAX = users.length;
generateCombinations(new ArrayList<>(),0);
return new int[] {maxSubscriber,maxRevenue};
}
public static void main(String[] args) {
int[][] users = {
{40, 2900},
{23, 10000},
{11, 5200},
{5, 5900},
{40, 3100},
{27, 9200},
{32, 6900}
};
int[] emoticons = {1300, 1500, 1600, 4900};
solution(users, emoticons);
}
}
우선순위 큐 자료구조를 사용한 로직
package programmers;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
public class EmoticonDiscountEvent {
static int[] discountIndex = {40, 30, 20, 10};
static PriorityQueue<int[]> pq;
static int[] discountRate;
static int[][] users;
static int[] emoticons;
public static void generateCombinations(int depth) {
// 모든 이모티콘에 대한 할인율 조합이 완성되었을 때
if(depth == discountRate.length) {
int subscriber = 0;
int fee = 0;
// 사용자별로 할인율 조합에 따른 구매 및 서비스 가입 여부 결정
for(int i = 0; i < users.length; i++) {
int sum = 0;
for(int j = 0; j < emoticons.length; j++) {
// 사용자의 할인율 기준을 만족하면 구매
if(discountRate[j] >= users[i][0]) {
sum += emoticons[j] - ((emoticons[j] * discountRate[j])/100);
}
}
// 사용자가 지출 한도를 초과하면 서비스 가입
if(sum >= users[i][1]) subscriber++;
else fee += sum; // 지출 한도 미만이면 구매 금액 추가
}
// 우선순위 큐에 결과 저장 ( 서비스 가입자 수, 판매액)
pq.offer(new int[] {subscriber, fee});
return;
}
// 할인율 조합 생성
for(int i = 0; i < discountIndex.length; i++) {
discountRate[depth] = discountIndex[i];
System.out.println(Arrays.toString(discountRate));
generateCombinations(depth + 1);
}
}
public static int[] solution(int[][] usersInput, int[] emoticonsInput) {
users = usersInput;
emoticons = emoticonsInput;
discountRate = new int[emoticons.length];
// 우선순위 큐 초기화 ( 서비스 가입자 수 내림차순, 판매액 내림차순)
pq = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] == o2[0] ? o2[1] - o1[1] : o2[0] - o1[0];
}
});
// 할인율 조합 생성 메서드 호출
generateCombinations(0);
return pq.poll();
}
public static void main(String[] args) {
int[][] users = {
{40, 2900},
{23, 10000},
{11, 5200},
{5, 5900},
{40, 3100},
{27, 9200},
{32, 6900}
};
int[] emoticons = {1300, 1500, 1600, 4900};
solution(users, emoticons);
}
}
과제 진행하기
문3) 과제를 받은 루는 다음과 같은 순서대로 과제를 하려고 계획을 세웠습니다.
과제는 시작하기로 한 시각이 되면 시작합니다.
새로운 과제를 시작할 시각이 되었을 때, 기존에 진행 중이던 과제가 있다면 진행 중이던 과제를 멈추고 새로운 과제를 시작합니다.
진행중이던 과제를 끝냈을 때, 잠시 멈춘 과제가 있다면, 멈춰둔 과제를 이어서 진행합니다.
만약, 과제를 끝낸 시각에 새로 시작해야 되는 과제와 잠시 멈춰둔 과제가 모두 있다면, 새로 시작해야 하는 과제부터 진행합니다.
멈춰둔 과제가 여러 개일 경우, 가장 최근에 멈춘 과제부터 시작합니다.
과제 계획을 담은 이차원 문자열 배열 plans가 매개변수로 주어질 때, 과제를 끝낸 순서대로 이름을 배열에 담아 return 하는 solution 함수를 완성해주세요.
제한사항
- 3 ≤ plans의 길이 ≤ 1,000
- plans의 원소는 [name, start, playtime]의 구조로 이루어져 있습니다.
- name : 과제의 이름을 의미합니다.
- 2 ≤ name의 길이 ≤ 10
- name은 알파벳 소문자로만 이루어져 있습니다.
- name이 중복되는 원소는 없습니다.
- start : 과제의 시작 시각을 나타냅니다.
- "hh:mm"의 형태로 "00:00" ~ "23:59" 사이의 시간값만 들어가 있습니다.
- 모든 과제의 시작 시각은 달라서 겹칠 일이 없습니다.
- 과제는 "00:00" ... "23:59" 순으로 시작하면 됩니다. 즉, 시와 분의 값이 작을수록 더 빨리 시작한 과제입니다.
- playtime : 과제를 마치는데 걸리는 시간을 의미하며, 단위는 분입니다.
- 1 ≤ playtime ≤ 100
- playtime은 0으로 시작하지 않습니다.
- 배열은 시간순으로 정렬되어 있지 않을 수 있습니다.
- name : 과제의 이름을 의미합니다.
- plans의 원소는 [name, start, playtime]의 구조로 이루어져 있습니다.
- 진행중이던 과제가 끝나는 시각과 새로운 과제를 시작해야하는 시각이 같은 경우 진행중이던 과제는 끝난 것으로 판단합니다.
입출력 예
| plans | result |
|---|---|
[["korean", "11:40", "30"], ["english", "12:10", "20"], ["math", "12:30", "40"]] | ["korean", "english", "math"] |
[["science", "12:40", "50"], ["music", "12:20", "40"], ["history", "14:00", "30"], ["computer", "12:30", "100"]] | ["science", "history", "computer", "music"] |
[["aaa", "12:00", "20"], ["bbb", "12:10", "30"], ["ccc", "12:40", "10"]] | ["bbb", "ccc", "aaa"] |
입출력 예 설명
입출력 예 #1
"korean", "english", "math"순으로 과제를 시작합니다. "korean" 과제를 "11:40"에 시작하여 30분 후인 "12:10"에 마치고, 즉시 "english" 과제를 시작합니다. 20분 후인 "12:30"에 "english" 과제를 마치고, 즉시 "math" 과제를 시작합니다. 40분 후인 "01:10"에 "math" 과제를 마칩니다. 따라서 "korean", "english", "math" 순으로 과제를 끝내므로 차례대로 배열에 담아 반환합니다.
입출력 예 #2
"music", "computer", "science", "history" 순으로 과제를 시작합니다.
| 시각 | 진행 중 과제 | 잠시 멈춘 과제 | 설명 |
|---|---|---|---|
| "12:20" | "music" | [] | "music"을 시작합니다 |
| "12:30" | "computer" | ["music"] | "music"을 잠시 멈추고(남은 시간 30분)"computer"를 시작합니다 |
| "12:40" | "science" | ["music","computer"] | "computer"를 잠시 멈추고(남은 시간 90분) "science"를 시작합니다 |
| "13:30" | "computer" | ["music"] | "science"를 끝내고 가장 최근에 멈춘 "computer"를 다시 시작합니다 |
| "14:00" | "history" | ["music","computer"] | "computer"를 잠시 멈추고(남은 시간 60분) "history"를 시작합니다 |
| "14:30" | "computer" | ["music"] | "history"를 끝내고 가장 최근에 멈춘 "computer"를 다시 시작합니다 |
| "15:30" | "music" | [] | "computer"를 끝내고 가장 최근에 멈춘 "music"을 다시 시작합니다 |
| "16:00" | - | [] | "music"을 끝냅니다 |
- 따라서 ["science", "history", "computer", "music"] 순서로 과제를 마칩니다.
나의 풀이
package programmers;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Stack;
public class AssignmentProgress {
public static class Assignment {
String subject;
int startTimeInMinutes; // 분으로 표현된 시작 시간
int remainTime;
public Assignment(String subject, String start, int durationMin) {
this.subject = subject;
this.startTimeInMinutes = convert(start); // 문자열 시간을 분으로 변환
this.remainTime = durationMin;
}
}
public static int convert(String stringTime) {
String[] times = stringTime.split(":");
return Integer.parseInt(times[0]) * 60 + Integer.parseInt(times[1]);
}
public static String[] solution(String[][] plans) {
List<String> answer = new ArrayList<>();
Arrays.sort(plans, Comparator.comparing(plan -> convert(plan[1])));
Stack<Assignment> working = new Stack<>();
for (int i = 0; i < plans.length; i++) {
String subject = plans[i][0];
String startTime = plans[i][1];
int durationMin = Integer.parseInt(plans[i][2]);
Assignment currentAssignment = new Assignment(subject, startTime, durationMin);
if (i == plans.length - 1) {
answer.add(currentAssignment.subject);
} else {
int nextTime = convert(plans[i + 1][1]);
int remainTime = nextTime - currentAssignment.startTimeInMinutes;
working.push(currentAssignment);
while (!working.isEmpty() && remainTime > 0) {
Assignment workingAssignment = working.pop();
int played = Math.min(remainTime, workingAssignment.remainTime);
if (played == workingAssignment.remainTime) {
answer.add(workingAssignment.subject);
} else {
workingAssignment.remainTime -= played;
working.push(workingAssignment);
}
remainTime -= played;
}
}
}
while (!working.isEmpty()) {
answer.add(working.pop().subject);
}
System.out.println(answer.toString());
return answer.toArray(new String[0]);
}
public static void main(String[] args) {
String[][] plans = {
{"aaa", "12:00", "20"},
{"bbb", "12:10", "30"},
{"ccc", "12:40", "10"}
};
solution(plans);
}
}
혼자서 하는 틱택토
문4) 틱택토는 두 사람이 하는 게임으로 처음에 3x3의 빈칸으로 이루어진 게임판에 선공이 "O", 후공이 "X"를 번갈아가면서 빈칸에 표시하는 게임입니다. 가로, 세로, 대각선으로 3개가 같은 표시가 만들어지면 같은 표시를 만든 사람이 승리하고 게임이 종료되며 9칸이 모두 차서 더 이상 표시를 할 수 없는 경우에는 무승부로 게임이 종료됩니다.
할 일이 없어 한가한 머쓱이는 두 사람이 하는 게임인 틱택토를 다음과 같이 혼자서 하려고 합니다.
- 혼자서 선공과 후공을 둘 다 맡는다.
- 틱택토 게임을 시작한 후 "O"와 "X"를 혼자서 번갈아 가면서 표시를 하면서 진행한다.
틱택토는 단순한 규칙으로 게임이 금방 끝나기에 머쓱이는 한 게임이 종료되면 다시 3x3 빈칸을 그린 뒤 다시 게임을 반복했습니다. 그렇게 틱택토 수 십 판을 했더니 머쓱이는 게임 도중에 다음과 같이 규칙을 어기는 실수를 했을 수도 있습니다.
- "O"를 표시할 차례인데 "X"를 표시하거나 반대로 "X"를 표시할 차례인데 "O"를 표시한다.
- 선공이나 후공이 승리해서 게임이 종료되었음에도 그 게임을 진행한다.
게임 도중 게임판을 본 어느 순간 머쓱이는 본인이 실수를 했는지 의문이 생겼습니다. 혼자서 틱택토를 했기에 게임하는 과정을 지켜본 사람이 없어 이를 알 수는 없습니다. 그러나 게임판만 봤을 때 실제로 틱택토 규칙을 지켜서 진행했을 때 나올 수 있는 상황인지는 판단할 수 있을 것 같고 문제가 없다면 게임을 이어서 하려고 합니다.
머쓱이가 혼자서 게임을 진행하다 의문이 생긴 틱택토 게임판의 정보를 담고 있는 문자열 배열 board가 매개변수로 주어질 때, 이 게임판이 규칙을 지켜서 틱택토를 진행했을 때 나올 수 있는 게임 상황이면 1을 아니라면 0을 return 하는 solution 함수를 작성해 주세요.
제한사항
- board의 길이 = board[i]의 길이 = 3
- board의 원소는 모두 "O", "X", "."으로만 이루어져 있습니다.
- board[i][j]는 i + 1행 j + 1열에 해당하는 칸의 상태를 나타냅니다.
- "."은 빈칸을, "O"와 "X"는 해당 문자로 칸이 표시되어 있다는 의미입니다.
입출력 예
| board | result |
|---|---|
| ["O.X", ".O.", "..X"] | 1 |
| ["OOO", "...", "XXX"] | 0 |
| ["...", ".X.", "..."] | 0 |
| ["...", "...", "..."] | 1 |
입출력 예 설명
입출력 예 #1
- 예제 1번의 게임판은 다음과 같습니다.
O.X
.O.
..X선공 후공이 번갈아가면서 다음과 같이 놓았을 때 이러한 게임판이 나올 수 있습니다.
- 1행 1열 → 1행 3열 → 2행 2열 → 3행 3열
- 1행 1열 → 3행 3열 → 2행 2열 → 1행 3열
- 2행 2열 → 1행 3열 → 1행 1열 → 3행 3열
- 2행 2열 → 3행 3열 → 1행 1열 → 1행 3열
물론 위와 다르게 머쓱이가 2행 2열에 O, 3행 3열에 X, 1행 3열에 X, 1행 1열에 O 순서로 표시를 해서 실수를 했을 가능성도 있지만 "실수를 했을 가능성이 있는가"를 묻는 게 아닌 "이 게임판이 규칙을 지켜서 진행한 틱택토에서 나올 수 있는 상황인가"를 묻는 문제라는 것에 유의해주세요. 따라서 1을 return 합니다.
입출력 예 #2
- 예제 2번의 게임판은 다음과 같습니다.
OOO
...
XXX- 규칙을 지켜서 진행한 틱택토라면 선공과 후공이 번갈아가면서 각각 1행, 3행 중 두 칸씩에 표시를 한 뒤 5번째 차례에 선공이 1행에 가로로 3개의 O를 완성했을 때 종료되므로 적어도 머쓱이가 게임이 종료된 후에도 계속 진행하는 실수를 했다는 것을 추론해 볼 수 있고, 정상적인 틱택토에서는 이러한 상황이 나올 수 없습니다. 따라서 0을 return 합니다.
입출력 예 #3
- 예제 3번은 2행 2열에만 X가 표시가 되어있습니다. 선공 O 표시가 없이 X만 있으므로 머쓱이가 O를 표시해야 할 때 X를 표시하는 실수를 했다는 것을 추론해 볼 수 있고, 규칙을 지켜서 진행했을 때는 이러한 상황이 나올 수 없습니다. 따라서 0을 return 합니다.
입출력 예 #4
- 예제 4번은 빈 3x3 게임판입니다. 선공이 아직 빈칸에 표시하기 전에 이러한 상황이 나올 수 있습니다. 따라서 1을 return 합니다.
나의 풀이
package programmers;
public class Tictactoe {
static int MAX = 3;
static char[][] map;
public static boolean checkLine(char player) {
for(int i = 0; i < MAX; i++) {
// 가로줄 확인
if(map[i][0] == player && map[i][1] == player && map[i][2] == player) return true;
// 세로줄 확인
if(map[0][i] == player && map[1][i] == player && map[2][i] == player) return true;
}
// 대각선 확인
if(map[0][0] == player && map[1][1] == player && map[2][2] == player) return true;
if(map[0][2] == player && map[1][1] == player && map[2][0] == player) return true;
return false;
}
// 현재 게임 보드가 유효한지 검사하는 함수
public static boolean isValidMap() {
int Ocnt = 0;
int Xcnt = 0;
// 보드 전체를 순회하며 'O'와 'X'의 개수를 센다
for(int i = 0; i < MAX; i++) {
for(int j = 0; j < MAX; j++) {
if(map[i][j] == 'O') Ocnt++;
else if(map[i][j] == 'X') Xcnt++;
}
}
// 'O'가 없고 'X'만 있는 경우는 유효하지 않음
if (Ocnt == 0 && Xcnt > 0) return false;
// 'O'와 'X'의 개수 차이가 1을 초과하는 경우는 유효하지 않음
if(Math.abs(Ocnt - Xcnt) > 1) return false;
// 직선 검사
boolean oLine = checkLine('O');
boolean xLine = checkLine('X');
// 'O'와 'X'가 동시에 직선을 만든 경우는 유효하지 않음
if(oLine && xLine) return false;
// 'O'의 직선이 있는데 'O'의 개수가 'X'의 개수보다 하나 더 많지 않은 경우는 유효하지 않음
if(oLine && Ocnt != Xcnt + 1) return false;
// 'X'의 직선이 있는데 'O'와 'X'의 개수가 같지 않은 경우는 유효하지 않음
if(xLine && Ocnt != Xcnt) return false;
return true;
}
public static int solution(String[] boards) {
map = new char[MAX][MAX];
for(int i = 0; i < MAX; i++) {
for(int j = 0; j< MAX; j++) {
map[i][j] = boards[i].charAt(j);
}
}
System.out.println(isValidMap());
return isValidMap() ? 1 : 0;
}
public static void main(String[] args) {
String[] boards = {"OOO", "OOO", "OOO"};
solution(boards);
}
}
나의 생각
문제를 보고 처음에는 깊이우선탐색으로 모든 경우의 수를 다 확인해야하나 생각하였지만 이 문제에서 필요한 정보는 게임판이 나올수 있는 경우의 수가 아닌 게임판이 규칙을 지켜서 진행한 틱택토에서 나올 수 있는 상황인가를 확인하는 문제였다.
즉, 틱택토 게임에서 나올 수 있는 조건만 잘 확인한다면 구현으로도 충분히 문제를 풀 수 있겠다고 생각하였다. 문제를 보며 내가 생각한 내용은 다음과 같다.
1. 말판 개수 비교
- `O`와 `X`의 개수 차이가 1 이내인지 확인
- 선공, 후공 turn제 게임이기 때문에 `O`, `X`의 개수 차이가 1개 보다 높을 수 없다.
2. 직선 판단
- 게임 보드에서 `O`와 `X`가 이루는 직선을 찾음
3. 게임 상황에 따른 상세 조건 처리
- `O`와`X`의 개수, 직선의 존재 여부에 따라 게임 상황을 정확히 판단해야함
- `O`직선이 만들어진 경우, `X`의 개수는 `O`보다 하나 적어야함
- `O`가 선공이기때문에, `O`로 직선이 만들어진다면 `O`의 개수는 `X`개수 보다 하나 많다
- `X`직선이 만들어진 경우, `O`,`X`의 개수는 같아야함
- 마찬가지로, `X`가 후공이기때문에, O`,`X`의 개수는 같다로직은 다음과 같은 순서로 구현하였다.
- 매개변수로 주어지는 String[] 배열
boards의 정보를 바탕으로O의 개수,X의 개수 정보를 알아야한다.
map = new char[MAX][MAX];
for(int i = 0; i < MAX; i++) {
for(int j = 0; j< MAX; j++) {
map[i][j] = boards[i].charAt(j);
}
}나는 이를 위해 전역변수로 char[][] map 을 선언하였는데 이는 몇 가지 장점을 가지고 있다.
1. 클래스 내에서의 접근성 : 전역 변수로 선언된 map은 클래스 내의 모든 메소드에서 직접 접근할 수 있음. 이것은 다른 메서드에서 `map`을 파라미터로 전달할 필요가 없으므로 코드가 더 간결해지고 메소드 간의 인터페이스가 단순해짐
2. 상태 유지 : 전역 변수는 클래스의 인스턴스가 존재하는 동안 그 상태를 유지하는데, 한 메서드에서 `map`을 수정하면 다른 메소드에서도 이 변경 사항이 반영된다. 이것은 데이터를 여러 메소드에 걸쳐 공유하고 유지하는데 유용할 수 있음
3. 재사용성과 응집도 : `map`이 클래스의 여러 메소드에서 공통으로 사용되는 경우, 전역 변수로 선언함으로써 코드의 재사용성과 응집도를 향상시킬수 있음. 이는 관련 작업을 수행하는 메소드들이 `map`을 공유함으로써 서로 연관되어 있음을 명확하게 표현함
4. 메모리 관리 : `map`이 프로그램 실행 동안 계속 필요한 경우, 한 번만 메모리에 할당하여 여러 메소드에서 사용할 수있음. 이것은 필요할 때마다 `map`을 새로 생성하고 소멸시키는 것보다 메모리 사용 측면에서 효율적일 수 있음- 전역변수로 활용할 것인가, 본인은
map배열을 선언하여 저장 공간 소모 및 오버헤드(추가적인 시간, 메모리, 또는 기타 리소스)를 줄이겠다라고 생각하면 사용하지 않는 간단한 방법도 물론 존재한다.
for (int i = 0; i < MAX; i++) {
for (int j = 0; j < MAX; j++) {
if (boards[i].charAt(j) == 'O') Ocnt++;
else if (boards[i].charAt(j) == 'X') Xcnt++;
}
}- 현재
틱택토게임 보드가 유효한가?
유효성을 검사 항목
O가 없고 X만 있는 경우 유효하지 않음
O와 X의 개수 차이가 1을 초과하는 경우 유효하지 않음
O와 X가 동시에 직선을 만든 경우는 유효하지 않음
O의 직선이 있는데, O의 개수가 X의 개수보다 하나 더 많지 않은 경우는 유효하지 않음
X의 직선이 있는데, O와 X의 개수가 같이 않는 경우는 유효하지 않음위 검사 항목을 로직으로 구현한 결과는 다음과 같다.
// 현재 게임 보드가 유효한지 검사하는 함수
public static boolean isValidMap() {
int Ocnt = 0;
int Xcnt = 0;
// 보드 전체를 순회하며 'O'와 'X'의 개수를 센다
for(int i = 0; i < MAX; i++) {
for(int j = 0; j < MAX; j++) {
if(map[i][j] == 'O') Ocnt++;
else if(map[i][j] == 'X') Xcnt++;
}
}
// 'O'가 없고 'X'만 있는 경우는 유효하지 않음
if (Ocnt == 0 && Xcnt > 0) return false;
// 'O'와 'X'의 개수 차이가 1을 초과하는 경우는 유효하지 않음
if(Math.abs(Ocnt - Xcnt) > 1) return false;
// 직선 검사
boolean oLine = checkLine('O');
boolean xLine = checkLine('X');
// 'O'와 'X'가 동시에 직선을 만든 경우는 유효하지 않음
if(oLine && xLine) return false;
// 'O'의 직선이 있는데 'O'의 개수가 'X'의 개수보다 하나 더 많지 않은 경우는 유효하지 않음
if(oLine && Ocnt != Xcnt + 1) return false;
// 'X'의 직선이 있는데 'O'와 'X'의 개수가 같지 않은 경우는 유효하지 않음
if(xLine && Ocnt != Xcnt) return false;
return true;
}- 직선인가를 어떻게 판단할 것인가??
보통 현재 항목과 다음 항목과 비교를 위해서 dfs로 연결되는지 확인을 하는 방법이 주로 쓰이지만 이번 로직에서는 위에서 언급한대로 모든 경우를 찾는게 아닌, 그래서 이 틱택토 맵이 나올 수 있는냐? 이기때문에 가로, 세로, 대각선을 확인하는 로직을 구현하였다.
public static boolean checkLine(char player) {
for(int i = 0; i < MAX; i++) {
// 가로줄 확인
if(map[i][0] == player && map[i][1] == player && map[i][2] == player) return true;
// 세로줄 확인
if(map[0][i] == player && map[1][i] == player && map[2][i] == player) return true;
}
// 대각선 확인
if(map[0][0] == player && map[1][1] == player && map[2][2] == player) return true;
if(map[0][2] == player && map[1][1] == player && map[2][0] == player) return true;
return false;
}숫자 블록
문5) 그렙시에는 숫자 0이 적힌 블록들이 설치된 도로에 다른 숫자가 적힌 블록들을 설치하기로 하였습니다. 숫자 블록을 설치하는 규칙은 다음과 같습니다.
블록에 적힌 번호가 n 일 때, 가장 첫 블록은 n * 2번째 위치에 설치합니다. 그 다음은 n * 3, 그 다음은 n * 4, ...위치에 설치합니다. 기존에 설치된 블록은 빼고 새로운 블록을 집어넣습니다.
블록은 1이 적힌 블록부터 숫자를 1씩 증가시키며 순서대로 설치합니다. 예를 들어 1이 적힌 블록은 2, 3, 4, 5, ... 인 위치에 우선 설치합니다. 그 다음 2가 적힌 블록은 4, 6, 8, 10, ... 인 위치에 설치하고, 3이 적힌 블록은 6, 9, 12... 인 위치에 설치합니다.
이렇게 3이 적힌 블록까지 설치하고 나면 첫 10개의 블록에 적힌 번호는 [0, 1, 1, 2, 1, 3, 1, 2, 3, 2]가 됩니다.
그렙시는 길이가 1,000,000,000인 도로에 1부터 10,000,000까지의 숫자가 적힌 블록들을 이용해 위의 규칙대로 모두 설치 했습니다.
그렙시의 시장님은 특정 구간에 어떤 블록이 깔려 있는지 알고 싶습니다.
구간을 나타내는 두 정수 begin, end 가 매개변수로 주어 질 때, 그 구간에 깔려 있는 블록의 숫자 배열을 return하는 solution 함수를 완성해 주세요.
제한 사항
- 1 ≤ begin ≤ end ≤ 1,000,000,000
- end - begin ≤ 5,000
입출력 예
| begin | end | result |
|---|---|---|
1 | 10 | [0, 1, 1, 2, 1, 3, 1, 4, 3, 5] |
입출력 예 #1
다음과 같이 블럭이 깔리게 됩니다.
나의 풀이
처음 구현했던 로직(실패)
package programmers;
import java.util.Arrays;
import java.util.LinkedHashMap;
import java.util.Map;
public class NumberBlocks {
static long N;
static long M;
static Map<Long, Long> map ;
public static int[] solution(long begin, long end) {
N = end;
M = end / 2;
map = new LinkedHashMap<>();
for(long k = 1; k <= begin; k++) {
map.put(k, 0L);
}
for(long i = 1; i <= M; i++) {
for(long j = i; j <= N; j+=i) {
if (j != i) {
map.put(j, i);
}
}
}
int[] answer = new int[map.size()];
int cnt = 0;
for(long value : map.values()) {
answer[cnt++] = (int)value;
}
return answer;
}
public static void main(String[] args) {
long begin = 1;
long end = 10;
solution(begin, end);
}
}
효율성 시간초과 로직 (실패)
package programmers;
public class NumberBlocks {
public static int getBlockValue(long blockNumber) {
if(blockNumber == 1) return 0;
for (long i = 2; i * i <= blockNumber; i++) {
if (blockNumber % i == 0 && blockNumber / i <= 10000000) {
return (int)(blockNumber / i);
}
}
return 1;
}
public static int[] solution(long begin, long end) {
int[] answer = new int[(int)(end - begin) + 1];
for(long i = begin; i <= end; i++) {
answer[(int)(i - begin)] = getBlockValue(i);
}
return answer;
}
public static void main(String[] args) {
long begin = 1;
long end = 10;
solution(begin, end);
}
}
효율성을 통과한 정답 로직
package programmers;
public class NumberBlocks {
public static int[] solution(long begin, long end) {
int[] answer = new int[(int)(end - begin) + 1];
for (int i = 0; i < answer.length; i++) {
long blockNumber = begin + i;
for (long j = 2; j * j <= blockNumber; j++) {
if (blockNumber % j == 0) {
if(blockNumber / j > 10000000) {
answer[i] = (int) j;
continue;
}else {
answer[i] = (int) (blockNumber / j);
}
break;
}
}
if(answer[i] == 0) answer[i] = 1;
}
if(begin == 1) answer[0] = 0;
return answer;
}
public static void main(String[] args) {
long begin = 1;
long end = 10;
solution(begin, end);
}
}
나의 생각
표를 보면서 뭔가 규칙이 있지않을까 유심히 관찰하였다.
2,3,5,7 에는 숫자 1로 고정되어 있고, 4,6,8,9,10은 숫자가 증가하는데 뭔가 약수로 채워진다는 느낌을 받았다. 이를 바탕으로 소수인 블록은 숫자가 고정적으로 1로 채워지고,
소수가 아닌 블록은 자기자신의 수를 제외하고 가장 큰 수가 채워진다.
예를들어, 10이 적힌 블록이 있다고 하면, 10의 약수(자기 자신은 제외) {1,2,5}인데
1 * 10 = 1로 갱신
2 * 5 = 2로 갱신
5 * 2 = 5로 갱신
----------------
- 10 * 2 = 20 번째 위치에 배치되기 때문에 (10을 초과)따라서 위 내용을 정리해보면 아래와 같다.
배치 규칙: 숫자 n이 적힌 블록은 n * 2, n * 3, n * 4, ... 위치에 배치된다. 즉, 각 숫자 블록은 자신의 배수 위치에 순서대로 배치
숫자 블록의 범위: 숫자 블록에 적힐 수 있는 숫자는 1부터 시작하여 10,000,000까지
이는 블록에 배치될 수 있는 숫자의 최대 크기를 나타낸다
블록의 갱신: 뒤에 배치되는 숫자 블록이 먼저 배치된 블록을 대체한다.
이는 블록이 배치되는 위치에 이미 다른 숫자 블록이 있으면,
그 블록은 새로 배치되는 블록으로 갱신된다는 의미
이 규칙에 따라, 특정 위치 a에 배치되는 숫자 블록은 "위치 a의 약수 중
자신을 제외하고 10,000,000 이하인 가장 큰 수"가 된다.
예를 들어, 10번째 위치에 배치될 수 있는 숫자 블록은 1, 2, 5가 된다.
하지만 1은 10 * 1 위치, 2는 5 * 2 위치, 5는 2 * 5 위치에 배치되므로,
최종적으로 10번째 위치에는 가장 큰 숫자인 5가 배치된다.
결론적으로, 주어진 위치의 최대 10,000,000 이하의 가장 큰 약수가 해당 위치에 배치될 숫자이다. 고찰
처음에 이 문제를 접했을 때, 매개변수 long타입이라는 것을 보고 int 범위를 초과하는 수가 들어올 수 있으므로 로직을 가능한 한 단순하게 구성해야겠다고 생각했다. 그러나 초기에 구현한 로직은 1부터 10,000,000 범위의 숫자에 대해 모든 배수를 계산하고 맵에 저장하는 방식을 채택하였다. 이 접근 방식은 불필요한 계산과 메모리 사용을 많이 필요로 했다. 사실, 맵 자료 구조보다 int[] answer 배열을 직접 활용하는 방식이 더 직관적이고 효율적이였다. 하지만 문제의 핵심 규칙성을 파악하기 전까지, 단순히 구현에만 집중하고 문제의 실제 요구사항과 효율적인 접근 방식에 대해 충분히 고민을 하지 않았던것 같다.
앞으로는 문제를 해결하기 전에 먼저 그 규칙성과 요구사항을 철저히 분석하는 것의 중요성을 깊이 인식하게 되었다. 특히, 문제의 맥락과 제한 사항을 면밀히 고려하여 가능한 가장 효율적이고 간결한 솔루션을 설계하는데 더 많은 시간을 할애해야겠다.
