섹션1. 시뮬레이션 & 구현 - (3) | 과일 가져가기 문제 풀이

🎈섹션1. 시뮬레이션 & 구현 - (3) | 과일 가져가기 문제 풀이

🟦 1-6. 과일 가져가기

문제

문제 분석 (풀이)

• 문제 조건 1. 서로 이득이 될 때만 교환이 가능
• 문제 조건 2. 교환 가능 여러명 이면 번호 작은 학생과 교환

⇒ 서로 교환 시 이득이 나는 조건

1) 각 학생에게 최솟값이 유일해야 한다.

2) 서로 교환하려는 최솟값 과일이 달라야 한다. (= 과일 idx 번호 달라야 한다.)

3) 교환 이후, 1개 증가한 과일 개수가 여전히 그대로 최솟값인 과일이어야 한다.

(= 증가한 과일 ≥ 감소한 과일)

내 시도

나는 Fruit (사과, 배, 귤) 객체를 새로 생성해서, ArrayList 에 담아 → 각 학생의 최솟값을 체크해놓고, 최솟값 과일이 다를 경우 교환이 되도록 할 생각이었다. → 잘 안되었다.

완성 코드

// 1-6. 과일 가져가기 | 어려운 문제 -> 반복해서 풀어보기
class Solution1 {
    //1) 최솟값을 확인해야 함
    //2) 최솟값은 유일해야 함
    //3) 최솟값 갖는 과일 인덱스 값은 서로 달라야 함
    //4) 증가한 과일 <= 감소한 과일 이어야 함

    //입력 배열 내부에서 각 학생이 갖는 과일 속 최솟값 담는 용도 
    public int getMin(int[] fruit) {
        int min = 100;
        for(int x : fruit) {
            min = Math.min(min, x);
        }
        return min;
    }
    //최솟값이 유니크한지 확인용 배열
    public Boolean isMinUnique(int[] fruit) {
        int cnt = 0;
        int min = getMin(fruit);
        //얻어온 최솟값이 전체 배열 순회해도 여전히 cnt==1 인지 확인
        for(int x : fruit) {
            if(x == min) cnt++;
        }
        //cnt==1 이면 유니크한 거니 True 반환 
        return cnt == 1;
    }
    //최솟값의 인덱스값 반환 함수(=과일 확인용)
    public int getMinIndex(int[] fruit) {
        int min = getMin(fruit);
        for(int i=0; i<3; i++) {
            if(fruit[i] == min) return i;
        }
        return 0;
    }

    //[솔루션 함수]
    public int solution(int[][] fruit){
        int answer = 0;
        int n = fruit.length; //학생수 n명 뽑고
        int[] ch = new int[n];//체크용 배열 (교환시 체크)
        for(int i=0; i<n; i++) {
            //만약 현재 i번째 학생이 교환 이루어진 애면 그냥 continue 넘어감
            if(ch[i] == 1) continue;
            // 각 학생별로 배열 보냈을 때.최솟값이 유일값 아니면 그냥 넘어감 
            if(isMinUnique(fruit[i])== false) continue;

            //이제 j는 i보다 뒤쪽 학생들 순회용
            for(int j=i+1 ; j<n; j++) {
                if(ch[j] == 1) continue;
                if(isMinUnique(fruit[j]) == false) continue;
                //교환 전이면서 유일한 최솟값 과일 뽑아서 
                int a = getMinIndex(fruit[i]);
                int b = getMinIndex(fruit[j]);
                // a와 b 각각의 과일이 서로 다르면서 각 값은 0보다 큰 값이어야 함
                if(a != b && fruit[i][b] > 0 && fruit[j][a] > 0) {
                    //=> 교환 이후에도 증가한 과일 개수가 여전히 바구니에서 최솟값 갖는 과일인지 확인하는 부분 
                    //i 학생의 증가한 과일 개수가 감소한 과일개수보다 커야하고, j 학생의 증가한 과일 개수가 감소한 과일 개수보다 커야 한다. 
                    if(fruit[i][a] + 1 <= fruit[i][b] - 1 && fruit[j][b] + 1 <= fruit[j][a] - 1) { 
                        //교환처리
                        fruit[i][a]++;
                        fruit[i][b]--;

                        fruit[j][b]++;
                        fruit[j][a]--;
                        //방문처리 
                        ch[i]=1;
                        ch[j]=1;
                        //현재의 안쪽 for문 탈출 
                        //교환은 최초 각 i에 대하여 한번씩만 가능하므로
                        break; 
                    }
                }
            }
        }
        //모든 학생 최솟값 갖는 애들 누적합하여 리턴
        for(int[] x : fruit) {
            answer += getMin(x);
        }
        return answer;
    }
    //실행 메인 
    public static void main(String[] args){
        Solution1 T = new Solution1();
        System.out.println(T.solution(new int[][]{{10, 20, 30}, {12, 15, 20}, {20, 12, 15}, {15, 20, 10}, {10, 15, 10}}));
        System.out.println(T.solution(new int[][]{{10, 9, 11}, {15, 20, 25}}));    
        System.out.println(T.solution(new int[][]{{0, 3, 27}, {20, 5, 5}, {19, 5, 6}, {10, 10, 10}, {15, 10, 5}, {3, 7, 20}}));
        System.out.println(T.solution(new int[][]{{3, 7, 20}, {10, 15, 5}, {19, 5, 6}, {10, 10, 10}, {15, 10, 5}, {3, 7, 20}, {12, 12, 6}, {10, 20, 0}, {5, 10, 15}}));
    }
}

---

🟦 1-7. 비밀번호

문제

문제 분석 (풀이)

• 1) 3X3 배열에 keypad의 값을 초기화
• 2) dist[][]배열 → i 가 j까지 가는 (시간)을 세팅할 용도인데 초반에는 2로 초기화
• 3) dist[][]배열도 자기 자신에게 향하는 대각선 부분은 0 으로 초기화
• 4) 이제 3X3 키패드를 차례로 순회하며 현재의 from출발 좌표에서

나머지 각각의 좌표에 대해 다시 for(0~8)로 8방향을 돌면서 인접 거리를 확인하고 인접한 곳에 대해서는 dist[from][to] 값을 1로 세팅한다.

• 5) 이제 password 배열 내부를 차례로 돌면서 (String 문자열을) → 하나씩 뽑아 charAt() - 48 로 숫자 변형 후. answer에 각 숫자 간 입력 총 시간을 누적한다.

완성 코드

package to_0419;

import java.util.*;
class Solution {
	public int solution(int[] keypad, String password){
		int answer = 0;
		int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
		int[] dy = {0, 1, 1, 1, 0, -1, -1, -1}; 
		int[][] pad = new int[3][3];
		int[][] dist = new int[10][10];
		for(int i = 0; i < 3; i++){
			for(int j = 0; j < 3; j++){
				pad[i][j] = keypad[i*3 + j];
			}
		}
		for(int i = 0; i < 10; i++){
			Arrays.fill(dist[i], 2);
		}
		for(int i = 0; i < 10; i++) dist[i][i] = 0;
		
		for(int i = 0; i < 3; i++){
			for(int j = 0; j < 3; j++){
				int from = pad[i][j];
				for(int k = 0; k < 8; k++){
					if(i+dx[k] >= 0 && i+dx[k] < 3 && j+dy[k] >= 0 && j+dy[k] < 3){
						int to = pad[i+dx[k]][j+dy[k]];
						dist[from][to] = 1;
					}
				}
			}
		}
		for(int i = 1; i < password.length(); i++){
			int from = (int)password.charAt(i-1)-48;
			int to = (int)password.charAt(i)-48;
			answer += dist[from][to];
		}	
		return answer;
	}

	public static void main(String[] args){
		Solution T = new Solution();
		System.out.println(T.solution(new int[]{2, 5, 3, 7, 1, 6, 4, 9, 8}, "7596218"));	
		System.out.println(T.solution(new int[]{1, 5, 7, 3, 2, 8, 9, 4, 6}, "63855526592"));
		System.out.println(T.solution(new int[]{2, 9, 3, 7, 8, 6, 4, 5, 1}, "323254677"));
		System.out.println(T.solution(new int[]{1, 6, 7, 3, 8, 9, 4, 5, 2}, "3337772122"));
	}
}

---