[2025-02-13] SQL, Java 알고리즘 문제

이규정·2025년 2월 13일

1] SQL - 특정 기간동안 대여 가능한 자동차들의 대여비용 구하기

문제 설명
다음은 어느 자동차 대여 회사에서 대여 중인 자동차들의 정보를 담은 CAR_RENTAL_COMPANY_CAR 테이블과 자동차 대여 기록 정보를 담은 CAR_RENTAL_COMPANY_RENTAL_HISTORY 테이블과 자동차 종류 별 대여 기간 종류 별 할인 정책 정보를 담은 CAR_RENTAL_COMPANY_DISCOUNT_PLAN 테이블 입니다.

CAR_RENTAL_COMPANY_CAR 테이블은 아래와 같은 구조로 되어있으며, CAR_ID, CAR_TYPE, DAILY_FEE, OPTIONS 는 각각 자동차 ID, 자동차 종류, 일일 대여 요금(원), 자동차 옵션 리스트를 나타냅니다.

자동차 종류는 '세단', 'SUV', '승합차', '트럭', '리무진' 이 있습니다. 자동차 옵션 리스트는 콤마(',')로 구분된 키워드 리스트(예: ''열선시트,스마트키,주차감지센서'')로 되어있으며, 키워드 종류는 '주차감지센서', '스마트키', '네비게이션', '통풍시트', '열선시트', '후방카메라', '가죽시트' 가 있습니다.

CAR_RENTAL_COMPANY_RENTAL_HISTORY 테이블은 아래와 같은 구조로 되어있으며, HISTORY_ID, CAR_ID, START_DATE, END_DATE 는 각각 자동차 대여 기록 ID, 자동차 ID, 대여 시작일, 대여 종료일을 나타냅니다.

CAR_RENTAL_COMPANY_DISCOUNT_PLAN 테이블은 아래와 같은 구조로 되어있으며, PLAN_ID, CAR_TYPE, DURATION_TYPE, DISCOUNT_RATE 는 각각 요금 할인 정책 ID, 자동차 종류, 대여 기간 종류, 할인율(%)을 나타냅니다.

할인율이 적용되는 대여 기간 종류로는 '7일 이상' (대여 기간이 7일 이상 30일 미만인 경우), '30일 이상' (대여 기간이 30일 이상 90일 미만인 경우), '90일 이상' (대여 기간이 90일 이상인 경우) 이 있습니다. 대여 기간이 7일 미만인 경우 할인정책이 없습니다.

문제
CAR_RENTAL_COMPANY_CAR 테이블과 CAR_RENTAL_COMPANY_RENTAL_HISTORY 테이블과 CAR_RENTAL_COMPANY_DISCOUNT_PLAN 테이블에서 자동차 종류가 세단 또는 SUV 인 자동차 중 2022년 11월 1일부터 2022년 11월 30일까지 대여 가능하고 30일간의 대여 금액이 50만원 이상 200만원 미만인 자동차에 대해서 자동차 ID, 자동차 종류, 대여 금액(컬럼명: FEE) 리스트를 출력하는 SQL문을 작성해주세요. 결과는 대여 금액을 기준으로 내림차순 정렬하고, 대여 금액이 같은 경우 자동차 종류를 기준으로 오름차순 정렬, 자동차 종류까지 같은 경우 자동차 ID를 기준으로 내림차순 정렬해주세요.

1. 요구사항

세단 혹은 SUV
2022년 11월 1일 부터 2022년 11월 30일 까지 대여 가능
30일 간의 대여금액 : 50만원 이상 200만원 미만
출력 : car_id , car_type , FEE
정렬 : order by FEE desc, car_type, car_id desc

2. 문제 접근

(1) 대상 자동차 선정

CAR_RENTAL_COMPANY_CAR 테이블에서 CAR_TYPE이 '세단' 또는 'SUV'인 자동차만 선택

(2) 할인 정책 적용

CAR_RENTAL_COMPANY_DISCOUNT_PLAN 테이블과 조인
DURATION_TYPE이 '30일 이상'인 할인 정책 적용

30일 요금 계산:

FEE = DAILY_FEE * (1 - DISCOUNT_RATE/100.0) * 30

정수만 출력하기 위해 FLOOR() 함수 사용

(3) 대여 가능 여부 체크

CAR_RENTAL_COMPANY_RENTAL_HISTORY에서 2022-11-01 ~ 2022-11-30 사이에 대여된 자동차 제외

겹치는 대여 조건:

h.START_DATE <= '2022-11-30'
AND h.END_DATE   >= '2022-11-01'

NOT EXISTS 사용하여 해당 기간에 대여 기록이 없는 자동차만 선택

(4) 요금 조건 적용

계산된 30일 요금(FEE)이 500,000원 이상 2,000,000원 미만인 자동차 선택

(5) 정렬 조건

FEE 내림차순
CAR_TYPE 오름차순
CAR_ID 내림차순

3. 최종 SQL 코드

SELECT 
    c.CAR_ID,
    c.CAR_TYPE,
    FLOOR(c.DAILY_FEE * (1 - p.DISCOUNT_RATE / 100.0) * 30) AS FEE
FROM CAR_RENTAL_COMPANY_CAR c
JOIN CAR_RENTAL_COMPANY_DISCOUNT_PLAN p
    ON c.CAR_TYPE = p.CAR_TYPE
   AND p.DURATION_TYPE = '30일 이상'
WHERE c.CAR_TYPE IN ('세단', 'SUV')
  -- 2022년 11월 1일 ~ 11월 30일에 대여 기록이 없는 자동차만 선택
  AND NOT EXISTS (
      SELECT 1
      FROM CAR_RENTAL_COMPANY_RENTAL_HISTORY h
      WHERE h.CAR_ID = c.CAR_ID
        AND h.START_DATE <= '2022-11-30'
        AND h.END_DATE   >= '2022-11-01'
  )
  -- 30일간 대여 금액 조건: 50만원 이상 200만원 미만
  AND FLOOR(c.DAILY_FEE * (1 - p.DISCOUNT_RATE / 100.0) * 30) BETWEEN 500000 AND 1999999
ORDER BY FEE DESC, CAR_TYPE ASC, CAR_ID DESC;

4. 코드 설명

JOIN: 자동차 테이블과 할인 정책 테이블을 자동차 종류와 '30일 이상' 조건으로 조인
FEE 계산: FLOOR(c.DAILY_FEE * (1 - p.DISCOUNT_RATE / 100.0) * 30) 사용
대여 가능 여부: NOT EXISTS 서브쿼리로 2022-11-01 ~ 2022-11-30 기간에 대여된 자동차 제외
요금 조건: 계산된 FEE가 500,000원 이상 1,999,999원 이하인 경우만 선택
정렬: FEE 내림차순, CAR_TYPE 오름차순, CAR_ID 내림차순

[2025-02-13] SQL

EXIST 는 출력컬럼이 없어도 조회가 가능한 if문임.(부정은 NOT EXIST)

정수 변환은 floor()

2] Java 알고리즘 문제 - 신고 결과 받기

문제 설명
신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다.

다음은 전체 유저 목록이 ["muzi", "frodo", "apeach", "neo"]이고, k = 2(즉, 2번 이상 신고당하면 이용 정지)인 경우의 예시입니다.

각 유저별로 신고당한 횟수는 다음과 같습니다.

위 예시에서는 2번 이상 신고당한 "frodo"와 "neo"의 게시판 이용이 정지됩니다. 이때, 각 유저별로 신고한 아이디와 정지된 아이디를 정리하면 다음과 같습니다.

따라서 "muzi"는 처리 결과 메일을 2회, "frodo"와 "apeach"는 각각 처리 결과 메일을 1회 받게 됩니다.

이용자의 ID가 담긴 문자열 배열 id_list, 각 이용자가 신고한 이용자의 ID 정보가 담긴 문자열 배열 report, 정지 기준이 되는 신고 횟수 k가 매개변수로 주어질 때, 각 유저별로 처리 결과 메일을 받은 횟수를 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

입출력 예

입출력 예 설명

입출력 예 #1

문제의 예시와 같습니다.

입출력 예 #2

"ryan"이 "con"을 4번 신고했으나, 주어진 조건에 따라 한 유저가 같은 유저를 여러 번 신고한 경우는 신고 횟수 1회로 처리합니다. 따라서 "con"은 1회 신고당했습니다. 3번 이상 신고당한 이용자는 없으며, "con"과 "ryan"은 결과 메일을 받지 않습니다. 따라서 [0, 0]을 return 합니다.

제한시간 안내
정확성 테스트 : 10초

1. 요구사항

4. 코드 작성

답은 맞는데, 시간초과함.

import java.util.*;

class Solution {
    public int[] solution(String[] id_list, String[] report, int k) {
        int[] answer = new int[id_list.length];

        Set<String> real = new HashSet<>();
        for(String a : report){
            real.add(a);
        }
        
        int[] repNum = new int[id_list.length];
        String[] temp = new String[2];
        for(String a : real){
            temp = a.split(" ");
            for(int i = 0 ; i < id_list.length ; i++){
                if(id_list[i].equals(temp[1])){
                    repNum[i] ++;
                    break;
                }
            }
        }
        
        
        for(int i = 0 ; i < id_list.length ; i++){
            String tempId = "";
            if(repNum[i] >= k){
                tempId = id_list[i];
            } else {
                continue;
            }
            
            for(String a : real){
                temp = a.split(" ");
                if(temp[1].equals(tempId)){
                    for(int j = 0 ; j < id_list.length ; j++){
                        if(id_list[j].equals(temp[0])){
                            answer[j] ++;
                            break;
                        }
                    }
                }
            }
            
        }
        return answer;
    }
}

5. 문제점

코드 효율성 비교 및 개선 방안

아래는 기존 코드의 비효율적인 점과, 개선한 코드(맵 자료구조 활용)의 효율적인 점을 단계별로 설명하고, 이를 표로 정리한 내용입니다.

기존 코드의 비효율적인 점

사용자 인덱스 조회
- 문제점: 신고 내역을 처리할 때마다 id_list를 순회하여 해당 인덱스를 찾음 (O(n) 선형 검색).
- 영향: 사용자 수가 많아질 경우, 매번 전체 리스트를 순회하기 때문에 성능 저하 발생.
중복 신고 처리
- 문제점: 신고 문자열을 split(" ")로 분리할 때마다 반복 호출하여 처리하며, 중복 신고 제거를 위해 HashSet<String>을 사용하지만, 각 신고마다 중복 검사와 배열 접근이 이루어짐.
- 영향: 동일한 사용자의 신고가 여러 번 발생해도 매번 처리 로직이 반복되어 불필요한 연산 발생.
반복문 사용
- 문제점: 신고 당한 사용자와 신고한 사용자를 찾기 위해 다중 중첩 반복문을 사용함.
- 영향: 신고 건수와 사용자 수가 많을 경우, 최악의 경우 O(n * m) 시간 복잡도로 성능 저하를 초래함.
split() 호출
- 문제점: 각 신고마다 split(" ")를 반복 호출하여 문자열을 분리함.
- 영향: 불필요한 문자열 분리 연산으로 오버헤드 발생.
전체 시간 복잡도
- 문제점: 위의 문제들이 복합적으로 작용하여 신고 건수와 사용자 수가 많아질 경우 성능 문제가 발생함.
- 영향: 제한 시간 내에 처리가 어려워 속도 제한에 걸릴 가능성이 높음.

개선 코드

import java.util.*;

class Solution {
    public int[] solution(String[] id_list, String[] report, int k) {
        int n = id_list.length;
        int[] answer = new int[n];
        
        // 1. 사용자 ID와 인덱스를 매핑하는 Map 생성
        Map<String, Integer> idIndexMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            idIndexMap.put(id_list[i], i);
        }
        
        // 2. 신고 내역을 처리: 신고 당한 사용자별로 신고자 Set을 관리하는 Map 생성
        Map<String, Set<String>> reportMap = new HashMap<>();
        for (String r : report) {
            String[] parts = r.split(" ");
            String reporter = parts[0];
            String reported = parts[1];
            
            // 해당 신고 당한 사용자의 신고자 Set이 없다면 생성 후 추가
            reportMap.putIfAbsent(reported, new HashSet<>());
            reportMap.get(reported).add(reporter);
        }
        
        // 3. 각 신고 당한 사용자에 대해 신고 횟수가 k 이상인 경우, 신고자들에게 메일 카운트를 증가
        for (Map.Entry<String, Set<String>> entry : reportMap.entrySet()) {
            if (entry.getValue().size() >= k) {
                for (String reporter : entry.getValue()) {
                    int idx = idIndexMap.get(reporter);
                    answer[idx]++;
                }
            }
        }
        
        return answer;
    }
}

개선한 코드의 효율적인 점

제시한 개선 코드는 HashMap과 HashSet을 활용하여 위의 문제점을 해결합니다.

사용자 인덱스 조회 개선
- 방법: HashMap<String, Integer>를 사용하여 각 사용자 ID를 인덱스에 매핑함.
- 효과: O(1) 시간에 인덱스 조회가 가능하여, 매번 전체 리스트를 순회할 필요가 없음.
중복 신고 처리 개선
- 방법: Map<String, Set<String>>를 사용하여,
  - Key: 신고 당한 사용자 ID
  - Value: 해당 사용자를 신고한 유니크한 신고자 집합
- 효과: 중복 신고가 자동으로 제거되며, 각 신고에 대해 효율적으로 데이터 관리가 가능함.
반복문 사용 최소화
- 방법: 신고 내역을 단일 순회하며 처리하고, 필요한 경우에만 신고자 목록을 순회함.
- 효과: 불필요한 중첩 반복문을 제거하여 전체 연산 횟수를 줄임.
split() 호출 최소화
- 방법: 신고 데이터를 처음 순회할 때 한 번만 split(" ") 호출하여 필요한 데이터를 추출하고, 이후에는 매핑된 데이터 구조를 사용함.
- 효과: 문자열 분리 연산이 반복되지 않아 오버헤드가 감소함.
전체 시간 복잡도 개선
- 방법: 각 단계별로 한 번씩 순회하면서 처리함으로써 불필요한 연산을 제거함.
- 효과: 신고 건수와 사용자 수가 많아져도 효율적으로 처리 가능.

항목	현재 코드의 비효율적인 점	제시한 코드의 효율적인 점
사용자 인덱스 조회	- 매번 신고 내역 처리 시 `id_list`를 순회하여 해당 인덱스를 찾음 (O(n) 선형 검색)	- `HashMap<String, Integer>`를 사용해 사용자 ID와 인덱스를 매핑하여 O(1) 시간에 인덱스 조회
중복 신고 처리	- 신고 문자열을 `split(" ")`로 분리할 때마다 반복 호출 - 중복 신고 제거를 위해 `HashSet<String>` 사용하나, 문자열 처리 및 반복문이 중첩되어 있음	- `Map<String, Set<String>>` 구조를 사용하여 각 신고 당한 사용자마다 유니크한 신고자 집합을 관리 - 중복 신고 자동 제거 및 효율적 처리
반복문 사용	- 신고 내역마다 신고 당한 사용자와 신고한 사용자를 찾기 위해 다중 중첩 반복문 사용 - id_list 내에서 매번 순회하여 인덱스 확인	- 신고 내역을 단일 순회하면서 처리하고, 신고자 메일 발송도 별도의 순회로 진행 - HashMap을 활용해 불필요한 전체 순회를 제거
split() 호출	- 각 신고마다 `split(" ")`를 반복 호출하여 문자열을 분리함 - 불필요한 문자열 분리 연산으로 오버헤드 발생	- 신고 데이터를 처음 순회할 때 한 번씩만 `split(" ")` 호출하여 필요한 데이터를 추출 - 이후에는 데이터 구조(Map, Set)로 빠르게 접근
전체 시간 복잡도	- 신고 건수와 사용자 수가 많아질 경우, 중첩 반복문과 반복적인 선형 검색으로 인해 성능 저하 우려 (최악의 경우 O(n*m)의 시간 복잡도 가능)	- 각 단계별로 한 번씩 순회하면서 처리하여 전체 시간 복잡도를 크게 줄임 - 사용자와 신고 내역이 많아져도 효율적으로 처리 가능

[2025-02-13] Java

Map 에는 키가 없을 경우 삽입하는 매서드도 있다.( map.putIfAbsent(키, 값) )

Map 자료구조는 entrySet() 매서드를 통해 Map 안의 키값묶음을 Set 형태의 엔트리묶음으로 얻을 수가 있는데, 그래서 각 하나하나의 객체는 반드시 Map.Entry<키자료형,값자료형> 변수명 으로 받아야함.

키만 Set 형태로 받으려면 .keySet() , 값만 Collection 형태로 받으려면 .values()

이규정

반갑습니다. 백엔드 개발자가 되기 위해 노력중입니다.

이전 포스트

[2025-02-12] SQL, Java 알고리즘 풀이

다음 포스트

[2025-02-13] SQL, Java 알고리즘 문제

1] SQL - 특정 기간동안 대여 가능한 자동차들의 대여비용 구하기

1. 요구사항

2. 문제 접근

(1) 대상 자동차 선정

(2) 할인 정책 적용

(3) 대여 가능 여부 체크

(4) 요금 조건 적용

(5) 정렬 조건

3. 최종 SQL 코드

4. 코드 설명

2] Java 알고리즘 문제 - 신고 결과 받기

1. 요구사항

4. 코드 작성

5. 문제점

코드 효율성 비교 및 개선 방안

기존 코드의 비효율적인 점

개선 코드

개선한 코드의 효율적인 점

[2025-02-12] SQL, Java 알고리즘 풀이

[2025-02-21] Servlet vs Spring

0개의 댓글