[Greedy] 모험가 길드 (java)

[나의 코드]

public class Greedy3 {
    public int solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken()); // 2 3 1 2 2
        }
        Arrays.sort(arr); // 1 2 2 2 3

        int result = 0;

        // 비교
        for (int i = 0; i < N-1; i++) {
            int lv1 = arr[i]; // 1
            int lv2 = arr[i+1]; // 2

            if (lv1 == 1) {
                result++;
            }
            else if (lv1 == lv2) {
                result++;
                i = i + lv2;
            }
        }

        System.out.println(result);
        return result;
    }

    public static void main(String[] args) throws Exception {
        new Greedy3().solution();
    }
}

/*

S = 2 3 1 2 2

1. 오름차순 정렬
-> 1 2 2 2 3

2. 최소단위로 그룹화

3. 그룹화되지 못한 애들은 남기기

 */

 

나는 int[] 배열로 구현했는데, ArrayList로 구현하는게 더 효율적인 것 같다.

내 코드는 빌드하는데 5 sec, 780 ms 시간이 걸렸지만, 나동빈님 코드는 1 sec, 882 ms 시간이 걸렸다.

 

[나동빈님 코드]

public class Greedy3 {
    public int solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            arrayList.add(Integer.parseInt(st.nextToken())); // 2 3 1 2 2
        }
        Collections.sort(arrayList); // 1 2 2 2 3

        int result = 0; // 총 그룹의 수
        int count = 0; // 현재 그룹에 포함된 모험가의 수
        for (int i = 0; i < N; i++) {
            count += 1; // 현재 그룹에 해당 모험가를 포함시키기
            if (count >= arrayList.get(i)) { // 현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면, 그룹 결성
                result += 1;
                count = 0;
            }
        }

        System.out.println(result);
        return result;
    }

    public static void main(String[] args) throws Exception {
        new Greedy3().solution();
    }
}

 

그리고 +1을 할 때 result += 1이 아니라 result++로 하는게 더 좋은가?

-> i++ 는 현재 값을 사용한 후에 1을 증가시키기 때문에, 일반적으로 루프의 조건식에서 사용되고, i+=1 은 i 의 값을 1 증가시키고 그 결과를 i 에 할당하기 때문에 일반적으로 루프에서 카운터로 사용된다고 한다!

 

굳이 if else 조건문으로 비교를 안하고 한번의 조건문으로 구현을 가능하게 했다.

로직을 어떻게 저렇게 구현할 생각을 하시지..? 나동빈님은 천재다..