lango

찍먹? 부먹?
난 부먹 개발자.

4 minute read


Input-1
n=5, lost=[2,4], reserve=[1,3,5]
Output-1
5

Input-2
n=5, lost=[2,4], reserve=[3]
Output-2
4

문제 풀이

이 문제의 경우 그리디 알고리즘을 활용하여 접근하였다.

그리디 알고리즘이란?
가장 직관적인 알고리즘 설계 패러타임 중 하나이며, 매번 단계에서 선택할 때마다 가장 좋은 답을 선택하는 기법이다.
지금 선택한 것을 앞으로의 남은 선택에 영향을 끼칠지 고려하지 않는다는 전제이며, 전반적으로 적절한 결과를 도출하자는 알고리즘 기법이다.
항상 최적의 답을 구하는 것은 아니지만 어느정도 최적의 답에 근사한 결과를 빠르게 구할 수 있다는 장점이 있다.
특정 상황에서는 그리디 알고리즘이 최적의 답을 보장할 수도 있다.

그렇다면 그리디 알고리즘처럼 최적의 답만 찾는 방식으로 문제에 접근해보자.

  1. lost와 reserve 배열의 원소는 오름차순이어야 한다.
  2. 기본적으로 여벌 체육복을 가진 학생들은 수업에 참여할 수 있기에 answer에 n(전체 학생수) - lost.length(도난당한 학생수)를 저장한다.
  3. 여벌 체육복을 가져왔는데 도난당할 수 있기 때문에 lost와 reserve 배열에서 중복이 발생할 경우를 고려해야 한다.
  4. 도난 당한 학생에게 체육복을 빌려주는 경우는 lost의 원소에서 +- 1씩 증가시킨 수가 reserve 배열에 존재하는지 검증한다.
  5. 도난당한 학생에게 체육복을 빌려줄 때마다 answer를 증가시키면 된다.

위 풀이과정대로 코드를 작성해보자.

먼저 answer를 선언하고 lost와 reserve 배열을 오름차순으로 정렬하자.

1
2
3

int answer = n - lost.length; // 기본 값 : 도난 당하지 않고 여벌이 있는 학생 수
Arrays.sort(lost);
Arrays.sort(reserve);


다음으로 3-5번까지의 내용을 중첩 반복문과, Set을 활용한 2가지 방식으로 풀어보았다.

중첩 반복문 풀이

먼저 여벌 체육복을 가져왔는데 도난당한 학생의 경우 다른 도난당한 학생에게 빌려줄 수 없기 때문에 별도로 해당 원소를 마킹해두어야 한다.
중첩 반복문을 돌며 lost[i]와 reserve[j]가 중복일 때 해당 원소를 -1로 변경하고 answer를 1 증가시켰다.

1
2
3
4
5
6
7
8
9
10
11

// 여벌 체육복을 가져왔는데 도난당한 경우
for(int i=0; i<lost.length; i++) {
    for(int j=0; j<reserve.length; j++) {
        if(lost[i] == reserve[j]) {
            answer++;
            lost[i] = -1;
            reserve[j] = -1;
            break;
        }
    }
}

-1로 변경한 이유는?

0으로 변경하게 되면 이후 도난당한 학생에게 빌려줄 때 0+1 로직을 통해 1이 되어 조건문을 탈 수 있으므로 0이 되도록 -1로 두었다.

answer를 증가시킨 이유는?

여벌 체육복을 가져왔는데 도난당한 학생의 경우도 어쨋든 수업을 참여할 수 있기 때문에 answer를 증가시키는게 맞다.

다음으로 lost와 reserve의 중복도 처리하였으니 체육복을 빌려주는 로직을 짜면 된다.

1
2
3
4
5
6
7
8
9
10

// 도난당한 학생에게 빌려주는 경우
for(int i=0; i<lost.length; i++) {
    for(int j=0; j<reserve.length; j++) {
        if((lost[i]+1 == reserve[j]) || (lost[i]-1 == reserve[j])) {    
            answer++;
            reserve[j] = -1;
            break;
        }
    }
}

위와 같이 lost[i]+1 이나 lost[i]-1이 reserve[j]와 같으면 인접한 수로 보고 answer를 증가시킨다.
answer를 증가시켰다면 다음 인접수는 고려하지 않아도 되기에 reverve[j]를 -1로 변경하여 검증에서 제외하도록 한다(이것이 그리디 알고리즘 의도라고 생각이 들었다.)

HastSet 풀이

HashSet을 활용하면 복잡한 중첩반복문 작성할 필요없이 간단하다.

먼저 reserveSet이란 이름으로 HashSet을 하나 생성하고 reserve의 값을 저장한다.

1
2

HashSet<Integer> reserveSet = new HashSet<>(); 
for(int i : reserve) reserveSet.add(i);

중첩반복문 풀이와 동일하게 HashSet에 중복 여부를 따져 처리하자.

1
2
3
4
5
6
7
8

// 여벌 체육복을 가져왔는데 도난당한 경우 
for(int i=0; i<lost.length; i++) {
    if(reserveSet.contains(lost[i])) {
        answer++;
        reserveSet.remove(lost[i]);
        lost[i] = -1;
    }
}

그리고 아래와 같이 HashSet에서 인접 원소 수를 확인하여 answer를 증가시키면 된다.

1
2
3
4
5
6
7
8
9
10
11

// 도난당한 학생에게 빌려주는 경우
for(int i=0; i<lost.length; i++) {
    if(reserveSet.contains(lost[i]-1)) {
        answer++;
        reserveSet.remove(lost[i]-1); 
    }
    else if(reserveSet.contains(lost[i]+1)) {
        answer++;
        reserveSet.remove(lost[i]+1);  
    }
}


작성 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

import java.util.*;

class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] lost = {2,4};
        int[] reserve = {1,3,5};
        long start = System.currentTimeMillis();
        solution(n,lost,reserve);
        long end = System.currentTimeMillis();
        System.out.println("\n수행시간 = " + (end-start));
    }

    public static int solution(int n, int[] lost, int[] reserve) {
        int answer = n - lost.length;
        Arrays.sort(lost);
        Arrays.sort(reserve);
        // 여벌 체육복을 가져왔는데 도난당한 경우
        for(int i=0; i<lost.length; i++) {
            for(int j=0; j<reserve.length; j++) {
                if(lost[i] == reserve[j]) {
                    answer++;
                    lost[i] = -1;
                    reserve[j] = -1;
                    break;
                }
            }
        }
        // 도난당한 학생에게 빌려주는 경우
        for(int i=0; i<lost.length; i++) {
            for(int j=0; j<reserve.length; j++) {
                if((lost[i]+1 == reserve[j]) || (lost[i]-1 == reserve[j])) {    
                    answer++;
                    reserve[j] = -1;
                    break;
                }
            }
        }
        return answer;
    }

    public static int solution2(int n, int[] lost, int[] reserve) {
        int answer = n - lost.length;
        HashSet<Integer> reserveSet = new HashSet<>(); 
        Arrays.sort(lost);
        Arrays.sort(reserve);
        for(int i : reserve) reserveSet.add(i);        
        // 여벌 체육복을 가져왔는데 도난당한 경우 
        for(int i=0; i<lost.length; i++) {
            if(reserveSet.contains(lost[i])) {
                answer++;
                reserveSet.remove(lost[i]);
                lost[i] = -1;
            }
        }
        // 도난당한 학생에게 빌려주는 경우
        for(int i=0; i<lost.length; i++) {
            if(reserveSet.contains(lost[i]-1)) {
                answer++;
                reserveSet.remove(lost[i]-1); 
            }
            else if(reserveSet.contains(lost[i]+1)) {
                answer++;
                reserveSet.remove(lost[i]+1);  
            }
        }
        return answer;
    }
}

회고

  • 그리디 알고리즘에 대해서 알아보고, 어떤 방식으로 문제에 접근해야 할지 공부할 수 있었다.
  • HashSet의 contains() 메서드를 통해 원소 존재여부를 검증하는 과정이 가독성이 좋다고 느껴졌다.

You may also enjoy