알고리즘 #0010

• 문제 링크: 바로가기 (클릭)

I. 문제 상황

1. 초기 코드 작성

• 주어진 문제에 따라 배열을 만들고 슬라이싱해야 한다.
• 아래의 [코드 1]처럼 코드를 작성한다.

---

• [코드 1] 처음 작성한 코드 답안
  

2. 실행 결과

• 일부 테스트 케이스에서 시간 초과가 발생되었다.
• [결과 1]
  

II. 문제 분석

1. 시간 복잡도 계산

• 입력 제한 사항은 아래와 같다.
  

---

• 또한 [코드 1]에서 이중 for문을 사용하기 때문에 시간 복잡도는 O(n$^2$)이다.

2. 코드 수정

• 시간 복잡도를 낮추기 위해 단일 for문 사용을 고려해봐야 한다.
• 이를 위하여 일차원 배열 answer에 들어갈 값의 규칙을 파악해야 한다.
• [코드 1]의 이중 for문에서 일차원 배열 arr의 인덱스 값은 (i-1)*n + (j-1)이었다.
• 이를 역으로 이용하여 row와 col의 값을 이용하면 아래와 같은 식이 나온다.
• [코드 2]
  

---

• 전체 코드는 아래와 같다.
• [코드 3]
  

3. 결과

• [결과 2]