정수를 대체하는 횟수는 ? : 중요한 기본기 + 재귀 , map

https://leetcode.com/problems/integer-replacement/solutions/3614937/java-hashmap-solution-using-memoization/

Java HashMap Solution Using Memoization - Integer Replacement - LeetCode

 

리트 코드의 문제이다.

문제를 해결하는 과정도 중요하지만, 문제를 푸는 방식도 중요하다.

 

1. 에지 케이스를 항상 생각하자 .

정수 값의 범위가 주어졌을때 양 끝 값이 들어오는 조건문을 항상 먼저 기입해두자.

 

2. 적절한 자료구조를 생각하면서 패턴을 찾자 .

패턴만 찾을려고하면 문제의 해결이 보이지 않거나 어렵게 푸는 경향이 있다라는 것을 알게 되었다 . 문제에 집중을 하되 지속적으로 머리 속의 자료구조를 뒤져보자.

 

복잡 한 패턴은 단순하게 접근할때 풀릴때가 많다.

숫자의 패턴이 안보이는 상태에서 , 주어진 조건을 넣어 완탐이 가능한 재귀함수를 생각하는 방법이 있다.

 

 

class Solution {
  Map<Integer, Integer> map = new HashMap<>();
  public int integerReplacement(int n){
    if (n == Integer.MAX_VALUE) return 32; //n = 2^31-1;
    if(n == 1) return 0;
    if(map.containsKey(n)) {
      return map.get(n);
    } else if(n % 2 == 0) {
      map.put(n, integerReplacement(n/2) + 1);
    } else {
      map.put(n, Math.min(integerReplacement(n+1), integerReplacement(n-1)) + 1);
    }
    return map.get(n);
  }
}