DailyCoding
key값과 value값을 쌍으로 갖고있는 2차원 배열을 입력받아
Hashmap으로 바꾸시오.
import java.util.HashMap;
public class ArrayToHashmap {
public HashMap<String, String> convertListToHashMap(String[][] arr) {
HashMap<String,String> result = new HashMap<String,String>();
if(arr.length==0 || arr[0].length==0){
return result;
}else {
for (int i = 0; i < arr.length; i++) {
if (!result.containsKey(arr[i][0]))
result.put(arr[i][0], arr[i][1]);
}
return result;
}
}
}
Section2 - 코테준비Quiz
1. 박스에 물건 넣기
물건을 박스에 넣으려 한다.
박스에 최대수용 무게는 limit로 입력받고 각 물건의 무게는 배열행태로 입력받는다.
- 박스에 최대 2개의 물건을 넣을 수 있음
- 물건의 무게는 40 이상 240 이하
- limit는 물건1개의 무게보다 무조건 크게 주어진다.
import java.util.Arrays;
public class CarryingLuggage {
int count =0;
private static int[] remove(int[] arr, int index) { // 배열의 특정 인덱스 지우는 메서드
if (arr == null || index < 0 || index >= arr.length) {
return arr;
}
int[] result = new int[arr.length - 1];
int copyIndex = 0;
for (int i = 0; i < arr.length; i++) {
if (i == index) {
continue;
}
result[copyIndex++] = arr[i];
}
return result;
}
private static int[] remove(int[] arr, int index, int index2) { // 배열의 특정 인덱스 지우는 메서드
if (arr == null || index < 0 || index >= arr.length) {
return arr;
}
int[] result = new int[arr.length - 2];
int copyIndex = 0;
for (int i = 0; i < arr.length; i++) {
if (i == index || i == index2) {
continue;
}
result[copyIndex++] = arr[i];
}
return result;
}
public int movingStuff(int[] stuff, int limit) {
// Greedy 알고리즘으로 풀어보자.
// stuff 배열 요소를 탐색해 limit에 가까운 조합 먼저 한박스 완성
// 조합방법 = 특정 요소를 기준으로 합이 limit인게 있는지 검사, 있으면 조합하고 해당요소들 사용했다고 체크, 없으면 limit-1이 있는지 검사
// 남은 애들끼리 또 조합해 박스 완성하기를 반복
// stuff가 없으면 끝
// boolean을 이용하지 않고 사용한 요소값을 삭제하면서 재귀 돌려도 될듯
// for문*재귀방법 , 이중for문 어차피 시간복잡도는 똑같을 듯? << 맞나?
// boolean[] used = new boolean[stuff.length];
//
// for(int i =0; i<stuff.length; i++) {
// if(used[i]==false){
//
// }
// }
int[] arr = stuff.clone(); // 기존값 안바뀌게 깊은복사
//System.out.println(Arrays.toString(arr));
//arr[0]랑 나머지 요소 합 구하기
// 구한 합을 limit랑 비교
// System.out.println(Arrays.toString(arr));
// System.out.println(count);
for (int l = 0; l < arr.length; l++) { // 짝이 생길 가능성이 없는애들 먼저 빼주기
if (arr[l] > limit - 40) {
count++;
arr = remove(arr, l);
if (arr.length == 0) break;
movingStuff(arr, limit);
}
}
if (arr.length != 0) {
for (int j = 0; j < arr.length - 1; j++) {
for (int k = j + 1; k < arr.length; k++) {
int sum = arr[j] + arr[k]; //stuff요소는 40이상이라 가능
for (int i = 0; i < limit; i++) {
if (sum == limit - i) {
count++;
arr = remove(arr, j, k);
if (arr.length == 0) break;
movingStuff(arr, limit);
break;
}
}
if (arr.length == 0) break; //arr.length==0인데 불필요하게 돌지 않게 하기위해 써줌
}
if (arr.length == 0) break;
}
}
System.out.println(Arrays.toString(arr));
System.out.println(count);
return count;
}
}
//입력
carryingLuggage.movingStuff(new int[]{60, 80, 120, 135}, 140);
//출력
[]
3
[]
4
[]
6
[135]
6count가3일 때 arr은 빈배열이 돼서 아무것도 안하고 종료가 되어야 하는데... 이상하게 계속 돌다가 갑자기 arr에 135가 추가된다.
private static int[] remove(int[] arr, int index) { // 배열의 특정 인덱스 지우는 메서드
if (arr == null || index < 0 || index >= arr.length) {
return arr;
}
int[] result = new int[arr.length - 1];
int copyIndex = 0;
for (int i = 0; i < arr.length; i++) {
if (i == index) {
continue;
}
result[copyIndex++] = arr[i];
}
return result;
}
private static int[] remove(int[] arr, int index, int index2) { // 배열의 특정 인덱스 지우는 메서드
if (arr == null || index < 0 || index >= arr.length) {
return arr;
}
int[] result = new int[arr.length - 2];
int copyIndex = 0;
for (int i = 0; i < arr.length; i++) {
if (i == index || i == index2) {
continue;
}
result[copyIndex++] = arr[i];
}
return result;
}
public int movingStuff(int[] stuff, int limit) {
// Greedy 알고리즘으로 풀어보자.
// stuff 배열 요소를 탐색해 limit에 가까운 조합 먼저 한박스 완성
// 조합방법 = 특정 요소를 기준으로 합이 limit인게 있는지 검사, 있으면 조합하고 해당요소들 사용했다고 체크, 없으면 limit-1이 있는지 검사
// 남은 애들끼리 또 조합해 박스 완성하기를 반복
// stuff가 없으면 끝
// boolean을 이용하지 않고 사용한 요소값을 삭제하면서 재귀 돌려도 될듯
// for문*재귀방법 , 이중for문 어차피 시간복잡도는 똑같을 듯? << 맞나?
// boolean[] used = new boolean[stuff.length];
//
// for(int i =0; i<stuff.length; i++) {
// if(used[i]==false){
//
// }
// }
int[] arr = stuff.clone(); // 기존값 안바뀌게 깊은복사
//System.out.println(Arrays.toString(arr));
//arr[0]랑 나머지 요소 합 구하기
// 구한 합을 limit랑 비교
// System.out.println(Arrays.toString(arr));
// System.out.println(count);
for (int l = 0; l < arr.length; l++) { // 짝이 생길 가능성이 없는애들 먼저 빼주기
if (arr[l] > limit - 40) {
count++;
arr = remove(arr, l);
--l; // arr가 바뀌니까 넣어줘야 함
if (arr.length == 0) break;
}
}
if (arr.length != 0) {
for (int j = 0; j < arr.length - 1; j++) {
for (int k = j + 1; k < arr.length; k++) {
int sum = arr[j] + arr[k]; //stuff요소는 40이상이라 가능
for (int i = 0; i < limit; i++) {
if (sum == limit - i) {
count++;
arr = remove(arr, j, k);
--j;
--k;
System.out.println(Arrays.toString(arr));
if (arr.length == 0) break;
System.out.println(Arrays.toString(arr));
break;
}
}
if (arr.length == 0) break; //arr.length==0인데 불필요하게 돌지 않게 하기위해 써줌
}
if (arr.length == 0) break;
}
}
// System.out.println(Arrays.toString(arr));
System.out.println(count);
return count;
}굳이 재귀를 쓸 필요 없게 기능을 구현하고서는 지우지를 않았다...
이제 위 코드가 의도한데로 동작하기는 하지만 또 문제가 있다.
j가 0일 때 sum == limit - i조건을 만족해 버리면
k for문의 나머지를 수행하는 과정에서 j가 음수가 된다.
arr가 반복문을 수행하는 과정에서 계속 변해서 예상치 못한 변수가 생길 확률이 높아보인다. 따라서 boolean을 이용해서 다시 해봤다.
import java.util.Arrays;
public class CarryingLuggage {
int count =0;
private static int[] remove(int[] arr, int index) { // 배열의 특정 인덱스 지우는 메서드
if (arr == null || index < 0 || index >= arr.length) {
return arr;
}
int[] result = new int[arr.length - 1];
int copyIndex = 0;
for (int i = 0; i < arr.length; i++) {
if (i == index) {
continue;
}
result[copyIndex++] = arr[i];
}
return result;
}
public int movingStuff(int[] stuff, int limit) {
// Greedy 알고리즘으로 풀어보자.
// stuff 배열 요소를 탐색해 limit에 가까운 조합 먼저 한박스 완성
// 조합방법 = 특정 요소를 기준으로 합이 limit인게 있는지 검사, 있으면 조합하고 해당요소들 사용했다고 체크, 없으면 limit-1이 있는지 검사
// 남은 애들끼리 또 조합해 박스 완성하기를 반복
// stuff가 없으면 끝
// boolean을 이용하지 않고 사용한 요소값을 삭제하면서 재귀 돌려도 될듯 (boolean 안쓰면 배열 길이가 계속 바껴서 더 복잡함..)
// for문*재귀방법 , 이중for문 어차피 시간복잡도는 똑같을 듯? << 맞나?
int[] arr = stuff.clone(); // 기존값 안바뀌게 깊은복사
for (int l = 0; l < arr.length; l++) { // 짝이 생길 가능성이 없는애들 먼저 빼주기
int aaa = limit-arr[l];
boolean have = false;
if(aaa>=40){
for(int m=0; m<arr.length; m++){
if(m!=l && arr[m]<=aaa){ // 툭정요소가 limit와의 차이가 40이상이라도 그 차이 이하의 값을 갖는 요소가 없으면 함께 박스에 들어갈 수 있는 요소가 없음
have = true; // 따라서 함께 박스에 들어갈 경우의 수가 존재하는지 체크하는 것
}
}
}
//System.out.println(!have);
if (arr[l] > limit - 40 || !have) { // stuff 요소는 40이상이니 특정 요소가 limit와의 차이가 40미만이면 무조건 혼자 박스에 들어갈 수 밖에 없음
count++;
arr = remove(arr, l);
--l; // arr가 바뀌니까 넣어줘야 함
if (arr.length == 0) break;
}
}
int num = 0;
for(int i = 0; i < arr.length-1; i++ ) { // arr 요소들을 크기순으로 정렬
for (int j = i+1; j < arr.length; j++ ) {
if(arr[j] > arr[i]) {
num = arr[j];
arr[j] = arr[i];
arr[i] = num;
}
}
}
int rest = 0;
boolean[] used = new boolean[arr.length];
if (arr.length != 0) { // 혹시나 물건1개 당 1개의 물건만 들어가게 될 경우를 방지하기 위함
for (int i = 0; i < arr.length - 1; i++) {
if (used[i] == false) {
for (int j = i + 1; j < arr.length; j++) {
if(used[j]==false) {
int sum = arr[j] + arr[i];
rest = limit - sum;
if (rest >= 0) {
count++;
used[i] = true;
used[j] = true;
System.out.println(Arrays.toString(used));
System.out.println(Arrays.toString(arr));
System.out.println(count);
break;
}
}
}
}
}
}
// System.out.println(Arrays.toString(arr));
System.out.println(count);
return count;
}
}
//입력
{60, 73, 80, 87, 103, 109, 119, 123, 128, 129, 136, 146, 153, 168, 182}, 200
//출력
[true, false, false, false, false, false, false, false, false, false, true]
[136, 129, 128, 123, 119, 109, 103, 87, 80, 73, 60]
5
[true, false, false, true, false, false, false, false, false, true, true]
[136, 129, 128, 123, 119, 109, 103, 87, 80, 73, 60]
6
[true, false, false, true, true, false, false, false, true, true, true]
[136, 129, 128, 123, 119, 109, 103, 87, 80, 73, 60]
7
[true, false, false, true, true, true, false, true, true, true, true]
[136, 129, 128, 123, 119, 109, 103, 87, 80, 73, 60]
8
8
위 경우 11이 나와야 하는데 8이 나왔다.
요소끼리 짝짓다 보면 남는 애들이 생기는 것을 볼 수 있다.
남은 애들만큼 ++해줘야겠다.
import java.util.Arrays;
public class CarryingLuggage {
int count =0;
private static int[] remove(int[] arr, int index) { // 배열의 특정 인덱스 지우는 메서드
if (arr == null || index < 0 || index >= arr.length) {
return arr;
}
int[] result = new int[arr.length - 1];
int copyIndex = 0;
for (int i = 0; i < arr.length; i++) {
if (i == index) {
continue;
}
result[copyIndex++] = arr[i];
}
return result;
}
public int movingStuff(int[] stuff, int limit) {
// Greedy 알고리즘으로 풀어보자.
// stuff 배열 요소를 탐색해 limit에 가까운 조합 먼저 한박스 완성
// 조합방법 = 특정 요소를 기준으로 합이 limit인게 있는지 검사, 있으면 조합하고 해당요소들 사용했다고 체크, 없으면 limit-1이 있는지 검사
// 남은 애들끼리 또 조합해 박스 완성하기를 반복
// stuff가 없으면 끝
// boolean을 이용하지 않고 사용한 요소값을 삭제하면서 재귀 돌려도 될듯 (boolean 안쓰면 배열 길이가 계속 바껴서 더 복잡함..)
// for문*재귀방법 , 이중for문 어차피 시간복잡도는 똑같을 듯? << 맞나?
int[] arr = stuff.clone(); // 기존값 안바뀌게 깊은복사
for (int l = 0; l < arr.length; l++) { // 짝이 생길 가능성이 없는애들 먼저 빼주기
int aaa = limit-arr[l];
boolean have = false;
if(aaa>=40){
for(int m=0; m<arr.length; m++){
if(m!=l && arr[m]<=aaa){ // 툭정요소가 limit와의 차이가 40이상이라도 그 차이 이하의 값을 갖는 요소가 없으면 함께 박스에 들어갈 수 있는 요소가 없음
have = true; // 따라서 함께 박스에 들어갈 경우의 수가 존재하는지 체크하는 것
}
}
}
//System.out.println(!have);
if (arr[l] > limit - 40 || !have) { // stuff 요소는 40이상이니 특정 요소가 limit와의 차이가 40미만이면 무조건 혼자 박스에 들어갈 수 밖에 없음
count++;
arr = remove(arr, l);
--l; // arr가 바뀌니까 넣어줘야 함
if (arr.length == 0) break;
}
}
int num = 0;
for(int i = 0; i < arr.length-1; i++ ) { // arr 요소들을 크기순으로 정렬
for (int j = i+1; j < arr.length; j++ ) {
if(arr[j] > arr[i]) {
num = arr[j];
arr[j] = arr[i];
arr[i] = num;
}
}
}
int rest = 0;
boolean[] used = new boolean[arr.length];
if (arr.length != 0) { // 혹시나 물건1개 당 1개의 물건만 들어가게 될 경우를 방지하기 위함
for (int i = 0; i < arr.length - 1; i++) {
if (used[i] == false) {
for (int j = i + 1; j < arr.length; j++) {
if(used[j]==false) {
int sum = arr[j] + arr[i];
rest = limit - sum;
if (rest >= 0) {
count++;
used[i] = true;
used[j] = true;
System.out.println(Arrays.toString(used));
System.out.println(Arrays.toString(arr));
System.out.println(count);
break;
}
}
}
}
}
}
///////////////////////////////추가///////////////////////////////////
for(boolean o:used){ // 짝짓고 남은애들 처리
if(o==false) {
count++;
}
}
///////////////////////////////추가///////////////////////////////////
System.out.println(count);
return count;
}
}
모든 테스트 케이스 통과.
박스 하나에 물건 2개까지 밖에 안들어간다는 것을 뒤늦게 발견해 한참 고민했다...
Arrays.sort(arr, Collections.reverseOrder()); sort메소드를 사용하면 더 간단하게 정렬할 수 있었다.
import java.util.*;
public class Solution {
public int movingStuff(int[] stuff, int limit) {
int twoStuff = 0;
// 짐을 무게순으로 오름차순 정렬
Arrays.sort(stuff);
// 가장 가벼운 짐의 인덱스
int leftIdx = 0;
// 가장 무거운 짐의 인덱스
int rightIdx = stuff.length - 1;
while(leftIdx < rightIdx) {
// 가장 가벼운 짐과 무거운 짐의 합이 limit 보다 작거나 같으면 2개를 한번에 나를 수 있다
if(stuff[leftIdx] + stuff[rightIdx] <= limit) {
// 다음 짐을 확인하기 위해 가장 가벼운 짐과 무거운 짐을 가리키는 인덱스를 옮겨주고
// 한번에 2개 옮길 수 있는 개수를 +1 해준다
leftIdx++;
rightIdx--;
twoStuff++;
} else {
// 위 조건에 맞지 않는 경우는 한번에 한 개만 나를 수 있는 경우이기 때문에
// 가장 무거운 짐의 인덱스만 옮겨준다
rightIdx--;
}
}
// 전체 짐의 개수에서 한번에 2개를 나를 수 있는 경우를 빼 주면 총 필요한 박스의 개수를 구할 수 있다
return stuff.length - twoStuff;
}
}
시간복잡도를 더 줄일 수 있었다.
(cf. 만약에 한박스에 들어갈 수 있는 물건의 갯수에 제한이 없다면 greedy방식으로는 힘들고 완전탐색을 해야한다. 맨 처음 시도했던 방법과 유사하게 재귀를 이용해야하는데, 배열을 바꾸는 것 뿐만이 아니라 limit의 나머지를 이용해 다시 더해질 수 있는 물건이 있는지 탐색하면 될 것 같다.)
2. 동전 거슬러주기
입력받는 k원만큼 돈을 거슬러줘야한다. 최소한의 동전 갯수로 거슬러주고 몇개의 동전을 거슬러 줬는지 출력하라.
- 동전의 종류는 1원, 5원, 10원, 50원, 100원, 500원이 있다.
나의풀이
public class ChangeOfCoin {
public int partTimeJob(int k) { // k원만큼 동전으로 거슬러주기
int count =0;
int sum =0;
int[] coin = {500, 100, 50, 10, 5 ,1};
for(int o : coin){
if(k%o==0) {
while(!(sum==k)){
sum += o;
count++;
}
}else{
while(!(sum>k-o)){
sum += o;
count++;
}
}
}
return count;
}
}
ans
import java.util.*;
public class Solution {
public int partTimeJob(int k) {
int result = 0;
//동전의 종류를 배열에 넣어준 이후
int[] wallet = new int[]{500, 100, 50, 10, 5, 1};
//해당 동전의 종류만큼 배열을 순회합니다.
for(int i = 0; i < wallet.length; i++) {
//총 금액이 0보다 클때마다
if(k > 0) {
//총 금액을 현재 동전으로 나눈 수를 구합니다(해당 동전의 총 갯수)
int sum = (int)Math.floor((double)k / wallet[i]);
//해당 동전의 갯수를 결과에 더해준 이후
result = result + sum;
//총 금액을 사용한 동전의 금액만큼 차감합니다.
k = k - (wallet[i] * sum);
}
}
//결과를 반환합니다.
return result;
}
}for문을 한번만 사용하니 시간복잡도 면에서 답지가 더 좋은 코드인 것 같다.
3. 보드게임 구현
(문제 저작권 때문에 구체적인 게임 규칙 언급 불가)
수도코드
1. boolean을 이용해 board의 요소를 모두 false로 만든 뒤 말의 위치를 true로 바꿔 위치를 확인할 수 있도록 한다.
-
말이 움직이게 하는 기능 구현.
-
말이 움직여도착한 곳의 값을 확인해 점수(score)에 더해주기
-
범위 밖으로 이동하려하면 그 즉시 게임종료, return null
import java.util.Arrays;
public class BoardGame {
int index1 = 0;
int index2 = 0;
int findTrue = 0;
public Integer boardGame(int[][] board, String operation) {
// 움직이는 말의 위치를 boolean을 통해 확인
// 문자열 각 인덱스에 따라 말 이동
// 정해진 범위 밖(배열밖)으로 이동하려 할 시 오류 나올거임. 그때 try catch로 예외처리해서 바로 null리턴하게 만들면 됨
boolean[][] location = new boolean[board.length][board[0].length]; // board가 정사각형이라는 보장이 없으면 for문 돌리면 됨.
int score = 0;
location[0][0] = true;
boolean indexTrue = true;
for(int i=0; i<operation.length(); i++){
try {
location = move(location, operation.charAt(i));
}finally{
for (int j = 0; j < location.length; j++) {
findTrue = Arrays.asList(location[j]).indexOf(true); // 말의 위치 index 찾기
if (findTrue != -1) {
index2 = findTrue;
index1 = j;
break;
}
}
if (index1>=0 && index2>=0 && board[index1][index2] != 0) {
score += board[index1][index2];
}else if (index1<0 || index2<0) return null;
}
}
return score;
}
private boolean[][] move(boolean[][] moved,char mo){
print(moved);
System.out.println(mo);
if(mo=='U'){
for(int j=0; j<moved.length; j++) { // 현재 위치 탐색
findTrue = Arrays.asList(moved[j]).indexOf(true); // 말의 위치 index 찾기
if(findTrue!=-1) {
index2 = findTrue;
index1 = j;
break;
}
}
moved[index1][index2] = false;
index1=index1-1;
moved[index1][index2] = true;
}else if(mo=='D') {
for (int j = 0; j < moved.length; j++) { // 현재 위치 탐색
findTrue = Arrays.asList(moved[j]).indexOf(true); // 말의 위치 index 찾기
if (findTrue != -1) {
index1 = j;
index2 = findTrue;
break;
}
}
moved[index1][index2] = false;
index1=index1+1;
moved[index1][index2] = true;
}else if(mo=='L') {
for (int j = 0; j < moved.length; j++) { // 현재 위치 탐색
findTrue = Arrays.asList(moved[j]).indexOf(true); // 말의 위치 index 찾기
if (findTrue != -1) {
index1 = j;
index2 = findTrue;
break;
}
}
moved[index1][index2] = false;
index2=index2-1;
moved[index1][index2] = true;
}else if(mo=='R') {
for (int j = 0; j < moved.length; j++) { // 현재 위치 탐색
findTrue = Arrays.asList(moved[j]).indexOf(true); // 말의 위치 index 찾기
if (findTrue != -1) {
index1 = j;
index2 = findTrue;
break;
}
}
moved[index1][index2] = false;
index2=index2+1;
moved[index1][index2] = true;
}
System.out.println(index2);
return moved;
}
private void print(boolean[][] arr){
for(int i=0;i<arr.length;i++) {
System.out.println(Arrays.toString(arr[i]));
}
}
}
//입력
System.out.println("-------------board1-------------");
System.out.println(boardGame.boardGame(board1,"RRDLLD")); // 4
System.out.println("-------------board2-------------");
System.out.println(boardGame.boardGame(board2,"UUUDD")); // null
System.out.println("-------------board3-------------");
System.out.println(boardGame.boardGame(board3,"DDRRRUDUDUD")); // 0
System.out.println("-------------end-------------");
//출력
[true, false, false, false]
[false, false, false, false]
[false, false, false, false]
[false, false, false, false]
R
1
[false, true, false, false]
[false, false, false, false]
[false, false, false, false]
[false, false, false, false]
R
2
[false, false, true, false]
[false, false, false, false]
[false, false, false, false]
[false, false, false, false]
D
2
[false, false, false, false]
[false, false, true, false]
[false, false, false, false]
[false, false, false, false]
L
1
[false, false, false, false]
[false, true, false, false]
[false, false, false, false]
[false, false, false, false]
L
0
[false, false, false, false]
[true, false, false, false]
[false, false, false, false]
[false, false, false, false]
D
0
4
-------------board2-------------
[true, false, false]
[false, false, false]
[false, false, false]
U
0
[true, false, false]
[true, false, false]
[false, false, false]
U
0
[true, false, false]
[false, false, false]
[false, false, false]
U
null
-------------board3-------------
[true, false, false, false, false]
[false, false, false, false, false]
[false, false, false, false, false]
[false, false, false, false, false]
[false, false, false, false, false]
D
null
-------------end-------------예시케이스 1,2번은 문제가 없는데 3번에서 문제가 발생했다.
3번만 확인하기 위해 board1,2 input을 주석처리해 봤더니
아래와 같이 board3의 결과가 제대로 나온다.
[true, false, false, false, false]
[false, false, false, false, false]
[false, false, false, false, false]
[false, false, false, false, false]
[false, false, false, false, false]
D
0
[false, false, false, false, false]
[true, false, false, false, false]
[false, false, false, false, false]
[false, false, false, false, false]
[false, false, false, false, false]
D
0
[false, false, false, false, false]
[false, false, false, false, false]
[true, false, false, false, false]
[false, false, false, false, false]
[false, false, false, false, false]
R
1
[false, false, false, false, false]
[false, false, false, false, false]
[false, true, false, false, false]
[false, false, false, false, false]
[false, false, false, false, false]
R
2
[false, false, false, false, false]
[false, false, false, false, false]
[false, false, true, false, false]
[false, false, false, false, false]
[false, false, false, false, false]
R
3
[false, false, false, false, false]
[false, false, false, false, false]
[false, false, false, true, false]
[false, false, false, false, false]
[false, false, false, false, false]
U
3
[false, false, false, false, false]
[false, false, false, true, false]
[false, false, false, false, false]
[false, false, false, false, false]
[false, false, false, false, false]
D
3
[false, false, false, false, false]
[false, false, false, false, false]
[false, false, false, true, false]
[false, false, false, false, false]
[false, false, false, false, false]
U
3
[false, false, false, false, false]
[false, false, false, true, false]
[false, false, false, false, false]
[false, false, false, false, false]
[false, false, false, false, false]
D
3
[false, false, false, false, false]
[false, false, false, false, false]
[false, false, false, true, false]
[false, false, false, false, false]
[false, false, false, false, false]
U
3
[false, false, false, false, false]
[false, false, false, true, false]
[false, false, false, false, false]
[false, false, false, false, false]
[false, false, false, false, false]
D
3
0
-------------end-------------위 결과를 통해 board2의 수행과정이 board3에 영향을 줬다는 것을 알 수 있다.
클래스 변수들을 전부 private접근제안자를 추가해봤지만 같은 문제가 반복되었고 boardGame 메서드가 시작될 때 클래스변수들을 초기화해줘서 문제를 해결할 수 있었다.
(board2 기능수행 중 index1가 -1로 할당되었고 그 값이 그대로 남아있어 board3이 제대로 수행하지 않았던거였다.)
import java.util.Arrays;
public class BoardGame {
private int index1 = 0;
private int index2 = 0;
private int findTrue = 0;
public Integer boardGame(int[][] board, String operation) {
// 움직이는 말의 위치를 boolean을 통해 확인
// 문자열 각 인덱스에 따라 말 이동
// 정해진 범위 밖(배열밖)으로 이동하려 할 시 오류 나올거임. 그때 try catch로 예외처리해서 바로 null리턴하게 만들면 됨
boolean[][] location = new boolean[board.length][board[0].length]; // board가 정사각형이라는 보장이 없으면 for문 돌리면 됨.
int score = 0;
location[0][0] = true;
index1=0;
index2=0;
for(int i=0; i<operation.length(); i++){
try { // 인덱스값에 음수가 할당될 때 중간에 오류가 나서 멈춰버리는데 상관없이 진행하게 한다.
location = move(location, operation.charAt(i));
print(location);
}finally{
for (int j = 0; j < location.length; j++) {
findTrue = Arrays.asList(location[j]).indexOf(true); // 말의 위치 index 찾기
if (findTrue != -1) {
index2 = findTrue;
index1 = j;
break;
}
}
if (index1>=0 && index2>=0 && board[index1][index2] != 0) {
score += board[index1][index2];
}else if (index1<0 || index2<0) return null; // index에 음수 들어가 있으면 null출력하고 끝
}
}
return score;
}
private boolean[][] move(boolean[][] moved,char mo){
System.out.println(mo);
if(mo=='U'){
for(int j=0; j<moved.length; j++) { // 현재 위치 탐색
findTrue = Arrays.asList(moved[j]).indexOf(true); // 말의 위치 index 찾기
if(findTrue!=-1) {
index2 = findTrue;
index1 = j;
break;
}
}
moved[index1][index2] = false;
index1=index1-1;
moved[index1][index2] = true;
}else if(mo=='D') {
for (int j = 0; j < moved.length; j++) { // 현재 위치 탐색
findTrue = Arrays.asList(moved[j]).indexOf(true); // 말의 위치 index 찾기
if (findTrue != -1) {
index1 = j;
index2 = findTrue;
break;
}
}
moved[index1][index2] = false;
index1=index1+1;
moved[index1][index2] = true;
}else if(mo=='L') {
for (int j = 0; j < moved.length; j++) { // 현재 위치 탐색
findTrue = Arrays.asList(moved[j]).indexOf(true); // 말의 위치 index 찾기
if (findTrue != -1) {
index1 = j;
index2 = findTrue;
break;
}
}
moved[index1][index2] = false;
index2=index2-1;
moved[index1][index2] = true;
}else if(mo=='R') {
for (int j = 0; j < moved.length; j++) { // 현재 위치 탐색
findTrue = Arrays.asList(moved[j]).indexOf(true); // 말의 위치 index 찾기
if (findTrue != -1) {
index1 = j;
index2 = findTrue;
break;
}
}
moved[index1][index2] = false;
index2=index2+1;
moved[index1][index2] = true;
}
System.out.println(index2);
return moved;
}
private void print(boolean[][] arr){
for(int i=0;i<arr.length;i++) {
System.out.println(Arrays.toString(arr[i]));
}
}
}
try-catch문은 음수값이 인덱스에 할당될 때 오류가 발생하니 그 때 return null하고 끝내려고 넣었다.
ans
import java.util.*;
public class Solution {
public Integer boardGame(int[][] board, String operation) {
//HashMap을 선언한 후, 입력되는 명령어에 따라 이동할 좌표를 넣기
HashMap<String, int[]> DIR = new HashMap<String, int[]>(){{
put("U", new int[]{-1, 0});
put("D", new int[]{1, 0});
put("L", new int[]{0, -1});
put("R", new int[]{0, 1});
}};
//보드의 길이를 선언
int LEN = board.length;
//시작 좌표와, 점수를 0으로 할당합니다.
int Y = 0;
int X = 0;
int score = 0;
//입력받은 operation을 char배열로 변환
char[] chars = operation.toCharArray();
//해당 배열만큼 반복
for(int i = 0; i < chars.length; i++) {
int dY = DIR.get(String.valueOf(chars[i]))[0];
int dX = DIR.get(String.valueOf(chars[i]))[1];
Y += dY;
X += dX;
//isValid 함수를 이용하여, 이동이 불가능한 경우 null을 반환
if (!isValid(Y, X, LEN)) return null;
//이동이 가능한 경우, 해당 보드의 값만큼 전체 점수에 더함
score += board[Y][X];
}
//전체 점수를 반환
return score;
}
//이동이 가능한지 확인하여 boolean으로 결과를 반환하는 함수
public boolean isValid(int y, int x, int LEN) {
//최소값과, 최대값을 벗어나면 false, 가능하다면 true를 반환
return 0 <= y && y < LEN && 0 <= x && x < LEN;
}
}굳이 입력받은 문자열(opperation)을 문자배열로 바꾸지 말고
charAt을 이용해도 똑같은 결과를 얻을 수 있을 것 같다.
ans에서는 map을 이용해 2차원 형태를 좌표점처럼 가로축x, 세로축 y로 할당해 간단한 2차원 방정식 문제로 바꿨다.
마찬가지로 경로를 벗어나는 것도 x,y의 좌표점이 범위 밖에 위치하면 return null을 하도록 간단하게 표현이 가능하다.
4번 거스름돈 경우의 수
입력받는 금액(target)을 입력받는 화폐종류(type)로 나눌 수 있는 경우의 수를 구하시오.
import java.util.Arrays;
import java.util.Collections;
public class AmountDivided {
public long ocean(int target, int[] type) { // target만큼의 금액을 화폐의 종류(type)에 따라 몇가지 방법으로 가져갈 수 있는지 구하는 메서드
// CoinChange에서 했던 것과 비슷해보인다.
// 가장 큰 화폐단위부터 목표금액을 나눠서 최소한의 갯수로 거스름돈을 계산했었지만 이번에는 모든 경우의 수를 구해야 한다.
// type을 크기순으로 정렬시키자
// 가장 큰 단위의 화폐종류를 기준으로 목표금액을 나눠 거스름돈 걸러주는 알고리즘과 같이 진행한다.
// 가장 큰 단위의 화폐 사용횟수를 1씩 줄여가며 더 작은 화폐단위를 사용하는 경우의 수를 구해 counting해준다.
// 가장 작은 단위의 화폐를 최대한 많이 사용해 target을 나눈 case가 나올 시 종료한다.
Integer[] arr = Arrays.stream(type).boxed().toArray(Integer[]::new); // Wrapper 클래스로 박싱해주어야 역순정렬(Collections.reverseOrder()) 사용 가능.
Arrays.sort(arr, Collections.reverseOrder()); // 내림차순 정렬
int count = 0;
for(???){
int money = target;
for (Integer o : arr) {
if (money > 0) {
int sum = (int) Math.floor((double) money / o);
money = money - (o * sum);
}
}
count++;
}
}
}
위 수도코드와 같은 방식으로 알고리즘을 구현해보고자 했지만
반복문을 통해 특정케이스에서만 sum을 1씩 낮춰가며 진행하는 방법이 생각나지 않아서 일단 포기했다.
DFS를 활용한 방법을 생각해 봤다.
입력 받는 type 배열의 요소들을 각 노드라 생각하고 해당 노드에 가기위해 간석을 이용하는 비용을 요소값이라고 가정하면 target만큼의 비용을 내고 갈 수 있는 모든 루트를 구하면 될 것이다.
경우의 수에 더 초점을 맞춰서 생각해보았다.
큰 단위의 화폐를 사용한 횟수 하나가 줄어들 때 해당 단위를 더 작은 단위들로 조합하는 경우의 수 만큼 추가된다.
public class AmountDivided {
public long ocean(int target, int[] type) { // target만큼의 금액을 화폐의 종류(type)에 따라 몇가지 방법으로 가져갈 수 있는지 구하는 메서드
long[] answer = new long[target + 1];
answer[0] = 1;
for(int i : type) {
for(int j = i; j <= target; j++) {
answer[j] += answer[j-i];
}
}
for(int k=0; k<=target + 1; k+=10) {
System.out.println(k+"원을 만드는 경우의 수 = "+answer[k]);
}
return answer[target];
}
}
//입력
100, new int[]{10, 20, 50}
//출력
0원을 만드는 경우의 수 = 1
10원을 만드는 경우의 수 = 1
20원을 만드는 경우의 수 = 2
30원을 만드는 경우의 수 = 2
40원을 만드는 경우의 수 = 3
50원을 만드는 경우의 수 = 4
60원을 만드는 경우의 수 = 5
70원을 만드는 경우의 수 = 6
80원을 만드는 경우의 수 = 7
90원을 만드는 경우의 수 = 8
100원을 만드는 경우의 수 = 10
10목표 금액을 인덱스라 생각하고 입력 받은 type으로 1~target까지의 경우의 수를 나열한 배열을 이용해 값을 찾는 방식이다.
해당 배열값이 정해지는 과정은 아래와 같다.
for(int i : type) {
for(int j = i; j <= target; j++) {
answer[j] += answer[j-i];
}
System.out.println("-".repeat(10)+i+"원 화폐 추가"+"-".repeat(10));
for(int k=0; k<=target + 1; k+=10) {
System.out.println(k+"원을 만드는 경우의 수 = "+answer[k]);
}
}
//출력
----------10원 화폐 추가----------
0원을 만드는 경우의 수 = 1
10원을 만드는 경우의 수 = 1
20원을 만드는 경우의 수 = 1
30원을 만드는 경우의 수 = 1
40원을 만드는 경우의 수 = 1
50원을 만드는 경우의 수 = 1
60원을 만드는 경우의 수 = 1
70원을 만드는 경우의 수 = 1
80원을 만드는 경우의 수 = 1
90원을 만드는 경우의 수 = 1
100원을 만드는 경우의 수 = 1
----------20원 화폐 추가----------
0원을 만드는 경우의 수 = 1
10원을 만드는 경우의 수 = 1
20원을 만드는 경우의 수 = 2
30원을 만드는 경우의 수 = 2
40원을 만드는 경우의 수 = 3
50원을 만드는 경우의 수 = 3
60원을 만드는 경우의 수 = 4
70원을 만드는 경우의 수 = 4
80원을 만드는 경우의 수 = 5
90원을 만드는 경우의 수 = 5
100원을 만드는 경우의 수 = 6
----------50원 화폐 추가----------
0원을 만드는 경우의 수 = 1
10원을 만드는 경우의 수 = 1
20원을 만드는 경우의 수 = 2
30원을 만드는 경우의 수 = 2
40원을 만드는 경우의 수 = 3
50원을 만드는 경우의 수 = 4
60원을 만드는 경우의 수 = 5
70원을 만드는 경우의 수 = 6
80원을 만드는 경우의 수 = 7
90원을 만드는 경우의 수 = 8
100원을 만드는 경우의 수 = 10
10위에서 언급한 "큰 단위의 화폐를 사용한 횟수 하나가 줄어들 때 해당 단위를 더 작은 단위들로 조합하는 경우의 수 만큼 추가"를 생각해보며 결과값을 보면 이해하기 쉬울 것이다.
"큰 단위의 화폐를 사용한 횟수 하나가 줄어들 때 해당 단위를 더 작은 단위들로 조합하는 경우의 수 만큼 추가"이 규칙을 찾고 구현하기 위해 고민해 봤지만 유사한 기능들을 참고해 메서드를 구현하려다 결국 다 스포당했다.
따라서, 스스로 위 코드를 작성했다고 할 수는 없을 것 같다.
다만, 요즘 트렌드에서 잘나오지 않는 문제이기 때문에 비슷한 유형이 나올 때 활용할 수 있는 정도로만 이해하고 넘어가도 될 것 같다.
