[Conc & Sol] `for문` vs `향상된 for문` (cf. Iterator, ListIterator) & 역순 정렬 없이 큰 숫자 만들기

▼ Why ? What ?

 1일 1알고리즘 스터디에서 "숫자 짝꿍"이라는 문제를 풀다가 for문을 사용하여 `List`를 순회했을 경우에 요구되는 시간복잡도와 향상된 for문을 사용하여 `List`를 순회했을 경우에 요구되는 시간복잡도가 차이가 있다는 사실을 처음 알게되어 정리해두게 되었다.

---

▼ `for문` vs `향상된 for문` (cf. Iterator를 사용한 접근)

 

`for문`을 사용해 컬렉션(or 배열)을 순회하는 경우

 

• n번째 요소에 접근할 때, n-1번째 요소에서 접근하는 것이 아니라 !
  내부적으로 1번째 요소에서부터 순차적으로 n번을 반복해 접근하는 과정을 거친다 !
  ➙ 시간 복잡도 : O(n^2)
  
• while문과 같은 기본적인 반복문도 마찬가지이다.

List<Integer> list = new ArrayList<>();
// list에 요소 추가
for (int i = 0; list.size(); ++i) {
	// ...
}

 

---

 

`향상된 for문(for-each)` 사용

 

• 일반 for문과 달리 n번째 요소에 접근할 때, n-1번째 요소에서부터 접근 !
  ➙ 시간 복잡도 : O(n)
• 사실 향상된 for문은 내부적으로 `Iterator`를 기반으로 동작하기 때문에, 위와 같은 접근이 가능한 것이다 !
  ➙ 단, 순회 중 요소는 읽기만 가능하며 변경과 같은 작업은 불가능하다 !
  ( 그 이유는 당연하게도 원하는 인덱스(index)를 지정할 수 없기 때문에 ... )

List<Integer> list = new List<>();
// list에 요소 추가
for (Integer i : list) {
	System.out.println(i);
}

 

• `향상된 for문`을 컴파일(compile)하면 아래처럼 `Iterator`를 사용하여 순회하는 코드로 변환되는 것이다 !

List<Integer> list = new ArrayList<>();
// list에 요소 추가
Iterator<Integer> iter = list.ListIterator<>();
for (Iterator<Integer> iterator = list.iterator(); iterator.hasNext();)
	System.out.println(iter.next());]
}

 

---

 

요소에 직접적으로 접근하고 싶은 경우엔 `Iterator`를 이용

 

• 이 방식도 당연하게 n번째 요소에 접근할 때, n-1번째 요소에서부터 접근하기 때문에 효율적 !
  ➙ 아래와 같은 `remove()` 메서드를 이용하여 요소를 삭제하는 것은 가능하다 !

List<Integer> list = new ArrayList<>();
// list에 요소 추가
Iterator<Integer> iter = list.ListIterator<>();
for (Iterator<Integer> iterator = list.iterator(); iterator.hasNext();)
	System.out.println(iter.next());
    iter.remove(); // 현재 요소 삭제
}

 

---

 

양뱡향으로 순회 가능하며, 요소 수정도 가능한 `ListIterator`

 

Iterator

• 순방향으로 컬렉션을 순회하고, 요소를 읽고, 현재 요소를 제거할 수 있다.
  
  
• 메서드
  • hasNext(): 다음 요소가 있는지 확인.
  • next(): 다음 요소를 반환.
  • remove(): 현재 요소를 제거.
    
    
• 한계
  • 이전 요소로 이동하거나, 요소를 추가하거나, 현재 요소를 수정할 수 없다.
  • 모든 컬렉션에서 사용할 수 있지만, 제한된 기능만 제공한다.

---

ListIterator

• 주요 기능
  • Iterator의 모든 기능을 갖추고 있으며, 양방향으로 컬렉션을 순회할 수 있습니다.
  • 요소를 읽고, 추가하고, 제거하고, 수정할 수 있다.
  • List 인터페이스를 구현하는 컬렉션에서만 사용 가능 !
    
    
• 메서드
  • hasNext(): 다음 요소가 있는지 확인.
  • next(): 다음 요소를 반환.
  • hasPrevious(): 이전 요소가 있는지 확인.
  • previous(): 이전 요소를 반환.
  • nextIndex(): 다음 요소의 인덱스를 반환.
  • previousIndex(): 이전 요소의 인덱스를 반환.
  • remove(): 현재 요소를 제거.
  • set(E e): 현재 요소를 주어진 요소로 변경.
  • add(E e): 현재 위치에 주어진 요소를 추가.

 

---

▼ 알고리즘 문제 : "숫자 짝꿍"

 

숫자 짝꿍

https://school.programmers.co.kr/learn/courses/30/lessons/131128

프로그래머스

 

[ 나의 해결 코드 1 ]

• `ListIterator`를 이용하여 List를 순회한 경우

import java.util.*;   
import java.util.stream.*;

class Solution {
    public String solution(String X, String Y) {
        boolean isAllZero = false;
        HashMap<Character, Integer> yMap = new HashMap<>();
        
        for (char c : X.toCharArray()) {
            yMap.put(c, yMap.getOrDefault(c, 0) + 1); // 문자열의 각 숫자들이 몇 개인지 저장
        }
        
        List<Integer> list = new ArrayList<>(); // 공통으로 나타나는 숫자를 저장할 리스트
        
        for (char c : Y.toCharArray()) {
            if (yMap.getOrDefault(c, 0) > 0) { // 짝꿍 탐색
                yMap.put(c, yMap.get(c) - 1); // 짝꿍으로 체크된 숫자는 제거
                list.add(c - '0'); // 짝꿍으로 체크된 숫자를 리스트에 추가
            }
        }
        
        // 리스트에 들어있는 숫자로 만들 수 있는 최대 숫자 구하기
        Collections.sort(list, Collections.reverseOrder());
        
        ListIterator<Integer> iterator = list.listIterator();
        while (iterator.hasNext()){
             if (iterator.next() != 0) {
                 // 즉시 최대 숫자를 구하고 문자열로 만들어 반환
                return list.stream()
                       .map(String::valueOf) // Integer를 String으로 변환
                       .collect(Collectors.joining()); // 문자열로 결합
             }
             isAllZero = true;
        }
        
        // 모든 숫자가 0이면 "0", 빈 문자열이면 "-1"을 반환
        return isAllZero == true ? "0" : "-1";
    }
}

 

[ 나의 해결 코드 2 ]

• 향상된 for문을 이용하여 List를 순회한 경우

import java.util.*;   
import java.util.stream.*;

class Solution {
    public String solution(String X, String Y) {
        boolean isAllZero = false;
        HashMap<Character, Integer> yMap = new HashMap<>();
        
        for (char c : X.toCharArray()) {
            yMap.put(c, yMap.getOrDefault(c, 0) + 1); // 문자열의 각 숫자들이 몇 개인지 저장
        }
        
        List<Integer> list = new ArrayList<>(); // 공통으로 나타나는 숫자를 저장할 리스트
        
        for (char c : Y.toCharArray()) {
            if (yMap.getOrDefault(c, 0) > 0) { // 짝꿍 탐색
                yMap.put(c, yMap.get(c) - 1); // 짝꿍으로 체크된 숫자는 제거
                list.add(c - '0'); // 짝꿍으로 체크된 숫자를 리스트에 추가
            }
        }
        
        // 리스트에 들어있는 숫자로 만들 수 있는 최대 숫자 구하기
        Collections.sort(list, Collections.reverseOrder());
    
        for (Integer num : list) {
            if (num != 0) {
            	// 즉시 최대 숫자를 구하고 문자열로 만들어 반환
                return list.stream()
                       .map(String::valueOf) // Integer를 String으로 변환
                       .collect(Collectors.joining()); // 문자열로 결합
            }
            isAllZero = true;
        }
        
        return isAllZero == true ? "0" : "-1";
    }
}

 

[ 다른 스터디 부원의 해결 코드 ]

• 역순으로 정렬하기 위해서 머리 아픈 형 변환을 생각할 필요 없이, 큰 숫자부터 찾아서 문자열에 더해주는 방식으로 해결했다.
  ➙ 이런 문제가 나오면 역순 정렬 말고도 다른 편한 방식이 있는지도 생각해보자 !!

import java.util.*;

public String solution(String X, String Y) {

    // <Digit, 개수>
    Map<Integer, Integer> xMap = new HashMap<>();
    Map<Integer, Integer> yMap = new HashMap<>();

    for (String str : X.split("")) {
        int num = Integer.parseInt(str);
        xMap.put(num, xMap.getOrDefault(num, 0) + 1);
    }
    for (String str : Y.split("")) {
        int num = Integer.parseInt(str);
        yMap.put(num, yMap.getOrDefault(num, 0) + 1);
    }

    StringBuilder sb = new StringBuilder();
    for (int i = 9; i >= 0; i--) {
        if (xMap.containsKey(i) && yMap.containsKey(i)) {
            int cnt = Math.min(xMap.get(i), yMap.get(i));
            for (int j = 0; j < cnt; j++) {
                sb.append(i);
            }
        }
    }

    String answer = sb.toString();
    if (answer.startsWith("0")) {
        return "0";
    }
    if (answer.equals("")) {
        return "-1";
    }

    return answer;
}