프로그래머스 알고리즘 문제 풀이 - 그리디

zio도미닉·2022년 1월 11일
0

1. 체육복

  • 해결방법
    - 기본 배열을 1로 만들고 lost와 reserve 인덱스는 각각 -1 or +1을 해준다.
    - 첫번째 인덱스는 뒤에서만 빌릴수 있다
    - 2번째 인덱스 ~ 마지막 전까지 인덱스는 앞에서 먼저 확인하고 있으면 빌리고 없으면 뒤에서 빌린다.
    - 마지막 인덱스는 바로 앞에서만 빌릴 수 있다.
  • 주의할 점은 첫번째 인덱스와 마지막 인덱스는 빼줘서 반드시 계산할것 (마지막 인덱스를 안빼주면 인덱스 오류 발생)
import java.util.*;
class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = 0;
        
        int []arr=new int[n+1];
        for (int i=1;i<arr.length;i++) {
            arr[i]=1;
        }
        
        // lost 빼주기
        for (int i=0;i<lost.length;i++) {
            arr[lost[i]]-=1;
        }
        
        // reverse 더해주기
        for (int i=0;i<reserve.length;i++) {
            arr[reserve[i]]+=1;
        }
        
        // System.out.println(Arrays.toString(arr)); // 2,0,2,0,2
        
        
        
        // 1번 인덱스만 뒤에서 빌릴수 있음
        if (arr[1]==0 && arr[2]==2) {
            arr[1]=1;
            arr[2]=1;
        }
        
        // 나머지는 앞에서 먼저 빌리고 없으면 뒤에서 빌리기
        for (int i=2;i<arr.length-1;i++) {
            if (arr[i]==0) { // 체육복이 없는 경우
                if (arr[i-1]==2) { // 앞에서 빌림
                    arr[i]=1;
                    arr[i-1]=1;
                }
                else if (arr[i+1]==2){ // 뒤에서 빌림
                    arr[i]=1;
                    arr[i+1]=1;
                }
            } 
        }
        
        // 마지막 인덱스만 앞에서 빌릴 수 있음
        if (arr[n-1]==0 && arr[n-2]==2) {
            arr[n-1]=1;
            arr[n-2]=1;
        }
        
        // System.out.println(Arrays.toString(arr));
        for (int i=1;i<arr.length;i++) {
            if (arr[i]>=1) answer++;
            
        }
        
        return answer;
    }
} 

2. 조이스틱

3. 가장 큰수

첫번째 해결방법은 조합으로 모든 경우의 수를 찾을려고 하였음 -> 마지막 수가 100만이 아니라 자리수가 100만이라 이 방법은 실패

두번째 방법은 문자열을 이용한 방법

profile
BackEnd Developer

0개의 댓글