1회 테코테코

 

[2024-09-15] 10:00 ~ 12:00

---

≣ 목차

---

요약

- 부동 소수점 - Math 클래스 사용, BigDecimal

https://oliveyoung.tech/blog/2023-10-11/settlement-floation-point/

부동소수점 이야기 | 올리브영 테크블로그

- 문자열 - StringBuilder, StringBuffer (시간 복잡도)

  - immutable (+로 계속 만들면 객체가 계속 새로 생김)

- for -> stream 성능 개선

  - for 사용 시 O(n^2)
  - stream distinct 사용 시 /O(n)
- Arrays.sort(): dual pivot quick sort(primitive) / tim sort (wrapper)
  - 시간 복잡도 O(NlogN)

---

배열

첫 번째 문제

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

프로그래머스

접근 방법

1. 중복 값을 제거하기 위해 Set 자료 구조를 이용한다.

2. 오름차순 정렬한다.

고민 포인트

• 초기에 Arrays.sort(numbers); numbers 를 오름차순 정렬한 후, Set 에 추가하면 최종적으로 정렬을 할 필요가 없어질 것이라고 생각했지만 최종적으로 sorted() 를 통해 정렬해야 정답 처리가 되었다.
• 이 문제에서 히든 테스트 케이스에서는 오름차순 정렬을 하지 않으면 실패지만, 기본 테스트 케이스에서 우연히 정렬이 되어 정답 처리가 되었다.
• 반례를 찾는 것이 중요하다.
• Arrays.sort() 와 stream().sorted() 메서드를 이용해서 정렬을 할 경우, 동일한 값이 반환되지 않을 수 있다.

최종 코드 및 회고

• IntStream.range() 를 통해 for 문을 쉽게 stream 형태로 변경할 수 있다.

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

class Solution {
    public int[] solution(int[] numbers) {
        
        Set<Integer> set = new HashSet<>();
        
        IntStream.range(0, numbers.length-1).forEach(i -> 
            IntStream.range(i+1, numbers.length).forEach(j -> 
                set.add(numbers[i] + numbers[j])
            )
        );
        return set.stream().sorted().mapToInt(Integer::intValue).toArray();
    }
}

 

Arrays.sort(), stream().sorted() 유의할 점은?

예시

• 오름차순 정렬 & 반환

🚨 실패하는 코드(히든 테스트 케이스)

Arrays.sort(results.toArray()); 를 통해, results(Set) 값을 오름차순 정렬하고 반환하는 것을 기대했다.

정렬되지 않고 반환되는 문제가 발생했다.

 

실패 이유: results 를 정렬할 경우, results Set 객체가 오름차순 정렬되는 것이 아니라,
오름차순 정렬된 "새로운" 객체를 만들어서 저장한다. 따라서, 반환할 경우 정렬되지 않은 결과가 반환되는 것이다.

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

class Solution {
 	public int[] solution(int[] numbers) {

		Set<Integer> results = new HashSet<>();

		IntStream.range(0, numbers.length).forEach(i ->
			IntStream.range(i + 1, numbers.length).forEach(j ->
				results.add(numbers[i] + numbers[j])
			)
		);

		Arrays.sort(results.toArray());

		return results.stream().mapToInt(Integer::intValue).toArray();
	}
}

🚨 성공하는 코드

stream().sorted() 를 통해 오름차순 정렬된 정확한 결과를 반환하고 있다.

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

class Solution {
 	public int[] solution(int[] numbers) {

		Set<Integer> results = new HashSet<>();

		IntStream.range(0, numbers.length).forEach(i ->
			IntStream.range(i + 1, numbers.length).forEach(j ->
				results.add(numbers[i] + numbers[j])
			)
		);

		return results.stream().sorted().mapToInt(Integer::intValue).toArray();
	}
}

 

정렬 방식

Arrays.sort()

primitive - 듀얼 피봇 퀵 소트(Dual-Pivot QuickSort): 일반적인 퀵정렬과 달리 피봇을 2개 두고, 3개의 구간을 만든다.

  - int[], double[]...

  - 평균 O(nlogn)

wrapper - 팀 소트(Tim Sort): 삽입 정렬(Binary Insertion Sort)과 합병 정렬을 결합하여 만든 정렬이다.

  - Integer[], String[]...

  - 최선 O(n), 평균 O(nlogn), 최악 O(nlogn)

  - 추가 메모리는 사용하지만 기존의 Merge Sort 에 비해 적은 추가 메모리를 사용한다.

  - 다른 O(nlogn) 정렬 알고리즘의 단점을 최대한 극복한 알고리즘이다.

https://d2.naver.com/helloworld/0315536

 

Collections.sort()

- List 인터페이스를 구현한 컬렉션(ArrayList, LinkedList) 등에서 사용한다.

- Tim sort

- 평균 시간 복잡도 O(nlogn)

 

stream().sorted()

- Stream API

- 원본 데이터를 변경하지 않고, 새로 정렬된 stream 을 반환한다.

- 평균 시간 복잡도 O(nlogn)

---

두 번째 문제

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

프로그래머스

접근 방법

1. 모듈러 연산을 통해 인덱스를 반복 시켜서 접근한다.

2. 값이 동일할 경우 정답 횟수(answer) 에 추가한다.

3. 최댓값과 동일한 경우, 해당하는 인덱스+1 값을 반환한다.

고민 포인트

• 반복되는 인덱스를 모듈러 연산을 통해 접근한다.

최종 코드 및 회고

• 코딩 테스트를 풀면서 문제 풀기에 급급했지 내 코드의 시간 복잡도를 분석해보지 못했었다.
• 스터디에서 문제 풀이 발표를 하면서, 스터디원들의 조언으로 시간 복잡도를 생각해보게 되었다.
  • 내 코드의 시간 복잡도: O(3N)
  • 최댓값을 구하고 인덱스 값을 반환하는 부분은 3회 이므로, 시간 복잡도에 추가하지 않는다.

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

class Solution {
    public int[] solution(int[] answers) {
        
        int[] one = new int[]{1, 2, 3, 4, 5};
        int[] two = new int[]{2, 1, 2, 3, 2, 4, 2, 5};
        int[] three = new int[]{3, 3, 1, 1, 2, 2, 4, 4, 5, 5};
        
        //정답 횟수
        int[] answer = new int[3];
        for (int i = 0; i < answers.length; i++) {
            if (one[i % 5] == answers[i]) answer[0]++;
            if (two[i % 8] == answers[i]) answer[1]++;
            if (three[i % 10] == answers[i]) answer[2]++;
        }
        //최댓값
    	int max = Arrays.stream(answer).max().getAsInt();
        
        return IntStream.range(0, 3)
            .filter(i -> answer[i] == max)
            .map(i -> i + 1) //index
            .toArray();
    }
}