[Baekjoon] 7795_먹을 것인가 먹힐 것인가

Silver III

문제(출처: https://www.acmicpc.net/problem/7795)

---

<먹을 것인가 먹힐 것인가>

문제 

 

심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 수 있는 쌍의 개수는 7가지가 있다. 8-3, 8-6, 8-1, 7-3, 7-6, 7-1, 3-1.

두 생명체 A와 B의 크기가 주어졌을 때, A의 크기가 B보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하시오.

입력

 

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 A의 수 N과 B의 수 M이 주어진다. 둘째 줄에는 A의 크기가 모두 주어지며, 셋째 줄에는 B의 크기가 모두 주어진다. 크기는 양의 정수이다. (1 ≤ N, M ≤ 20,000) 

 

출력 

 

각 테스트 케이스마다, A가 B보다 큰 쌍의 개수를 출력한다.

 

 

문제 풀이

   - 시간 초과 코드

import sys

if __name__=='__main__':

    t=int(sys.stdin.readline())

    for i in range(t):
        n,m=map(int, sys.stdin.readline().split())
        a=list(map(int, sys.stdin.readline().split()))
        b=list(map(int, sys.stdin.readline().split()))

        b.sort(reverse=True)

        result=0
        for j in a:
            idx=0
            while True:
                if idx >= m:
                    break
                if j>b[idx]:
                    result+=(m-idx)
                    break
                idx+=1
        print(result)

 

• B만 정렬 후 A 값과 비교하여 크면 그 이후로도 A가 B보다 크기 때문에 m-idx를 이용하여 result 구함

계속해서 발생하는 시간 초과로 결국 검색의 힘을 빌렸다. 이 문제는 사실 이분 탐색 문제였다. 하지만 난... 이리 보고 저리 봐도 이분 탐색으로 풀지 않았다(?) 지금 코드에서도 조금만 더 하면 해결할 수 있을 것 같아 찾아본 결과  A도 정렬 후 idx를 활용하는 방법이 있었다.

 

예를 들어 입력이

A [8, 1, 7, 3, 1]

B [3, 6, 1]

이라고 하자. 

 

위의 시간 초과 코드는 

A [8, 1, 7, 3, 1]

B [6, 3, 1]

B만 정렬된 이 상태에서 A를 순회하며 B 값과 비교해 그 값보다 크면 나머지 값 보다도 클 것이기 때문에 m-idx를 result에 더해주는 방식을 사용한 것이다.

 

하지만 아래의 통과한 코드는

A [8, 7, 3, 1, 1]

B [6, 3, 1]

이와 같이 A, B를 둘 다 정렬하여 8>6 이므로 idx=0, result에 3을 더하고,

7>6 이므로 idx=0, result에 3을 더하고 

3>1 이므로 idx=2, resut에 1을 더하고

이런 식으로 위에서와 같이 m-idx는 맞지만, A를 정렬해줌으로써 idx를 다시 0으로 초기화해줄 필요가 없다는 점이 달랐다.

 

- 통과한 코드

import sys

if __name__=='__main__':

    t=int(sys.stdin.readline())

    for i in range(t):
        n,m=map(int, sys.stdin.readline().split())
        a=list(map(int, sys.stdin.readline().split()))
        b=list(map(int, sys.stdin.readline().split()))
        
        #정렬
        a.sort(reverse=True)
        b.sort(reverse=True)

        result=0
        idx=0
        for j in a: # A list
            while True:
                if idx >= m: # index 종료 조건
                    break
                if j>b[idx]: # 크면 -> 나머지 값보다도 다 큼
                    result+=(m-idx)
                    break
                idx+=1
        print(result)

 

• A, B 내림차순으로 정렬
• for문, while문 활용
• 핵심: idx, m-idx

---

생각🤔

 

아주 조금의 생각의 차이로 맞고 틀린 것이 결정된다는 것을 느낀다..

왜 이 아주 조금을 생각하지 못할까?!?!?!?!!?

위에 설명한 걸 보면 내가 이해한 것을 최대한 자세히 적으려 했으나 아주 주절주절이 되어버린 것 같다.. 😥

 

수많은 제출....

---