INFP 두람 - 백준 BOJ 25186

30분 이내에 풀지 못했지만, 문제를 다각도에서 접근하는 과정이 나중에 도움이 될 것 같아 글을 작성해본다

문제는 다음과 같다

 

https://www.acmicpc.net/problem/25186

25186번: INFP 두람

 

 

---

풀이 과정

사람도 N명이고 옷의 가짓수도 N개면 원순열일 때 무조건 안겹칠텐데? 싶어서 초반에 조금 헤맸다
문제를 다시 읽어보니, 인원수는 N 명 == 옷의 가짓수 가 아니라 종류별로 한벌 이상 존재하는 전체 옷의 합이었다.

 

브루트 포스 ( 틀린 풀이 )

처음에는 낭만이 가득한 브루트 포스로 문제를 접근해 보았다

 

• 배열을 오름차순으로 정렬
• 왼쪽부터 배열을 탐색하며, 0이 아닌 제일 작은 원소값을 발견하면 이를 배열 전체에 대해 모든 원소값에서 빼줌
• 이 과정을 반복하다가, 맨 마지막 원소만 남았을 때, 이 값이 2 이상이면 Unhappy 를, 미만이면 Happy 를 출력

 

7 1 5 7 4

1 4 5 7 7	// 정렬
0 3 4 6 6
0 0 1 3 3
0 0 0 2 2
0 0 0 0 0	// 마지막 원소가 2 미만이므로, Happy

================================================

1 13 2 4 1 1 1

1 1 1 1 2 4 13	// 정렬
0 0 0 0 1 3 12
0 0 0 0 0 2 11
0 0 0 0 0 0 9	// 마지막 원소가 2 이상이므로, Unhappy

================================================

 

그럴듯해 보인다

하지만 최악의 경우 시간복잡도가 O(N^2) 으로, 문제 조건에 의하면 이는 10^10 으로 제한시간인 1초를 아득히 넘어간다

 

비단 시간초과뿐만 아니라 엣지케이스 또한 존재하는데

 

2 1

1 2	// 정렬
0 1	// 맨마지막이 2 미만이니 Happy?

ABA	// 맨 처음과 마지막이 같아 Unhappy 이다

 

맨 마지막이 2 미만이었음에도 불구하고 Unhappy 가 나온다

 

또한 

 

1 13 2 4 1 1 1

1 1 1 1 2 4 11	// 정렬
0 0 0 0 1 3 10
0 0 0 0 0 2 9
0 0 0 0 0 0 7	// 2 이상이니 Unhappy?

// 실제로는 Happy 이다

 

와 같이 2 이상임에도 불구하고 Happy 인 엣지케이스도 발견했다

 

 

애드 혹

슬라이딩 윈도우, 이분탐색, dp 모두 고려 해봤으나 해당 문제에는 적용되지 않는 접근법이었다

해공간의 크기와 제한시간을 고려했을 때 O(N) 에 해결되어야 할 문제였고, 무언가 특별한 풀이가 있을 것 같았다

 

위의 브루트포스 풀이에서 기존에 생각했던 조건에 부합하지 않는 케이스들에 대해서 그 특별한 풀이를 찾아보기로 했다

 

 

... 이 과정을 반복하다가, 맨 마지막 원소만 남았을 때, 이 값이 2 이상이면 Unhappy 를, 미만이면 Happy 출력

 

 

기존에 떠올렸던 알고리즘의 과정 중 하나인데, 여기서 2 라는 값이 고정값이 아닌 가변적인 값임이 엣지 케이스를 통해 발견되었다

이 가변적인 값의 규칙을 발견하고자 여러 케이스들을 살펴보던 도중,

옷의 종류들 중 옷의 가짓수가 최대인 종류의 가짓수가, 옷의 가짓수의 총합의 절반 ( 내림된 값 ) 이하일 경우 원순열에서 인접한 원소들의 중복이 발생하지 않음을 찾아냈다

 

옷의 총 개수가 7개인 상황을 가정
이 중 A type 의 옷이 4개라고 가정을 해보자

A ? A ? A ? A

한가지 종류의 옷에 대해, 이들이 인접하지 않도록 최적으로 A 옷을 분류했다
나머지 3칸에는 어떤 옷이 들어가도 이들은 인접하지 않게 되지만,
A 가 4개가 됨에 따라 A 는 무조건 인접하게 됨

 

위의 설명에 따라서 O(N) 에 해답을 찾아낼 수 있는 특별한 풀이를 찾아냈다

 

문제의 조건에 따라 두가지 주의할점이 있는데,

 

1. 문제 조건에 따라 옷의 총합은 10^10 까지 될 수 있는데, 이는 int 범위( 최대값은 약 10^9 )를 넘어서므로 long type 으로 연산을 수행해야 하고 ( JS 같이 기본 숫자 type 의 범위가 크면 해당 x )
2. 옷의 총 가짓수가 1개일 경우, 종류의 최대값고 1이 되고, 이는 인접한 옷끼리 겹치지 않는 경우이지만, 위의 풀이로는 예외적인 케이스가 된다. 따라서 해당 케이스 처리가 필요하다

 

import java.io.*;
import java.util.*;
import java.util.stream.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int clothTypeCount = Integer.parseInt(reader.readLine());

        int[] clothCountByType = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        long maxClothCountFromType = Arrays.stream(clothCountByType).mapToLong(i -> i).reduce(0, (max, curr) -> Math.max(max, curr));
        long totalClothCount = Arrays.stream(clothCountByType).mapToLong(i -> i).reduce(0, (acc, curr) -> acc + curr);

        if(totalClothCount == 1) {
            System.out.println("Happy");
            return;
        }
        
        String answer = totalClothCount / 2 < maxClothCountFromType ? "Unhappy" : "Happy";

        System.out.println(answer);
    }
}