백준 14659 (한조서열정리하고옴ㅋㅋ) [Python/파이썬] [Greedy/그리디] +) Pypy3

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

14659번: 한조서열정리하고옴ㅋㅋ

 

---

나:

N = int(input())
heights= list(map(int,input().split()))
result =0

for i in range(N-1): 
    count = 0
    for j in range(i+1,N):
        if heights[i] > heights[j]:
            count +=1
            if result <  count:
                result =count
        else:
            if result <  count:
                result =count
            break

print(result)

완성된 코드는 위와 같다, 

솔직한 고백을 하자면 위 코드는 Python 으로 작성했지만 제출은 Pypy3 로 해서 정답에 해당하는 코드다.  

내가 생각하기에 만족스러운 코드 구현은 아니지만 일단 성공했기에 글을 올리고

Pypy3는 파이썬3의 문법을 그대로 지원하며, 대부분 파이썬3보다 실행 속도가 더 빠르다. 이 말은 Python 을 제출했을 때 시간초과가 난다면 동일한 코드를 Pypy3를 통해 제출 했을 떄 실행시간을 줄여 정답이 될 수 있고 위 경우가 바로 이 경우에 해당한다.

특히 반복문이 많을수록 Pypy3 가 파이썬 보다 빠른 경우가 많으니 Pypy3 를 지원한다면 적극 이용하자

 

(1)
N = int(input())
heights= list(map(int,input().split()))
result =0

우선 봉우리의 수 겸 활잡이의 수 N이 주어진다. 

그 다음 N개 봉우리의 높이가 왼쪽 봉우리부터 순서대로 주어진다. 

최종적으로 처치할 수 있는 적의 최대 숫자를 출력하기 위해 result 변수를 선언함.

 

(2)
for i in range(N-1): 
    count = 0
    for j in range(i+1,N):
        if heights[i] > heights[j]:
            count +=1
            if result <  count:
                result =count
        else:
            if result <  count:
                result =count
            break

print(result)

내가 구현하고 한것은 이중 반복문을 이용해 왼쪽 봉우리 순서대로 기준을 정해 그 다음 봉우리가 작으면 숫자를 세는 코드를 만들고자 했다.

첫번 째 반복문의 끝 범위는 N-1  이다. -1을 사용한 이유는 어짜피 마지막 봉우리의 경우는 그다음 봉우리가 존재하지 않으니 생각할 필요가 없어서도 있고 마지막 봉우리까지 반복문에 넣을경우 두번쨰 반복문에서 outofrange 가 발생하기 때문이다.

그리고 새로운 봉우리가 기준이 될때마다  처치 가능한 적의 숫자를 0부터 세야 하니 count = 0 을 해주었다.

두번 째  반복문의 첫 범위는 첫번 쨰 반복문의 기준 봉우리 다음부터해서 마지막 봉우리 까지 탐색하도록 했다. 탐색을 할 때 봉우리가 기준봉우리 보다 낮으면 적 처치를 나타내는 count를 +1 한다.

이때 만약 계속해서 기준봉우리가 클 경우 else 구문을 통해 적 처치를 나타내는 reuslt 값을 갱신 시킬수 없다. 그래서 if 절을 또 사용해 뒤의 else 구문처럼 result 값을 갱신할 수 있게 만들었다.

 

 

---

다른사람

ex_1 )

출처: twinoa 님

count = []
best_archery = -1
temp_cnt = 0

N = int(input()) # 봉우리(활잡이) 수 N 입력
arr = list(map(int, input().split())) # 봉우리 배열 입력

# 배열 처음부터 끝까지 반복
for i in arr : 
    
    # 만약 이전 값보다 현재값이 작으면 count + 1
    if best_archery > i : 
        temp_cnt += 1
    
    # 이전보다 크거나 같으면 이전값을 현재값으로 변경, count 초기화 및 배열에 저장
    else : 
        best_archery = i
        count.append(temp_cnt)
        temp_cnt = 0
else : 
    count.append(temp_cnt)
        
# count 배열 중 가장 큰 값 출력
print(max(count))

완성된 코드는 위와같다.

자세한 설명은 이분이 적은 주석에 나와있으니 주석을 통해 천천히 곱씹으면서 보면 좋을 듯 하다. 

다만 이전 값이 현재값보다 계속 클 경우를 대비해서 반복문 밖 else 구문을 이용해 처치된 적의 수를 count 리스트에 담음에 주목

 

---

ex_2) 

출처: verymanycoins 님

import sys

input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))

maxx = ans = cnt = 0
for x in arr:
    if maxx < x:
        maxx = x
        cnt = 0
        continue
    cnt += 1
    ans = max(ans, cnt)

print(ans)

완성된 코드는 위와같다.

반복문 한번으로 구현하는 생각을 이처럼 할수 있도록 생각할 필요가 있어서 집어넣었다.

그리고 리스트에 적 처치 숫자를 모아두지 않고 max 를 이용해 그때마다 판단해서 갱신한 값 하나만 갖도록 하는 부분에 주목할 필요가 있다.