DB의 동시성(Concurrency) 제어와 트랜잭션 설계 고민

서비스를 운영하다 보면 "이 기능은 하나의 트랜잭션으로 묶여야 해!" 하는 순간이 온다.

트랜잭션 처리가 필요한 상황과 발생 할 수 있는 이슈에 대해 정리하고,

이런 이슈를 방지할 방안에 대해 고민해보려고 한다.

 

 

이슈1: 동시에 같은 요청이 들어오면? (A.K.A. 따닥)

다수 혹은 한명의 사용자가 동시에 같은 API를 여러번 호출해서 특정 리소스A를 수정이나 삭제하려고 한다면?

-> 예상치 못한 중복 처리, 데이터 불일치가 발생할 수 있음 (전형적인 동시성 문제)

 

728x90

 

해결방안1: 비관적 락 (Pessimistic Lock)

   row-level lock 직접 걸기

@Lock(LockModeType.PESSIMISTIC_WRITE)
Optional<Data> findByIdForUpdate(Long id);

 

  • 장점: 안전하게 처리 가능
  • 단점: 성능 저하, 데드락

 

  해결방안2: 낙관적 락 (Optimistic Lock)

  version 필드를 두고 충돌이 날 것 같지 않다고 가정하고 먼저 처리한 뒤

  최종 커밋 시점에 version 비교하여 충돌 여부 확인

@Entity
public class Product {
    @Id
    private Long id;

    @Version
    private Long version;

    private int stock;
}
  • 장점: 락을 걸지 않아서 성능이 좋음
  • 단점: 충돌 발생 시 예외 처리 및 재시도 로직 필요
            동시 수정이 많을수록 실패율이 높아짐

 

  해결방안3: 분산 락 (Distributed Lock)

  로직 단에서 lock을 걸 때, 다중화 환경 지원을 위해 Redis 기반 락(Redisson) 등을 활용하여 직접 특정 key에 락 걸고 해제

RLock lock = redissonClient.getLock("lock:data1");
try {
    if (lock.tryLock(5, 10, TimeUnit.SECONDS)) {
        updateData();
    }
} finally {
    lock.unlock();
}
  • 장점: 여러 서버에서 동시에 접근할 때도 안전
            트래픽 높은 분산 환경에서 유용
  • 단점: Redis가 단일 실패 지점(SPOF)이 될 수 있음
            락 유실, 타임아웃 등 관리 필요

 

  해결방안4: 요청 자체의 중복 방지 (Idempotent 처리)

  각 요청에 유일한 ID (X-Request-Id) 부여 및 체크하여 중복 방지

@PostMapping("/api/process")
public ResponseEntity<?> process(@RequestHeader("X-Request-Id") String requestId) {
    if (requestService.isAlreadyProcessed(requestId)) {
        return ResponseEntity.status(409).body("이미 처리된 요청입니다");
    }

	requestService.process();
}

 

  • 장점: 중복 호출에 DB Lock 없이 안전하게 동작
  • 단점: 중복 체크용 저장소 필요 (DB, Redis 등)
             DB와는 관계 없이 요청에 대한 중복만 체크 가능

 


이슈2: 트랜잭션 안에 오래 걸리는 작업이 있을때

예를 들어, 아래와 같은 기능의 메서드를 호출하는 API 를 만든다.

@Transactional
public void process() {
    deleteData();	// 1. 데이터 삭제
    someLongTask();	// 2. 오래 걸리는 작업 (ex. 외부 API, 복잡한 연산 등)
    insertData();	// 3. 새로운 데이터 추가
}

이런 트랜잭션이 걸린 메서드가 있을 때, 일반적으로 잘 동작하지만

트래픽이 많아지거나 동시에 여러 요청이 들어오면 아래와 같은 문제가 발생한다.

  • DB 리소스를 오래 점유 → Lock이 유지됨
  • 다른 요청들이 해당 리소스에 접근 시 지연(Lock 대기) 또는 타임아웃 발생
  • 결국 전체 시스템의 응답 속도와 안정성에 영향을 줌

 

  해결방안1: 트랜잭션 분리 전략

  트랜잭션을 분리하여 오래 걸리는 작업은 비동기 처리(Kafka 등)

@Transactional
public void deleteData() { // 삭제는 즉시 처리
    repository.deleteById(id);
}

public void enqueueProcessingJob() { // 오래걸리는 작업은 비동기 메시지 큐로 처리
    kafkaProducer.send("data2-create", payload);
}
  • 장점: 트랜잭션 짧아져서 안정성이 높고 속도와 처리량 개선 가능
  • 단점: 분산 시스템 복잡도 증가. 재시도, 보상 로직 추가 필요

 

728x90
반응형

'Java' 카테고리의 다른 글

[Java] @FunctionalInterface 함수형 인터페이스  (0) 2025.04.10

1. 함수형 인터페이스 란?

단 하나의 추상 메서드만 가지는 인터페이스 (Java 8부터 함수형 프로그래밍을 지원하기 위해 도입)

 

 

2. 특징

  • 추상메서드가 하나 뿐인 인터페이스 (default 메서드나 static 메서드는 허용 됨.)
  • 람다 표현식으로 구현 가능
  • @FunctionalInterface 어노테이션을 사용하여 명시적으로 확인 가능
  • java.util.function 패키지에서 기본 함수형 인터페이스 제공
Consumer<T> 입력값을 받아서 처리하지만, 반환값은 없음

Consumer<String> print = (s) -> System.out.println(s);
Function<T, R> 입력값을 받아서 반환값을 생성

Function<String, Integer> length = (s) -> s.length();
Predicate<T> 조건을 검사하고 boolean 값을 반환

Predicate<String> isNotEmpty = (s) -> !s.isEmpty();
Supplier<T> 단순 값을 제공

Supplier<String> getString = () -> "Hello";

 

 

728x90

3. 사용 예시 

 함수형 인터페이스 생성

  • @FunctionalInterface : 함수형 인터페이스 임을 명시적으로 표현 (생략 가능)
  • run(String msg) : 유일한 추상 메서드
  • print1(String msg) : default 메서드 이므로 함수형 인터페이스로 선언하는 데에 지장 없음.
  • print2(String msg) : static 메서드 이므로 함수형 인터페이스로 선언하는 데에 지장 없음.
@FunctionalInterface
public interface MyFunction {
    void run(String msg);

    default void print1(String msg) {
        System.out.println(msg);
    }

    static void print2(String msg) {
        System.out.println(msg);
    }
}

 

 

 

함수형 인터페이스 구현

  • 출력: Functional Interface Test : Run!
public class FunctionalInterfaceExample {
    public static void main(String[] args) {
        MyFunction myFunction = (s) -> System.out.println("Functional Interface Test : " + s);
        myFunction.run("Run!"); 
    }
}

 

 

함수형 인터페이스 구현 + Bean 등록 간소화

@Configuration
public class MyConfig {

    @Bean
    public MyFunction<String, String> print() {
        return (s) -> System.out.println("Functional Interface Test : " + s);
    }
}

 

 

Stream API + java.util.function 패키지 사용

예시 : fruits List 에서 apple 인 항목만 추출하여 대문자로 출력하기

  • Predicate<String> : apple 인 항목인지 검증 (조건 판단)
  • Function<String, String> : 주어진 값을 대문자로 변환 (데이터 변환)
  • Consumer<String> : 주어진 값을 출력 (출력)
  • 출력 : Hello, APPLE
              Hello, APPLE
public class StreamExample {
    public static void main(String[] args) {
        List<String> fruits = Arrays.asList("apple", "banana", "orange", "apple");

        Predicate<String> isApple = (s) -> s.equals("apple");
        Function<String, String> toUpperCase = (s) -> s.toUpperCase();
        Consumer<String> printName = (name) -> System.out.println("Hello, " + name);

        fruits.stream()
            .filter(isApple)
            .map(toUpperCase)
            .forEach(printName);
    }
}

 

 

4. 결론

  • 함수형 인터페이스는 단 하나의 추상 메서드만 가진 인터페이스
  • 주로 람다 표현식과 함께 사용
728x90
반응형

'Java' 카테고리의 다른 글

DB의 동시성(Concurrency) 제어와 트랜잭션  (0) 2025.04.16

요구사항

주어진 주문서는 알파벳 소문자 1글자부터 최대 11글자까지의 모든 문자열이 사전 순으로 정렬되어 있고

일부 삭제된 주문 배열이 주어질 때 삭제된 주문을 제외한 n번째 주문을 구하기

 

 

입력 값

long n 구해야 하는 주문의 순번
String[] bans 삭제된 주문 배열
bans[i] 는 i+1 번째 삭제된 주문을 말한다. (a~z로만 구성)

 

 

풀이

1. 문자를 순번으로 순번을 문자로 변환하는 함수 생성

    -> 문자를 한 글자씩 읽어서 a=1 b=2 .... z=26 으로 변환하는 함수 생성

    -> 숫자를 읽어서 26으로 나눈 나머지문자로 뒷자리부터 변환하는 함수 생성

 

2. 삭제된 주문 배열을 모두 숫자로 변환하기

    -> 구해야 하는 순번과 비교하기 위함

 

3. 구해야 하는 진짜 순번 찾기

    -> 삭제된 주문 배열을 정렬하고 구해야하는 순번의 숫자보다 작은 경우 순번 1씩 증가시킴

 

4. 삭제된 주문을 적용한 새 순번을 다시 문자로 변환하여 return

 

728x90

Java 코드

import java.util.*;

class Solution {
    public String solution(long n, String[] bans) {
        String answer = "";
    
        long num;
        long[] bansNums = new long[bans.length];
        for(int i=0; i<bans.length; i++) {
            bansNums[i] = convertStrToNum(bans[i]);
        }
        
        Arrays.sort(bansNums);
        for(long bn : bansNums) if(bn <= n) n++;
        
        answer = convertNumToStr(n);
        
        return answer;
    }

    private long convertStrToNum(String str) {
        int length = str.length();
        long num = 0;

        for(int j=0;j<length;j++) {
            num += (str.charAt(j)-96) * Math.pow(26,(length-1-j));
        }

        return num;    
    }
    private String convertNumToStr(long num) {
        String str = "";

        while(num > 0) {
            str = String.valueOf((char)((num-1)%26+1+96)) + str;
            num=(num-1)/26;
        }

        return str;
    }
}

 

 

문제 출처

https://school.programmers.co.kr/learn/courses/30/lessons/389481
728x90
반응형

요구사항

1개 이상의 트리가 포함된 포레스트의 정보로 노드 리스트와 간선 리스트가 주어질때

각 노드는 홀수, 짝수, 역홀수, 역짝수  분류되고 어떤 노드를 루트노트로 설정하는지에 따라서 노드의 구분은 바뀔 수도 있다. 

노드의 숫자가 홀수이고 자식 노드 수가 홀수이면 홀수 노드

노드의 숫자가 홀수이고 자식 노드 수가 짝수이면 역홀수 노드

노드의 숫자가 짝수이고 자식 노드 수가 짝수이면 짝수 노드

노드의 숫자가 짝수이고 자식 노드 수가 홀수이면 역짝수 노드

이를 기준으로 트리의 성격을 판단한다.

홀수 노드와 짝수 노드로만 이루어진 트리는 홀짝트리가 되고 역홀수, 역짝수로만 이루어진 경우 역홀짝트리 라고 할때

주어진 포레스트에서 가능한 홀짝 트리와 역홀짝 트리의 갯수 구하기

 

 

입력 값

int[] nodes 노드 번호가 담긴 배열
nodes[i] 는 i+1 번째 노드의 번호이다. (순서는 무작위)
int[][] edges 노드와 노드간의 간선 정보가 담긴 배열
edges[i] 는 노드 번호가 2개 담겨있다
edges[i][0] 과 edges[i][1] 은 서로 연결되어 있다는 표시 

 

 

풀이

1. 각 노드의 자식노드 정보를 저장하기 위한 Map을 만들고 빈 list로 초기화

 

2. 간선 정보를 활용하여 각 노드의 자식 노드를 저장

 

3. 각 노드를 루트노드로 가정하고 루트노드의 성격에 따라서 각 노드 리스트에 저장

    -> 노드의 홀짝과 자식노드 숫자의 홀짝이 동일한 경우 yellowTree 리스트에 저장

    -> 노드의 홀짝과 자식노드 숫자의 홀짝이 다른 경우 redTree 리스트에 저장

 

4. 자식 노드 탐색 하기 (DFS)

    -> 자식 노드의 성격과 루트노드의 성격이 다른 경우 해당 Tree 리스트에서 삭제 처리

    -> 자식 노드의 자식 탐색 시 부모노드 정보도 들어있기 때문에 부모노드 탐색은 제외 처리

    -> 이미 Tree 리스트에서 제거된 루트 노드인 경우 자식 노드 탐색 중단

 

5. 모든 노드의 자식 루트를 탐색할 때 까지 3~4 반복

 

6. yellowTree 리스트 길이와 redTree 리스트 길이 return

 

728x90

Java 코드

import java.util.*;

class Solution {
    static List<Integer> yellowTree = new ArrayList<>();
    static List<Integer> redTree = new ArrayList<>();
    
    public int[] solution(int[] nodes, int[][] edges) {
        int[] answer = {};
        
        Map<Integer, List<Integer>> childsInfo = new HashMap<>();
        boolean isYellow;
        
        for(int node : nodes) {
            childsInfo.put(node, new ArrayList<>());
        }
        
        for(int[] edge : edges) {
            childsInfo.get(edge[0]).add(edge[1]);
            childsInfo.get(edge[1]).add(edge[0]);
        }
        
        for(int node : nodes) {
            isYellow = node%2 == childsInfo.get(node).size()%2;
            if(isYellow) yellowTree.add(node);
            else if(childsInfo.get(node).size() > 0) redTree.add(node);
            
            findChilds(node, node, node, childsInfo, isYellow);
        }
        
        answer = new int[]{yellowTree.size(), redTree.size()};
        
        return answer;
    }
    
    private void findChilds(int rootNode, int parentNode, int node, Map<Integer, List<Integer>> childsInfo, boolean isRootYellow) {
        List<Integer> childs;
        
        for(int childNode : childsInfo.get(node)) {
            if(childNode == parentNode) continue;
            if(yellowTree.indexOf(rootNode) == -1 && redTree.indexOf(rootNode) == -1) break;
            
            childs = childsInfo.get(childNode);
            
            if(isRootYellow != (childNode%2 == (childs.size()-1)%2)) { 
                if(isRootYellow) yellowTree.remove(yellowTree.indexOf(rootNode));
                else redTree.remove(redTree.indexOf(rootNode));
                return;
            } 
            
            findChilds(rootNode, node, childNode, childsInfo, childNode%2 == (childs.size()-1)%2);
        }
    }
}

 

 

문제 출처

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

728x90
반응형

요구사항

주어진 수식들 중 일부 결괏값이 'X'표시로 지워져 있으며, 수식은 2~9진법 중 하나의 진법을 사용할 때

지워진 수식을 완성하여 출력하기

(가능한 결괏값이 여러개인 경우 ?로 표시)

 

 

입력 값

String[] expressions 수식 문자열 배열
expresiion[i]는 A + B = C 혹은 A - B = C 형태의 문자열
A, B는 음이 아닌 2자리 이하의 정수
C는 음이 아닌 세자릿수 이하의 정수

 

 

풀이

1. 수식의 확인하고 저장할 변수 생성

List<Integer> numbers = new ArrayList<>(Arrays.asList(2,3,4,5,6,7,8,9)); 사용 가능한 진법 숫자를 담은 List
초기 값은 2~9 까지의 정수
List<String> unsolves = new ArrayList<>(); 지워진 수식을 담을 List
String fNum, sNum, rNum; 수식에서 추출할 정수 3개를 담을 문자열
int oper; 수식에서 추출할 수식을 담을 숫자

 

2. 수식 전체를 탐색

    -> 공란으로 수식을 잘라서 0번째는 첫번째 숫자(fNum), 2번째는 두번째 숫자(sNum), 4번째는 세번째 숫자(rNum) 저장

    -> 1번째는 연산부호로 + 인 경우 +1을 -인 경우 -1을 oper 에 저장

    -> 4번째 숫자가 "X" 인 경우 지워진 수식 List(unsolves) 에 추가

 

3. 사용 가능한 진법 별로 수식 연산 하여 불가능한 수식은 진법 리스트(numbers) 에서 제외 처리

    -> 주어진 진법으로 변환하지 못하는 숫자가 포함된 경우 제외 (= 진법과 같거나 큰 숫자라 표현할수 없는 숫자)
    -> 정상 수식일때 주어진 정답과 다르면 제외

 

4. 가능한 진법 숫자 리스트를 통해 지워진 수식 List 별로 정답 재 작성하기

    -> 숫자 별 정답 생성하여 하나라도 다른 정답이 있는 경우 X?로 변환

    -> 모두 같은 정답인 경우 X를 정답으로 변경  

 

5. 재 작성 된 수식 return

 

 

728x90

 

Java 코드

import java.util.*;

class Solution {
    public String[] solution(String[] expressions) {
        String[] answer = {};
        
        List<Integer> numbers = new ArrayList<>(Arrays.asList(2,3,4,5,6,7,8,9));
        List<String> unsolves = new ArrayList<>();
        String fNum, sNum, rNum;
        int oper;
        
        for(String expression : expressions) {
            fNum = expression.split(" ")[0];
            sNum = expression.split(" ")[2];
            rNum = expression.split(" ")[4];
            oper = "+".equals(expression.split(" ")[1]) ? 1 : -1;
            
            if("X".equals(rNum)) unsolves.add(expression);

            for(int i=2; i<=9; i++) {
                if(numbers.indexOf(i) == -1) continue;
                
                try {
                    if("X".equals(rNum)) {
                        // 변환 가능한지 여부만 체크
                        Integer.parseInt(fNum, i);
                        Integer.parseInt(sNum, i);
                    } else if(Integer.parseInt(fNum, i) + Integer.parseInt(sNum, i) * oper
                       != Integer.parseInt(rNum, i)) throw new NumberFormatException();
                } catch (NumberFormatException e) {
                    numbers.remove(numbers.indexOf(i));
                }
            }
        }
        
        answer = new String[unsolves.size()];
        String result, nowVal;
        
        for(int i=0; i<unsolves.size(); i++) {
            result  = "";
            fNum    = unsolves.get(i).split(" ")[0];
            oper    = "+".equals(unsolves.get(i).split(" ")[1]) ? 1:-1;
            sNum    = unsolves.get(i).split(" ")[2];
            
            for(int n : numbers) {
                nowVal = Integer.toString(Integer.parseInt(fNum, n) + Integer.parseInt(sNum, n)*oper, n);
                
                if(!"".equals(result) && !nowVal.equals(result)) {
                    result = "?";
                    break;
                }
                
                result = nowVal;
            }
            
            answer[i] = unsolves.get(i).replace("X", result);
        }
        
        return answer;
    }
}

 

 

문제 출처

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

728x90
반응형

요구사항

주어진 퍼즐판에서 빨간색과 파란색 수레가 각각의 주어진 도착 칸으로 이동해야 할때

1. 각 수레는 벽이나 격자 밖으로 나갈 수 없다.

2. 동시에 두 수레가 같은 칸에 있을 수 없다.

3. 수레는 상하좌우로만 움직일 수 있다.

4. 도착지에 도착하기 전까지 각 턴마다 수레를 무조건 움직여야 한다.

5. 두 수레가 서로 위치를 바꿀수 없다.

위와 같은 조건으로 가는 경로의 경우의 수 중에 최소값 구하기.

 

 

입력 값

int[][] maze 퍼즐판의 정보를 나타내는 배열
maze[i][j] 는 각 퍼즐판 칸을 의미하며 0~5로 이루어져 있다.
0: 빈칸
1: 빨간 수레의 시작 칸
2: 파란 수레의 시작 칸
3: 빨간 수레의 도착 칸
4: 파란 수레의 도착 칸
5: 벽 (벽으로는 이동할 수 없음)

 

 

풀이

1. 각 수레의 출발 칸과 도착 칸의 좌표 구하기

    -> 출발 칸 방문 여부 수레 별 각각 저장

 

2. 상하좌우 이동 가능한 모든 경우의 수 구하기 (Backtracking)

    -> 상하좌우 칸 중 퍼즐 판 내에서 벽인 경우 Pass

    -> 상하좌우 칸 중 각 수레가 방문한 적 있는 경우 Pass

    -> 상하좌우 칸 중 두 수레가 동일한 칸으로 이동하는 경우 Pass

    -> 상하좌우 칸 중 수레간 상호 교환하는 이동인 경우 Pass

    -> 이동 경로 저장 후 이동횟수 + 1 처리 하여 다음 이동 경로 추가 탐색 반복 (재귀)

 

3. 빨간 수레와 파란 수레가 각각 도착 좌표에 도착하면 총 이동 횟수 Min 비교

    -> 퍼즐은 최대 4*4 크기이므로 최초 minCount 는 16으로 시작 (16회 이상 움직일 수 없음)

 

4. 최소 이동 횟수 return

    -> minCount가 16 인 경우 한번도 도착하지 못했으므로 0 return

 

728x90

 

Java 코드

import java.util.*;

class Solution {
    // 수레 별 이동 경로
    static boolean[][] rMove, bMove;
    static int minCount = 16;
    
    public int solution(int[][] maze) {
        int answer = 0;
        
        rMove = new boolean[maze.length][maze[0].length];
        bMove = new boolean[maze.length][maze[0].length];
        
        // 수레 별 현재/끝 좌표
        int[] red       = new int[2];
        int[] redGoal   = new int[2];
        int[] blue      = new int[2];
        int[] blueGoal  = new int[2];
        
        // 시작 칸과 끝 칸 먼저 구하기
        for(int i=0; i<maze.length;i++) {
            for(int j=0; j<maze[0].length;j++) {
                if(maze[i][j] == 1) { red       = new int[]{i, j}; rMove[i][j] = true;}
                if(maze[i][j] == 2) { blue      = new int[]{i, j}; bMove[i][j] = true;}
                if(maze[i][j] == 3) { redGoal   = new int[]{i, j}; }
                if(maze[i][j] == 4) { blueGoal  = new int[]{i, j}; }
            }
        }
        
        move(red, blue, redGoal, blueGoal, maze, 0);
        answer = minCount == 16 ? 0 : minCount;
         
        return answer;
    }
    
    private void move(int[] red, int[] blue, int[] redGoal, int[] blueGoal, int[][] maze, int moveCnt) {
        int redX    = red[1];
        int redY    = red[0];
        int blueX   = blue[1];
        int blueY   = blue[0];
        
        if(redX == redGoal[1] && redY == redGoal[0] && blueX == blueGoal[1] && blueY == blueGoal[0]) {
            minCount = Math.min(minCount, moveCnt);
            return;
        }
        
        // 상하좌우 탐색용
        int[] rx    = {0, 0, -1, 1};
        int[] ry    = {-1, 1, 0, 0};
        int maxX    = maze[0].length;
        int maxY    = maze.length;
        
        List<int[]> redDirections   = new ArrayList<>();
        List<int[]> blueDirections  = new ArrayList<>();

        if(redX == redGoal[1] && redY == redGoal[0]) redDirections.add(red);
        else {
            for(int i=0; i<4; i++) {
                if(redX + rx[i] < 0 || redX + rx[i] >= maxX || redY + ry[i] < 0 || redY + ry[i] >= maxY
                  || rMove[redY + ry[i]][redX + rx[i]]
                  || maze[redY + ry[i]][redX + rx[i]] == 5
                  ) continue;

                redDirections.add(new int[]{redY + ry[i], redX + rx[i]});
            }
        }

        if(blueX == blueGoal[1] && blueY == blueGoal[0]) blueDirections.add(blue);
        else {
            for(int i=0; i<4; i++) {
                if(blueX + rx[i] < 0 || blueX + rx[i] >= maxX || blueY + ry[i] < 0 || blueY + ry[i] >= maxY
                  || bMove[blueY + ry[i]][blueX + rx[i]]
                  || maze[blueY + ry[i]][blueX + rx[i]] == 5
                  ) continue;

                blueDirections.add(new int[]{blueY + ry[i], blueX + rx[i]});
            }
        }

        for(int[] rDirection : redDirections) {
            for(int[] bDirection : blueDirections) {
                // 동일한 장소로 이동하는 경우 Pass
                if(rDirection[0] == bDirection[0] && rDirection[1] == bDirection[1]) continue;
                // 서로 자리 바꾸는 경우 Pass
                if(rDirection[0] == blueY && rDirection[1] == blueX
                  && bDirection[0] == redY && bDirection[1] == redX) continue;

                rMove[rDirection[0]][rDirection[1]] = true;
                bMove[bDirection[0]][bDirection[1]] = true;

                move(rDirection, bDirection, redGoal, blueGoal, maze, moveCnt+1);
                
                rMove[rDirection[0]][rDirection[1]] = false;
                bMove[bDirection[0]][bDirection[1]] = false;
            }
        }
    }
    
}

 

 

문제 출처

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

728x90
반응형

요구사항

A도둑과 B도둑이 정해진 물건을 훔칠 때 남기는 흔적이 주어지고 각각 정해진 최대 누적 흔적을 초과하는 경우 경찰에 붙잡힌다.

두 도둑이 경찰에 붙잡히지 않도록 물건을 훔칠 때 A도둑이 남길수 있는 최소한의 흔적 구하기.

(붙잡히지 않고 훔치기가 불가능한 경우에는 -1을 반환)

 

 

입력 값

int[][] info 도둑이 훔쳐야 하는 물건의 상세 정보
info[i][0]은 i+1 번째 물건을 A도둑이 훔칠 때 남는 흔적
info[i][1]은 i+1 번째 물건을 B도둑이 훔칠 때 남는 흔적
int n A도둑이 경찰에 붙잡히는 최소 흔적 개수
int m B도둑이 경찰에 붙잡히는 최소 흔적 개수

 

 

풀이

1. 누적 흔적을 저장할 배열 dp와 최대 누적 값으로 사용 할 수 있는 maxVal 생성

    -> dp는 초기값(=물건 훔치기 전) [0][0] 세팅을 위해 info 배열보다 1씩 크게 생성

    -> maxVal 은 추후 흔적 수 비교에 사용될 예정으로, 문제의 최대 흔적수와 동일하게 생성

 

2. 각 아이템 별로 흔적 경우의 수 저장

    -> 이 물건을 훔칠 수 있는 도둑의 경우 다음 누적 탐색 저장

        (도둑별 현재 물건의 흔적 수 + 도둑별 누적 흔적 < 경찰에 붙잡히는 흔적수)

    -> 불필요한 재탐색 방지를 위해 탐색한 dp는 false 처리

 

3. 2번 반복 중 마지막 물건인 경우 해당 시점의 A 도둑의 흔적 수로 비교하여 Minimum 값 구하기

 

4. 구한 minimum 값 return

    -> minimum 값이 초기 설정한 최대값과 동일 한 경우 모든 물건 훔치기 실패한 것이므로 -1 return

 

728x90

 

Java 코드

class Solution {
    public int solution(int[][] info, int n, int m) {
        int answer = 0;
        
        boolean[][] dp = new boolean[n+1][m+1];
        int maxVal = 120;
        int result = maxVal;
        
        // 초기 값 설정
        dp[0][0] = true;

        for (int i=0; i<info.length; i++) {
            int aTrace = info[i][0];
            int bTrace = info[i][1];
            
            for (int a=n; a>=0; a--) {
                for (int b=m; b>=0; b--) {
                    if(!dp[a][b]) continue;

                    // A가 이 물건을 훔칠 경우 저장
                    if (a + aTrace < n) {
                        dp[a + aTrace][b] = true;
                        if((i+1) == info.length) result = Math.min(a + aTrace, result);
                    }
                    // B가 이 물건을 훔칠 경우 저장
                    if (b + bTrace < m) {
                        dp[a][b + bTrace] = true;
                        if((i+1) == info.length) result = Math.min(a, result);
                    }
                    
                    dp[a][b] = false;
                }
            }
        }

        return result == maxVal ? -1 : result;
    }
}

 

 

문제 출처

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

728x90
반응형

요구사항

서버 1대당 수용할 수 있는 사용자와 매 시간 사용자의 수, 서버 증설 유지 시간이 주어질 때
매 시간 게임을 이용하는 사용자에 따라서 서버를 증설해야 한다면 하루 동안 최소 몇 번 서버를 증설해야 하는지 구하기

 

 

입력 값

int[] players 하루동안 시간대 별 게임 사용자 수
int[i] 는 i ~ i+1 시각에 사용하는 사용자 수
int m 서버 1대 당 수용할 수 있는 사용자 수
int k 증설한 서버의 유지 시간

 

 

풀이

1. 시간대 별 증설 서버 수 저장을 위한 배열 생성

 

2. 시간대 별 사용자와 서버 최대 수용 인원 비교

   -> 사용자 수(players[i]) / 수용인원(m) 이 증설 서버 수(servers[i]) 보다 적은 경우 Pass

 

3. 서버 증설이 필요한 경우 증설 된 서버 유지시간 만큼 증설 서버 배열에 추가 저장

    -> 사용자 수(players[i]) / 수용인원(m) - 증설 서버 수(servers[i]) 만큼 추가 저장

    -> 증설 서버 수 합산

 

4. 증설 서버 수 return

 

728x90

 

Java 코드

class Solution {
    public int solution(int[] players, int m, int k) {
        int answer = 0;
        
        int[] servers = new int[players.length];
        
        for(int i=0; i<players.length; i++) {
            if(players[i] / m <= servers[i]) continue;
            
            for(int j=1; j<k && (i+j)<servers.length; j++) {
                servers[i+j] += players[i] / m - servers[i];
            }
            
            answer += players[i] / m - servers[i];
        }
        
        return answer;
    }
}

 

 

문제 출처

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

728x90
반응형

+ Recent posts