항해99 TIL 4일차 (체육복 / 프로그래머스)

 

문제                   

프로그래머스

 

 

 

1 번째 시도                      

 

문제 파악

 

• 2번 학생은 1,3 번 학생의 교복을 빌릴 수 있지만 1번 교복을 빌리는 게 최상의 선택입니다.
• 왜냐하면 3번 교복을 빌릴시, 교복을 잃어버린 4번 학생이 교복을 못 빌릴 수 있기 때문입니다.
• 고로, 로직은 자신의 앞 번호에 해당하는 교복이 있으면 빌리고 없으면 뒤에 있는 교복을 빌리는 로직으로 짜겠습니다.
• 만약 3번 학생이 1번 학생의 교복을 빌리지 못한다면 4 번학생은 1 번학생의 교복을 빌릴 수 있는지 탐색을 안해도 됩니다.

 

+) 까먹고 제한사항을 확인을 안했습니다. 다시 제안사항을 살펴보니 학생의 수가 최대 30명이니 속도제한은 안 걸릴 것 같습니다. 제안사항을 확인하는 습관을 들입시다!

 

교복을 잃어버린 학생이 교복을 빌려줄 학생을 탐색하게 할 것입니다. 

for{
        for{}
}
위 구조가 되겠네요

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
       
    
        int y =0;
        ArrayList<Integer> borrower = new ArrayList<>();
        
        for(int i=0; i< lost.length; i++) {
            for(int j = y; j< reserve.length; j++) {
                
                if(lost[i] + 1 < reserve[j]) // lost 2 reserve 5 인 경우는 탐색 안 해도 되니까
                    break;
                
                if((lost[i] -1 == reserve[j] || lost[i] +1 == reserve[j]) && !borrower.contains(lost[i])) {
                    borrower.add(lost[i]);
 					y++; // +1 된 i가 탐색 했던 것을 재탐색하는 것을 방지, j와 동기화
                    break;
                }
                 y++; 
            }
        }
        return n - lost.length + borrower.size();
    }
}

 

문제를 다시 보니 lost와 reserve가 정렬되어있다는 이야기가 안 나와있었습니다. 예제를 보고 혼자 넘겨짚었습니다.
배열을 List로 바꾸고 정렬해주도록 하겠습니다. 

 

2 번째 시도                

+) 배열을 ArrayList로 변환하는 법은 지난 게시물을 참조해주세요
2024.03.29 - [자료구조] - List <-> 배열 변환하는 법

//  i =0  y= 0 j =0   lost =3  reserve = 1 첫 번째 if문 통과 두 번째 if문도 통과
//  i = 0 y = 1 j= 0
// i =0 y =1  j =1  두 번째 for문 아웃


import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
       
        ArrayList<Integer> loster = new ArrayList<>();
        ArrayList<Integer> reserver = new ArrayList<>();
        ArrayList<Integer> borrower = new ArrayList<>();
        
        for(int l: lost)
            loster.add(l);
        for(int r: reserve)
            reserver.add(r);

        Collections.sort(loster);
        Collections.sort(reserver);
        
        int y =0;
        
        for(int i=0; i< loster.size(); i++) {
            for(int j = y; j< reserver.size(); j++,y++) {
                
                if(loster.get(i) + 1 < reserver.get(j)) { // lost 2 reserve 4 와 같은 경우는 탐색 안 해도 되니까
                   y++;
                    break;
                }
                if((loster.get(i) -1 == reserver.get(j) || loster.get(i) +1 == reserver.get(j)) && !borrower.contains(loster.get(i))) {
                    borrower.add(loster.get(i));
                    y++;
                    break;
                }
                  // +1 된 i가 탐색 했던 것을 재탐색하는 것을 방지, j와 동기화
            }
        }
        return n - loster.size() + borrower.size();
    }
}

아까보다 16점은 늘었지만 정답은 아닙니다. 속도 문제도 아니니 예외상황을 빼트린 것 같습니다.

• 문제를 다시 읽어보니 교복을 잃어버린 학생이 여벌을 가져온 학생일 수도 있다는 겁니다.
• j와 y의 관계가 복잡해 List에서 해당되는 원소는 삭제하기로 하였습니다

 

3 번째 시도                    

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
       
        ArrayList<Integer> loster = new ArrayList<>();
        ArrayList<Integer> reserver = new ArrayList<>();
        ArrayList<Integer> borrower = new ArrayList<>();
        
        for(int l: lost)
            loster.add(l);
        for(int r: reserve)
            reserver.add(r);

        Collections.sort(loster);
        Collections.sort(reserver);
        
        int y =0;
        
       for (int i = 0; i < loster.size(); ) {
            if (reserver.contains(loster.get(i))) {
                reserver.remove(loster.get(i));
                loster.remove(i);
            } else {
                i++;
            }
        }
        
         for (int i = 0; i < loster.size(); i++) {
            for (int j = 0; j < reserver.size(); j++) {
                if (loster.get(i) - 1 == reserver.get(j) || loster.get(i) + 1 == reserver.get(j)) {
                    borrower.add(loster.get(i));
                    reserver.remove(j); 
                    break;
                }
            }
        }
        return n - loster.size() + borrower.size();
    }
}

 

 

깨달은 점

• 확실치 않으면 문제를 다시 확인하자
• 예외상황은 꼼꼼히!