16504. Gravity

• 문제 해석
  • 가로 N, 세로 100 크기의 공간에 수직으로 상자가 쌓여있다. 공간을 오른쪽으로 회전해 중력으로 상자들이 낙하할 때, 가장 큰 낙차 구하기
• 입력
  • 공간 가로 크기 N
  • 쌓여있는 상자 높이 리스트 Arr
• 출력
  • 가장 큰 낙차
• 아이디어
  • 기준의 맨 위쪽상자 기준 오른쪽에 높이가 같거나 높은 상자가 있다면, 낙차는 N - 자기자신의 위치인덱스 - 같거나 더 높게 쌓인 상자 개수 or N - 자기자신1 - 같거나 더 높게 쌓인 상자 개수
  • 회전하기 전 가장 왼쪽의 맨 위쪽에 있는 상자가 낙차가 클 가능성이 가장 높다.
  • 전체 상자에 대해서 enumerate으로 for문을 돌아야 하나? 아니면 포인터로 낙차 더해가면서 while문? 아니면 맨 왼쪽만 탐색해도 될까? ⇒ 일단 while문으로 가자!
• 필요변수
  • 임의의 최대낙차값 dropMax
  • 낙차 drop
• 코드(while문)

for tc in range(1, int(input()) + 1):
    N = int(input())
    Arr = list(map(int, input().split()))

    dropMax = 0

    s, e = 0, 0
    e += 1
    drop = 0
    while e < N:
        if Arr[s] > Arr[e]: # 기준상자가 오른쪽 비교할 상자보다 더 높으면 낙차 +1
            drop += 1
        e += 1              # 비교할 상자 우측 이동 +1

        if drop > dropMax:
            dropMax = drop

        if s==N-2: #종료 조건
            break
            
        if e == 9:          # 기준 상자에 대해서 낙차 확인을 끝내면,
            s += 1          # 기준 인덱스를 오른쪽으로 이동
            e = s + 1       # 비교 인덱스도 초기화
            drop = 0        # 낙차도 초기화

    print(f'#{tc} {dropMax}')

• 코드(맨 왼쪽만 따져보기)

for tc in range(1, int(input()) + 1):
    N = int(input())
    Arr = list(map(int, input().split()))

    cnt = 0
    for i in range(1, N):    # 맨왼쪽 상자(=인덱스0)의 오른쪽 탐색
        if Arr[0] <= Arr[i]: # 높이보다 크거나 같으면 낙차 발생 안함
            cnt += 1
    drop = N - 1 - cnt       # 유효낙차 = 회전시 높이(가로크기) - 자기자신 - 낙차0인경우

    print(f'#{tc} {drop}')

• 코드(for문)

for tc in range(1, int(input()) + 1):
    N = int(input())
    Arr = list(map(int, input().split()))

    dropMax = 0                     # 임의의 최대낙차값
    for i, e in enumerate(Arr):
        cnt = 0
        for j in range(i, N):
            if e <= Arr[j]:
                cnt += 1
        drop = N - i - cnt          # 낙차 공식
        if dropMax < drop:          # 최대 낙차 갱신
           dropMax = drop

    print(f'#{tc} {dropMax}')

• 피드백
  " "