[leetcode] Minimum Number of Operations to Move All Balls to Each Box

medium 1769. Minimum Number of Operations to Move All Balls to Each Box

코드

• 첫 번째 풀이

  class Solution {
     public int[] minOperations(String boxes) {
         char[] balls = boxes.toCharArray();
         int boxLength = balls.length; // 박스 길이
         int[] answer = new int[boxLength];
  
         for (int i = 0; i < boxLength; i++) {
             int temp = 0;
             for (int j = 0; j < boxLength; j++) {
                 if (i != j && balls[j] == '1') {
                     temp += Math.abs(i - j);
                 }
             }
             answer[i] = temp;
         }
  
         return answer;
     }
  }

  • Runtime: 167 ms, Memory: 39.8 MB
  • 이중 for문 사용

• 두 번째 풀이(다시 풀어보기)

  • rigth, left 사용
  • 나의 왼쪽과 오른쪽에 있는 공들을 각각 계산하여 더하기
    • 한 칸씩 옮겨갈 때마다 공의 개수와 관련이 있다.
  • Runtime: ?, Memory: ?

---

배운 내용

• charAt()이 toCharArray()보다 빠르다
  • toCharArray() : char[]를 선언하기 때문에 조금 더 느리고 메모리를 더 사용한다.
  • charAt() : O(1)의 시간복잡도(Constant-Time Operation)
• s.length()를 초기화해놓는 이유: for에서 i < s.length() 구문을 사용하는 경우, 매 loop마다 s.length()를 부른다.
• String은 Reference 타입이라서 s == "~~"를 쓸 수 없다. s가 레퍼런스로 들어오기 때문. s.equals("~~")과 같이 작성해야 한다.

참고

• What is the easiest/best/most correct way to iterate through the characters of a string in Java?