23-08-01 TIL

문제

• 백준 19637 (좀 IF문 좀 대신 써줘) - Java

  • 이 문제를 처음 풀었을 때에 반복문을 중첩해서 풀었더니 시간초과가 났다.

  • 문제가 되었을 것이라 생각했던 부분은

    for (int i = 0; i < M; i++) {
                int score = Integer.parseInt(br.readLine());
    
                for (int j = 0; j < N; j++) {
                    if (score <= titleScore[j]) {
                        bw.write(title[j] + "\n");
                        break;
                    }
                }
            }

    이 부분의 코드인데, 현재 입력받는 점수가 저장되어 있는 구분 전투력의 점수보다 작은지 비교하는 부분이다. (작은 순으로 저장하기 때문에 인덱스 순서대로 비교해도 문제 없을 듯)

  • 헌데 시간초과가 났기 때문에 아마도 반복문을 중첩해서 일어난 문제라고 생각했다.

시도

• 백준 19637 (좀 IF문 좀 대신 써줘) - Java
  • 반복문을 중첩하지 않고 조건문을 걸 수 있는 방법, 혹은 다른 알고리즘으로 풀 수 있는지 생각해볼 시간이 꽤나 필요했다.
  • 오랜 시간 끝에 나온 결론은 '우선 다른 알고리즘은 어차피 생각이 나지 않으니 알고 있는 것들중에서 풀어보자'라는 것과 이것도 비교하는 것이니 때문에 이분 탐색 방법으로 풀 수 있는가라는 것이였다.
  • 하지만 이분 탐색도 결국 반복문 중첩이기는 한데... 일단은 한번 이분 탐색을 사용해보기로 하였다.
  • 이분 탐색 알고리즘을 또 또 또 까먹어서 예전에 TIL로 정리해두었던 문제 풀이를 참고해보기로 하였다.

해결

• 백준 19637 (좀 IF문 좀 대신 써줘) - Java
  • 아마도 문제는 반복문 중첩이라기 보다는 사이즈가 큰 문제여서 그랬던 것 같다.
  • 0부터 N 까지 조건문을 하나씩 보기 보다는 이분 탐색으로 찾는 것이 더 적은 시간이 걸리기 때문으로 보인다.
  • 0부터 N까지는 O(N)이지만 이분 탐색은 O(logN)이니까 더 빠른 듯
  • 일단 해결을 하기는 했지만 이분 탐색에 대해서 어떤 문제에서 어떻게 사용되는지 다시 공부를 할 필요성을 느꼈다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		// 첫 번째 라인 읽기
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        // 칭호 갯수
        int N = Integer.parseInt(st.nextToken());
        // 캐릭터 갯수
        int M = Integer.parseInt(st.nextToken());
		// 칭호 (WEAK, NORMAL...)
        String[] title = new String[N];
        // 칭호에 따른 전투력 점수
        int[] titleScore = new int[N];
        // 칭호와 전투력 각각 할당
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            String tmpTitle = st.nextToken();
            int tmpTitleScore = Integer.parseInt(st.nextToken());

            title[i] = tmpTitle;
            titleScore[i] = tmpTitleScore;
        }

        for(int i = 0;i < M;i++){
			// 입력 받은 전투력
            int currScore = Integer.parseInt(br.readLine());
			// 첫번째 인덱스
            int low = 0;
            // 마지막 인덱스
            int high = N - 1;
            // 가운데 인덱스
            int mid = (low + high) / 2;
			// 이분 탐색 -> 절반씩 줄여나가는 방법
            while (low <= high){
				
                mid = (low + high) / 2;
				// 전투력 중간 값이 현재 입력 받은 전투력보다 작으면
                // 첫번째 인덱스를 가운데 인덱스 + 1로 지정
                if(titleScore[mid] < currScore){
                    low = mid + 1;
                }
                // 전투력 중간 값이 현재 입력 받은 전투력보다 크거나 같으면
                // 마지막 인덱스를 가운데 인덱스 - 1로 지정
                else{
                    high = mid - 1;
                }
            }
            // low가 high가 되는 시점에서 끝이 나기 때문에
            // title[low]가 찾던 칭호 (low가 찾던 인덱스 위치)
            bw.write(title[low]+"\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

}

궁금해서 찾아본 사항

• Builder vs Constructor
  • 인스턴스를 생성할 경우 Contructor에 매개변수를 넣어서 생성한다.
  • 헌데, 매개변수의 갯수가 많아서 일일히 집어넣기 힘들거나, 혹은 특정한 필드만을 넣어서 생성하고 싶을 경우
  • 클래스에 @Builder를 선언하고, 클래스이름.builder.매개변수().build(); 과 같은 방식으로 특정한 객체를 생성할 수 있다.
    -> 꼭, builder를 사용하지 않고, 그냥 constructor에 setter를 사용하면 되지 않을까?
    -> 여러 번의 함수 호출로 객체 생성이 되어 일관성이 깨진다.
    -> 한 번의 함수 호출로 객체 생성되고, 원하는 변수만 삽입 가능한 Builder 패턴 사용 추천