[Python] Softeer - 징검다리

[Python] Softeer - 징검다리

 

 

https://softeer.ai/app/assessment/index.html?xid=41191&xsrfToken=2TZ5K6MhQvCQl7OCoJmQ5ESvJIAFwdCh&testType=practice

Candidate | Softeer Assessment UI

 

문제설명

남북으로 흐르는 개울에 동서로 징검다리가 놓여져 있다.

 

이 징검다리의 돌은 들쑥날쑥하여 높이가 모두 다르다. 철수는 개울의 서쪽에서 동쪽으로 높이가 점점 높은 돌을 밟으면서 개울을 지나가려고 한다.

 

돌의 높이가 서쪽의 돌부터 동쪽방향으로 주어졌을 때 철수가 밟을 수 있는 돌의 최대 개수는?

제약조건

1 ≤ N ≤ 3×103 인 정수

1 ≤ Ai ≤ 108 인 정수

입력형식

첫 번째 줄에 돌의 개수 N이 주어진다.

두 번째 줄에 돌의 높이 Ai (1 ≤ i ≤ N)가 서쪽부터 동쪽으로 차례로 주어진다.

출력형식

첫 번째 줄에 철수가 밟을 수 있는 돌의 최대 개수를 출력하라.

입력예제1

5 3 2 1 4 5

출력예제1

3

구현 코드

import sys

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

arr= list(map(int, sys.stdin.readline().split()))

dic = {}
num_list = []

for idx, value in enumerate(arr):
  if idx==0:
    dic[value] = 1
  else:
    max=0
    for i in range(len(arr[:idx])):
      if arr[i] < value:
        if dic[arr[i]]>max:
          max=dic[arr[i]]
          
    dic[value] = max+1

maxCount = 0
for k, v in dic.items():
  # print(k, v)
  if v > maxCount:
    maxCount = v


print(maxCount)

 

 

설명

- 간단한 그리디 알고리즘

- 철수가 동쪽으로 진행하면서 서쪽에서 동쪽으로 이동 가능한 돌을 판별하는 방식으로 동작

- 동쪽 돌의 높이가 더 높거나 같으면 해당 서쪽 돌은 밟을 수 없게 되며, 반대로 서쪽 돌의 높이가 더 높거나 같으면 동쪽 돌은 밟을 수 없음

- 각 돌에 대해 밟을 수 있는지 여부를 판단하고, 그 결과를 합산하여 최대로 밟을 수 있는 돌의 개수를 계산
- 시간복잡도: O(N), N은 돌의 갯수