1021: 연속된 최장 길이

Link : judge.koreatech.ac.kr/problem.php?id=1021

---

1. 문제

• 순열이 주어질 때, 연속으로 증가하는 수의 최장 길이를 구해주세요.
  연속으로 증가한다는 의미는, i+1 번째 수가 i번째 수보다 1이 큰 경우 입니다. 예를들어 1, 2, 3, 5, 6 의 연속된 최장 길이는 "1, 2, 3" 으로 답이 3이 됩니다.

 

---

2. 문제의 조건

• 0 <= n <= 10 (순열 길이)
• 32bit singed integer

 

---

3. 문제 접근

• 시간 복잡도
  
  1초의 시간에 100T * 10L = 1000개를 계산할 수 있어야하므로 O(N^2.66) 시간 내에 계산할 수 있으면 된다고 생각하였습니다.
  
  
  
• 아이디어
  
  stack을 이용해도 되겠지만 배열로 처리하는 것이 더 좋다고 생각하였습니다.
  for로 1부터 len(arr) 까지 만약 (A)arr[i] - 1 == arr[i - 1] 이라면 pres(연속)을 1씩 증가합니다.
  단, 순열의 길이가 1이상이면 최소의 답은 1이기때문에 pres는 1부터 시작합니다.
  만약! (A)가 아닐 경우, pres가 max_length 보다 더 크면 max_length를 갱신시켜주며 pres를 1로 초기화시켜주면 된다고 판단하였습니다.
  
  즉, O(N)의 시간에 끝낼 수 있습니다.

 

---

4. 풀이 방법

• 1부터 len(arr)까지 탐색을 진행합니다.
• 1부터 시작했으므로 arr[i]와 arr[i-1]를 비교하고
  조건에 부합하면 pres++ 로 증가시킵니다.
• 만약 조건에 부합하지 않으면 최대값과 pres를 비교하여 최대값을 갱신시키고, pres을 1초 초기화 해줍니다.
• len(arr)에 도달하였을 때, for문을 벗어나며 한번 더 최대값과 pres를 비교하고 갱신시킵니다.

 

 

---

5. 소스코드

• cjw-git.tistory.com/30

 

---

 

cjw.git@gmail.com