Skip to content

Files

Latest commit

6319387 Β· Oct 31, 2023

History

History

0456-132-pattern

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
Sep 30, 2023
Oct 31, 2023

Medium


ν›„κΈ°

square time으둜 μ§œλ„ μ΅œμ ν™”λ§Œ 잘 ν•˜λ©΄ 톡과가 되긴 ν•©λ‹ˆλ‹€.

λ‹€λ§Œ O(N log N), μ‹¬μ§€μ–΄λŠ” μ„ ν˜• μ‹œκ°„κΉŒμ§€ λ…Έλ €λ³Ό 수 μžˆλŠ” λ¬Έμ œμž…λ‹ˆλ‹€. λ‘˜ λ‹€ 정말 λ…μ°½μ μ΄μ—ˆμŠ΅λ‹ˆλ‹€. κ·Έ μ€‘μ—μ„œ 더 λΉ λ₯Έ 것에 μ§‘μ€‘ν•˜λŠ” 것이 μ’‹μœΌλ‹ˆ, μ„ ν˜• μ‹œκ°„ 풀이λ₯Ό μžμ„Ένžˆ λ΄…μ‹œλ‹€.

  • 기반 아이디어도 μΈμƒμ μž…λ‹ˆλ‹€.
  • μ‚¬μš©ν•œ μ•Œκ³ λ¦¬μ¦˜λ„ κ½€λ‚˜ 유λͺ…ν•œ, 자주 λ“±μž₯ν•˜λŠ” ν…Œν¬λ‹‰μž…λ‹ˆλ‹€. (λ‹€λ§Œ κ²½ν—˜μ μœΌλ‘œ, 이 ν…Œν¬λ‹‰μ΄ ν˜„μ—…μ—μ„œ 자주 λ“±μž₯ν•˜μ§€λŠ” μ•Šμ„ 것 κ°™μŠ΅λ‹ˆλ‹€. μ˜€λ‘œμ§€ λ¬Έμ œν’€μ΄ μš©λ„μΌ κ²λ‹ˆλ‹€.)

잘 λͺ¨λ₯΄κ² λ”라도 슀포 λ‹Ήν•  κ°€μΉ˜κ°€ μΆ©λΆ„νžˆ μžˆμŠ΅λ‹ˆλ‹€.

μ„€λͺ…을 쑰금 μžμ„Ένžˆ μ μ–΄λ’€λŠ”λ°, 도움이 λ˜μ…¨μœΌλ©΄ μ’‹κ² μŠ΅λ‹ˆλ‹€.

풀이

핡심 아이디어뢀터 λ΄…μ‹œλ‹€.

132 둜 μ ‘κ·Όν•˜λŠ” 건 κ½€ κΉŒλ‹€λ‘­μŠ΅λ‹ˆλ‹€. λͺ¨λ“  μœ νš¨ν•œ ꡬ간을 μ €μž₯ν•˜κ³ , κ·Έ ꡬ간듀 쀑 μ–΄λ”˜κ°€μ— μ†ν•˜λŠ”μ§€ 체크해봐야 ν•˜κΈ° λ•Œλ¬Έμž…λ‹ˆλ‹€. λ¬Όλ‘  이진 탐색을 잘 μ¨μ„œ O(N log N)으둜 쀄여볼 μ‹œλ„λŠ” ν•  수 μžˆκ² μ§€λ§Œ, μ½”λ“œκ°€ μ›Œλ‚™ λ³΅μž‘ν•΄μ§ˆ 것 κ°™λ„€μš”.

κ·Έλž˜μ„œ, 배열을 λ’€μ§‘μ–΄λ΄…μ‹œλ‹€. 231 λ¬Έμ œκ°€ λ©λ‹ˆλ‹€. 그러면 접근법이 μ΄λ ‡κ²Œ λ°”λ€λ‹ˆλ‹€.

  • μ§€κΈˆκΉŒμ§€ μ²΄ν¬ν•œ μˆ«μžλ“€μ„ 2 후보라고 ν•©μ‹œλ‹€. κ·Έ μˆ˜λ³΄λ‹€ 큰 수(3)κ°€ λ“€μ–΄μ™”λ‹€λ©΄ μœ νš¨ν•œ 2κ°€ λ©λ‹ˆλ‹€.
  • μƒˆ μˆ«μžκ°€ 듀어왔을 λ•Œ, κ·Έ μˆ«μžκ°€ μœ νš¨ν•œ 2쀑 ν•˜λ‚˜λ³΄λ‹€ μž‘μœΌλ©΄ μœ νš¨ν•œ 1이 λ©λ‹ˆλ‹€. λ”°λΌμ„œ 231을 찾은 κ²ƒμœΌλ‘œ μ•Œκ³ λ¦¬μ¦˜μ΄ μ’…λ£Œλ©λ‹ˆλ‹€.
  • μ–΄λ–€ μ‹œμ μ—μ„œ μœ νš¨ν•œ 2κ°€ μ—¬λŸ¬κ°œ μžˆμ„ λ•Œ, κ·Έ μ€‘μ—μ„œ κ°€μž₯ 큰 κ²ƒλ§Œ 보면 λ©λ‹ˆλ‹€. λ‚˜λ¨Έμ§€λŠ” 버렀도 λ©λ‹ˆλ‹€.

ꡬ간을 기둝할 ν•„μš”λ„ μ—†μ–΄μ‘Œκ³ , λͺ¨λ“  μœ νš¨ν•œ 것듀을 기둝할 ν•„μš”λ„ μ—†μ–΄μ‘ŒμŠ΅λ‹ˆλ‹€. λ¬Έμ œκ°€ 더 κ°„κ²°ν•΄μ‘Œμ£ .


이제 이 접근법을 μ„ ν˜• μ‹œκ°„μœΌλ‘œ κ΅¬ν˜„ν•  ν…Œν¬λ‹‰μ„ μ†Œκ°œν•˜κ² μŠ΅λ‹ˆλ‹€. λ°”λ‘œ λͺ¨λ…Έν† λ‹‰ μŠ€νƒμž…λ‹ˆλ‹€. μŠ€νƒμ€ κ·Έλƒ₯ ν‰λ²”ν•˜κ²Œ λ‚΄μž₯ λΌμ΄λΈŒλŸ¬λ¦¬μ—μ„œ κ°–λ‹€ μ”λ‹ˆλ‹€. λŒ€μ‹  저희가 μ½”λ“œλ₯Ό 잘 μ§œμ„œ μŠ€νƒμ— λ“  값듀이 항상 λͺ¨λ…Έν† λ‹‰ν•˜λ„둝 μœ μ§€ν•˜λŠ” ν…Œν¬λ‹‰μž…λ‹ˆλ‹€. κ·Έλž˜μ„œ ν…Œν¬λ‹‰μ΄λΌλŠ” ν‘œν˜„μ„ μΌμŠ΅λ‹ˆλ‹€.

μ΄λ•Œ λͺ¨λ…Έν† λ‹‰μ€, λͺ¨λ“  μ›μ†Œκ°€ 항상 증가(a[i-1] ≀ a[i])ν•˜κ±°λ‚˜ 항상 κ°μ†Œ(a[i-1] β‰₯ a[i])ν•˜κ±°λ‚˜λ₯Ό μ˜λ―Έν•©λ‹ˆλ‹€. λ‹Ήμ—°νžˆ λ‘˜ 쀑 ν•˜λ‚˜λ§Œ κ°€λŠ₯ν•©λ‹ˆλ‹€.

λŒ€μ²΄λ‘œ νŒ¨ν„΄μ€ μ΄λ ‡μŠ΅λ‹ˆλ‹€. μ¦κ°€ν•˜λŠ” μŠ€νƒ κΈ°μ€€μœΌλ‘œ λ΄…μ‹œλ‹€. μˆ˜μ—΄μ„ μˆœνšŒν•˜λ©΄μ„œ μŠ€νƒμ— 값을 λ„£μŠ΅λ‹ˆλ‹€. λ§Œμ•½ ν˜„μž¬ μ›μ†Œκ°€ μŠ€νƒ 탑보닀 크닀면, κ·Έλƒ₯ ν‘Έμ‹œν•˜λ©΄ λ©λ‹ˆλ‹€. λ§Œμ•½ ν˜„μž¬ μ›μ†Œκ°€ μŠ€νƒ 탑보닀 μž‘λ‹€λ©΄, ν‘Έμ‹œν•˜λ©΄ λͺ¨λ…Έν† λ‹‰μ΄ κΉ¨μ§‘λ‹ˆλ‹€. κ·Έλž˜μ„œ ν˜„μž¬ μ›μ†Œλ³΄λ‹€ μž‘μ€ 것듀을 λͺ¨μ‘°λ¦¬ popν•΄μ„œ, λͺ¨λ…Έν† λ‹‰μ΄ λ˜λ„λ‘ μˆ˜λ™μœΌλ‘œ λ§Œλ“­λ‹ˆλ‹€. κ·Έ λ‹€μŒ μ‚΄ν¬μ‹œ ν‘Έμ‹œν•˜λ©΄ λ©λ‹ˆλ‹€.

이 μΉœκ΅¬λŠ” μ•„μ£Ό μ‚¬κΈ°μ μž…λ‹ˆλ‹€. μ‚¬μš©ν•  수 μžˆλŠ” 상황이라면, 무쑰건 O(N)의 μ‹œκ°„λ³΅μž‘λ„λ₯Ό 보μž₯ν•˜κΈ° λ•Œλ¬Έμž…λ‹ˆλ‹€. κ·Έλž˜μ„œ λ¬Έμ œκ°€ N^2μ •λ„λ‘œ μž…λ ₯ 배열을 탐색해야 ν•  κ²ƒμ²˜λŸΌ λ³΄μ΄λŠ”λ°, 막상 N이 μ‹­λ§Œ 이상이라면, λͺ¨λ…Έν† λ‹‰ μŠ€νƒ μ‘μš© 문제일 κ°€λŠ₯성을 ν•œ 번쯀 생각해봐야 ν•©λ‹ˆλ‹€.

λ°±μ€€μ—μ„œ κ΄€λ ¨ λ¬Έμ œλŠ” κ³¨λ“œ4~ν”Œλ ˆ3κΉŒμ§€ λΆ„ν¬ν•˜κ³  μžˆλŠ” κ±Έ λ΄€μŠ΅λ‹ˆλ‹€. λ‚œμ΄λ„ 높은 μŠ€νƒ λ¬Έμ œλŠ” 거의 λ‹€ 이거라고 λ³΄μ‹œλ©΄ λ©λ‹ˆλ‹€. 17298번 κ³¨λ“œ4 μ˜€ν°μˆ˜κ°€ 유λͺ…ν•œ λ¬Έμ œμ€‘ ν•˜λ‚˜μΈλ°, μžμž˜ν•œ 쑰건이 μ—†μ–΄μ„œ 이 ν…Œν¬λ‹‰ μž…λ¬Έμš©μœΌλ‘œ κ°•μΆ”ν•©λ‹ˆλ‹€. (ꡬ글링해가며 이해될 λ•ŒκΉŒμ§€ ν•΄λ³΄μ‹œκΈΈ μΆ”μ²œλ“œλ €μš”.) 특히 1725번 ν”Œλ ˆ5 νžˆμŠ€ν† κ·Έλž¨ λ¬Έμ œκ°€ μ•„μ£Ό 유λͺ…ν•œ μœ ν˜•μž…λ‹ˆλ‹€. μ΄κ²ƒλ§Œ 잘 읡히면 ν”Œλ ˆ 문제 λͺ‡ 개λ₯Ό λ‚ λ¨Ήν•  수 μžˆμŠ΅λ‹ˆλ‹€.

λ¦¬νŠΈμ½”λ“œμ—λŠ” λͺ¨λ…Έν† λ‹‰ μŠ€νƒ νƒœκ·Έκ°€ λ”°λ‘œ μžˆμŠ΅λ‹ˆλ‹€.


본격적인 ν’€μ΄μž…λ‹ˆλ‹€. μš°μ„  μƒμˆ ν•œ κ²ƒμ²˜λŸΌ 배열은 λ’€μ§‘μ—ˆμŠ΅λ‹ˆλ‹€.

β€œμœ νš¨ν•œ 2쀑 μ΅œλŒ“κ°’β€ λ³€μˆ˜λ₯Ό λ§Œλ“€μ–΄λ‘‘μ‹œλ‹€. 일단은 κ·Έλ ‡λ‹€κ³  가정해두고, μžμ„Έν•œ 것은 ν›„μˆ ν•˜κ² μŠ΅λ‹ˆλ‹€. 배열을 μˆœνšŒν•˜λ©΄μ„œ, μƒˆ μ›μ†Œκ°€ κ·Έ λ³€μˆ˜λ³΄λ‹€ μž‘λ‹€λ©΄ μœ νš¨ν•œ 1μ΄λ―€λ‘œ μΌκ³ λ¦¬μ¦˜μ„ 즉각 μ’…λ£Œμ‹œν‚΅λ‹ˆλ‹€.

이 λ¬Έμ œμ—μ„œλŠ” 단쑰 κ°μ†Œ(monotonic decreasing)λ₯Ό μ“Έ κ²λ‹ˆλ‹€. μƒˆ μ›μ†Œκ°€ μŠ€νƒ 탑보닀 μž‘λ‹€λ©΄, κ·Έλƒ₯ ν‘Έμ‹œν•©λ‹ˆλ‹€.

μƒˆ μ›μ†Œκ°€ μŠ€νƒ 탑보닀 큰 경우λ₯Ό λ΄…μ‹œλ‹€. 그러면 μŠ€νƒ 탑을 μœ νš¨ν•œ 2둜, μƒˆ μ›μ†Œλ₯Ό 3으둜 λ³Ό 수 μžˆμŠ΅λ‹ˆλ‹€. κ·Έλ ‡λ‹€λ©΄ 이후에 μœ νš¨ν•œ 2보닀 μž‘μ€ μˆ˜κ°€ λ°œκ²¬λœλ‹€λ©΄ 그것이 μœ νš¨ν•œ 1일 것이고, μ•Œκ³ λ¦¬μ¦˜μ΄ μ’…λ£Œλ˜κ² μ£ .

이런 λ°©μ‹μœΌλ‘œ μŠ€νƒ 탑을 popν•˜κ³ , popν•œ 숫자λ₯Ό β€œμœ νš¨ν•œ 2쀑 μ΅œλŒ“κ°’β€ λ³€μˆ˜μ— κΈ°λ‘ν•΄λ‘‘μ‹œλ‹€. 본래 κΈ°μ‘΄ μ΅œλŒ“κ°’λ³΄λ‹€ 더 큰지λ₯Ό νŒλ³„ν•˜κ³ μž max ν•¨μˆ˜ μ‚¬μš©μ„ κ³ λ €ν•΄μ•Ό ν•˜μ§€λ§Œ, 이 λ¬Έμ œμ—μ„œλŠ” β€œμœ νš¨ν•œ 2쀑 μ΅œλŒ“κ°’β€λ³΄λ‹€ 더 μž‘μ€ μˆ˜κ°€ 발견되면 즉각 μ•Œκ³ λ¦¬μ¦˜μ΄ μ’…λ£Œλ©λ‹ˆλ‹€. 즉, pop된 μˆ«μžκ°€ κΈ°μ‘΄ μ΅œλŒ“κ°’λ³΄λ‹€ μž‘μ€ κ²½μš°λŠ” μ• μ΄ˆμ— μŠ€νƒμ— 듀어가기도 전에 λλ‚˜λ―€λ‘œ κ³ λ €ν•˜μ§€ μ•Šμ•„λ„ λ©λ‹ˆλ‹€. λ˜ν•œ μŠ€νƒμ— λ‚¨μ•„μžˆλŠ” μˆ«μžλŠ” 항상 ν˜„μž¬ β€œμœ νš¨ν•œ 2쀑 μ΅œλŒ“κ°’β€λ³΄λ‹€ 크닀고 λ³Ό 수 μžˆμŠ΅λ‹ˆλ‹€.

λͺ¨λ…Έν† λ‹‰ μŠ€νƒμ˜ νŠΉμ§•μ€, μƒˆ μ›μ†Œμ— λŒ€ν•΄ popν•΄μ•Ό ν•˜λŠ” μˆ«μžκ°€ μ—¬λŸΏμΌ 수 μžˆλ‹€λŠ” κ²ƒμž…λ‹ˆλ‹€. κ·Έλž˜μ„œ while λ°˜λ³΅λ¬Έμ„ ν™œμš©ν•©λ‹ˆλ‹€. μƒˆλ‘œμš΄ μŠ€νƒ ν”Όν¬λŠ” 방금 popν•œ 것보닀 더 ν¬λ‹€λŠ” 점이 νŠΉμ§•μž…λ‹ˆλ‹€. (문제 μœ ν˜•μ— 따라 β€œκ°™κ±°λ‚˜ ν¬κ²Œβ€ μœ μ§€ν•˜κΈ°λ„, 단쑰 증가 μŠ€νƒμ„ 쓰기도 ν•©λ‹ˆλ‹€.)

λ§ˆμ§€λ§‰μœΌλ‘œ μƒˆ μ›μ†Œ κ·Έ μžμ²΄λ„ 2 ν›„λ³΄μ΄λ―€λ‘œ μŠ€νƒμ— λ„£μŠ΅λ‹ˆλ‹€.


이 λ‚΄μš©μ„ κ°ˆλ¬΄λ¦¬ν•œ 것이 μ•„λž˜ μ½”λ“œμž…λ‹ˆλ‹€. 생각보닀 κ°„κ²°ν•©λ‹ˆλ‹€.


Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j].

Return true if there is a 132 pattern in nums, otherwise, return false.

 

Example 1:

Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.

Example 2:

Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

Example 3:

Input: nums = [-1,3,2,0]
Output: true
Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

 

Constraints:

  • n == nums.length
  • 1 <= n <= 2 * 105
  • -109 <= nums[i] <= 109