[알고리즘 연습] 시청방해자 (by C++)

시청방해자

• 영화관에 사람이 일렬로 앉아있다고 가정하고, 앉은 키가 뒷 사람 모두보다 더 커서 뒷사람 모두에게 피해를 주는 사람의 수를 세자.
• 사람의 수 N을 입력받고, N명의 사람의 앉은 키를 입력받는다.
• 예를 들어, 10을 입력받고 56 46 55 76 65 53 52 53 55 50을 입력받으면, 뒷 사람 모두의 키보다 큰 인원은 3이므로 3을 출력한다.

---

풀이 (단순 접근)

#include <stdio.h>

int main() {
    //freopen("input.txt", "rt", stdin);

    int n,i,j,tmp,res = 0, flag = 1;
    int h[101];

    scanf("%d", &n);   

    for(i=0; i<n; i++) {   
        scanf("%d", &tmp);
        h[i] = tmp;
    }

    for(i=0; i<n-1; i++) {
        for (j=i+1; j<n; j++) {
            if (h[i] <= h[j]) {
                flag = 0;
                break;
            }
        }
        if (flag) {
            res++;
        }
        flag = 1;
    }

    printf("%d", res);

    return 0;
}

- 각 수마다 뒤에 자신보다 큰 수가 있는지 확인하는 방법을 사용헀다.

- tmp는 꼭 필요하지도 않은데 사용했다.

- 과정상 필요하긴 하지만, flag라는 거추장스러운 변수를 만들었다.

- 중첩 for문을 돌기 때문에 비효율적이다.

---

풀이 (효율적)

#include <stdio.h>

int main() {
    freopen("input.txt", "rt", stdin);

    int n,i,j,res = 0, max;
    int h[101];

    scanf("%d", &n);   

    for(i=1; i<=n; i++) {   
        scanf("%d", &h[i]);
    }

    max = h[n];
    for(i=n-1; i>=1; i--) {
        if (h[i] > max) {
            max = h[i];
            res++;
        }
    }

    printf("%d", res);

    return 0;
}

- 문제에서 '앉은 키가 뒷 사람 모두보다 더 커서'라는 부분에 주목하자.

- 결국은 뒤에서부터 확인하여 '지금까지 사람들 중 가장 큰 사람'이 시청 방해자가 되는 것이다.

- 중첩 for문을 돌지 않기 때문에 훨씬 효율적이다.