https://gkim1011.tistory.com/9
저번에는 문제에서 주어진 그림을 참고하여,
블럭 하나하나를 2차배열 bucket에 담은 후 중력 작용을 확인했었다.
하지만 굳이 bucket으로 안풀어도 되는 문제였다.
일단 생각해야 하는 것은
낙차가 가장 크게 생길 수 있는 지점은 블럭 탑의 꼭대기이라는 것이다.
그렇기 때문에 블럭 탑에서 낙차의 max 값은 어차피 꼭대기 블럭 하나의 낙차와 같다.
2중 배열을 돌면서 모든 블럭의 낙차를 계산하지 말고, 그 탑의 꼭대기 블럭의 낙차를 계산 후, max값을 찾아주면 된다.
2중 for문을 쓸건데, 첫번째 for문에서는 낙차 값을 초기화시켜준다.
T = int(input())
for tc in range(1, 1+T):
N = int(input())
arr = list(map(int, input().split()))
MAX = 0
for t in range(N - 1, -1, -1):
cnt = 0
지금 쓰면서 생각한건데 굳이 range를 거꾸로 갈 필요는 없다.
그냥 range(N)써도 된다는 뜻.
for s in range(t+1, N):
if arr[t]>arr[s]:
cnt+=1
if cnt>MAX:
MAX = cnt
print(f'#{tc} {MAX}')
내가 낙차 찾고자 하는 탑의 다음꺼부터 끝까지중에, 내 탑보다 크기가 작으면 낙차+1, 아니면 +0을 하면 된다.
그리고 마지막엔 MAX값과 비교하기
이 방법을 쓰면 저번 풀이처럼 M의 길이에 따른 영향을 받지 않아도 된다.
그리고 2중 for문이기 때문에 시간도 단축된다.
전체코드)
T = int(input())
for tc in range(1, 1+T):
N = int(input())
arr = list(map(int, input().split()))
MAX = 0
for t in range(N - 1, -1, -1):
cnt = 0
for s in range(t+1, N): # 지금 확인하고자 하는 다음칸~끝칸까지
if arr[t]>arr[s]: #높이가 더 높아야 낙차가 생김
cnt+=1
if cnt>MAX:
MAX = cnt
print(f'#{tc} {MAX}')
'파이썬 알고리즘' 카테고리의 다른 글
SWEA 4893 이진탐색 (list1) (1) | 2022.09.20 |
---|---|
SWEA 전기버스 풀이2: 재귀 활용해서 풀기 (3) | 2022.09.20 |
재귀 DFS 문제: 단어 최소 사용 개수 구하기 (0) | 2022.09.18 |
SWEA 1210 사다리 (1) | 2022.09.16 |
SWEA 1216 회문2 (1) | 2022.09.16 |