Computer Science Knowledge Storage

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

해당 문제는 결합법칙을 무시한 채 최대 값을 구하기 위한 문제입니다. - 연산에서는 왼쪽 값은 최댓값, 오른쪽 값은 최솟값이 되어야 최대값이 되고, + 연산에서는 두 값 모두 최대 값이 되어야 합니다. 이를 통해 dpMax 배열과 dpMin 배열을 통해 문제를 풀었습니다.

소스코드

class Solution {
        public int solution(String[] arr) {
            int n = arr.length / 2 + 1; // 숫자의 개수
            int[][] dpMax = new int[n][n];
            int[][] dpMin = new int[n][n];

            // 숫자 초기화
            for (int i = 0; i < n; i++) {
                dpMax[i][i] = Integer.parseInt(arr[i * 2]);
                dpMin[i][i] = Integer.parseInt(arr[i * 2]);
            }

            // 구간 길이
            for (int len = 1; len < n; len++) {
                for (int i = 0; i < n - len; i++) {
                    int j = i + len;
                    dpMax[i][j] = Integer.MIN_VALUE;
                    dpMin[i][j] = Integer.MAX_VALUE;

                    // i부터 j까지 연산자에 대한 분할 계산
                    for (int k = i; k < j; k++) {
                        String operator = arr[k * 2 + 1];
                        int maxLeft = dpMax[i][k];
                        int minLeft = dpMin[i][k];
                        int maxRight = dpMax[k + 1][j];
                        int minRight = dpMin[k + 1][j];

                        if (operator.equals("+")) {
                            dpMax[i][j] = Math.max(dpMax[i][j], maxLeft + maxRight);
                            dpMin[i][j] = Math.min(dpMin[i][j], minLeft + minRight);
                        } else if (operator.equals("-")) {
                            dpMax[i][j] = Math.max(dpMax[i][j], maxLeft - minRight);
                            dpMin[i][j] = Math.min(dpMin[i][j], minLeft - maxRight);
                        }
                    }
                }
            }

            return dpMax[0][n - 1]; // 전체 구간의 최댓값 반환
        }
    }

코드 설명

• int n = arr.length / 2 + 1; // 숫자의 개수 int[][] dpMax = new int[n][n]; int[][] dpMin = new int[n][n];
  • n: 숫자의 개수. 연산자는 숫자보다 항상 하나 적으므로, 전체 배열 길이의 절반(arr.length / 2)에 1을 더해 계산합니다.
  • dpMax[i][j]: i번째 숫자부터 j번째 숫자까지 가능한 최대값을 저장합니다.
  • dpMin[i][j]: i번째 숫자부터 j번째 숫자까지 가능한 최소값을 저장합니다.
• for (int i = 0; i < n; i++) { dpMax[i][i] = Integer.parseInt(arr[i * 2]); dpMin[i][i] = Integer.parseInt(arr[i * 2]); }
  
  • 각 숫자는 연산 없이 자기 자신이므로, dpMax[i][i]와 dpMin[i][i]를 해당 숫자로 초기화합니다.

for (int len = 1; len < n; len++) {
    for (int i = 0; i < n - len; i++) {
        int j = i + len;
        dpMax[i][j] = Integer.MIN_VALUE;
        dpMin[i][j] = Integer.MAX_VALUE;

• len: 현재 계산하려는 구간의 길이. 길이가 1부터 시작하여, 점차 늘어나며 모든 가능한 구간을 탐색합니다.
• i: 구간의 시작점.
• j: 구간의 끝점. 구간 길이가 len이므로, j = i + len으로 계산.

for (int k = i; k < j; k++) {
    String operator = arr[k * 2 + 1];
    int maxLeft = dpMax[i][k];
    int minLeft = dpMin[i][k];
    int maxRight = dpMax[k + 1][j];
    int minRight = dpMin[k + 1][j];

• k: 구간을 분할하는 기준점.
  • arr[k * 2 + 1]에서 연산자(+, -)를 가져옵니다.
  • k를 기준으로 왼쪽(i에서 k)과 오른쪽(k+1에서 j)의 최대/최소값을 가져옵니다.
    • maxLeft, minLeft: 왼쪽 구간 최대/최소값.
    • maxRight, minRight: 오른쪽 구간 최대/최소값.

if (operator.equals("+")) {
    dpMax[i][j] = Math.max(dpMax[i][j], maxLeft + maxRight);
    dpMin[i][j] = Math.min(dpMin[i][j], minLeft + minRight);
} else if (operator.equals("-")) {
    dpMax[i][j] = Math.max(dpMax[i][j], maxLeft - minRight);
    dpMin[i][j] = Math.min(dpMin[i][j], minLeft - maxRight);
}

• 연산자에 따라 결과를 계산
  • + 연산: 양쪽 구간의 최대/최소값을 더합니다.
  • - 연산: 왼쪽 최대값에서 오른쪽 최소값을 빼거나, 왼쪽 최소값에서 오른쪽 최대값을 뺍니다.
• 계산 결과를 갱신하며, dpMax[i][j]는 가능한 최대값, dpMin[i][j]는 가능한 최소값을 유지합니다.
• return dpMax[0][n - 1];
  • dpMax[0][n-1]: 입력 배열 전체(0번째 숫자부터 마지막 숫자까지)의 가능한 최대값을 반환합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

이 주어진 숫자 N을 여러 번 사용하여 특정 숫자 number를 만들기 위해 필요한 최소 사용 횟수를 찾는 문제를 해결합니다.
이것은 동적 계획법(Dynamic Programming, DP)을 활용하여 숫자 N을 점진적으로 조합해 나가는 방식입니다.

소스코드

import java.util.*;

class Solution {
    public int solution(int N, int number) {
        // N을 i번 사용해서 나온 수 => dp[i] 에 저장
        List<Set<Integer>> dp = new ArrayList<>();
        
        for(int i = 0; i <= 8; i++) {
            dp.add(new HashSet<>());
        }
        
        for(int i = 1; i <= 8; i++) {
            // 5, 55, 555 ....
            int repeatN = Integer.parseInt(String.valueOf(N).repeat(i));
            dp.get(i).add(repeatN);
            
            // 사칙연산으로 찾기
            for (int j = 1; j < i; j++) {
                for (int a: dp.get(j)) {
                    for (int b : dp.get(i - j)) {
                        // +
                        dp.get(i).add(a + b);
                        // -
                        dp.get(i).add(a - b);
                        dp.get(i).add(b - a);
                        // *
                        dp.get(i).add(a * b);
                        // /
                        if (b != 0) dp.get(i).add(a / b);
                        if (a != 0) dp.get(i).add(b / a);
                    }
                }
            }
            
            if (dp.get(i).contains(number)) {
                return i;
            }
        }
        
        return -1;
    }
}

코드 설명

• 입력값 및 변수 초기화
  • dp[i]: 숫자 N을 정확히 i번 사용해서 만들 수 있는 모든 숫자의 집합입니다.
  • 문제에 나왔던대로 답은 8보다 클 수 없기에 dp는 최대 8번까지 숫자를 사용한 결과를 저장할 수 있도록 초기화합니다.
• int repeatN = Integer.parseInt(String.valueOf(N).repeat(i)); dp.get(i).add(repeatN);
  String.valueOf(N).repeat(i)를 통해 N을 i번 반복합니다.
  
  • String.valueOf(N).repeat(i): 숫자 N을 i번 반복한 문자열을 생성합니다.
  • 숫자 repeatN을 dp[i]에 추가합니다.
• 사칙연산으로 숫자 조합
  
  • j와 i - j로 숫자 N을 각각 j번, i-j번 사용해서 만든 숫자들을 조합하여 dp[i]를 채웁니다.
  • 각 숫자 쌍 (a, b)에 대해 사칙연산을 수행하고 결과를 dp[i]에 추가:
    • 덧셈: a + b
    • 뺄셈: a - b, b - a
    • 곱셈: a * b
    • 나눗셈: a / b, b / a (0으로 나누는 경우를 제외).
• if (dp.get(i).contains(number)) { return i; }
  
  • targetNumber가 있으면 현재 i를 반환합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁

스프링 정리를 위한 포스팅입니다.
해당 포스팅은 @Controller, @Service, @Repository의 역할과 특징 정리입니다.

도입

Spring 프레임워크는 계층구조로 코드를 나누어 각 계층마다 역할을 분리하였습니다.(객체 지향적 특징)
이와 같은 계층 구조는 코드의 역할 분리를 명확히 하고 유지보수성을 높이는 데 중요한 역할을 합니다.

• Presentation Layer: 클라이언트의 요청 처리
• Business Layer: 비즈니스 로직 처리
• Persistence Layer: 데이터 접근 처리

클라이언트와의 요청 처리는 @Controller, 비즈니스 로직 처리는 @Service, 데이터베이스와의 통신은 @Repository를 통해 코드를 구성합니다. 

이번 포스팅에서는 @Controller, @Service, @Repository의 역할과 특징을 살펴보겠습니다.

@Controller

@Controller는 Spring MVC에서 컨트롤러 클래스를 정의할 때 사용되는 어노테이션입니다. 일반적으로 뷰 템플릿을 반환하는 방식으로 클라이언트의 요청을 처리합니다. 이 어노테이션이 있는 클래스는 HTTP 요청을 처리하고, Model 객체를 사용하여 데이터를 뷰에 전달합니다. @Controller는 주로 웹 애플리케이션에서 서버 사이드 렌더링을 위한 컨트롤러로 사용됩니다.

1. 클라이언트로부터 받은 요청을 통해 Handler 어댑터를 통해 해당 요청을 처리할 수 있는 controller를 찾습니다.
2. controller는 service와 repository의 비즈니스 로직을 처리한 후 뷰 이름을 handlerAdapter에게 전달합니다.
3. Dispatcher Servlet은 해당 뷰 네임에 해당하는 뷰를 ViewResolver를 통해서 뷰를 반환합니다.

@Controller
@RequiredArgsConstructor
public class UserController {
    private final UserService userService;

    @GetMapping("/users")
    public String getUsers(Model model) {
        model.addAttribute("users", userService.findAll());
        return "userList"; // "userList" 뷰 반환
    }
}

@Controller + @RequestBody

@RequestBody는 HTTP 요청 본문을 자바 객체로 변환하여 매핑해주는 어노테이션입니다. 이 어노테이션을 @Controller와 함께 사용하면, 클라이언트에서 전달한 JSON, XML 등의 데이터를 객체로 받을 수 있습니다. @Controller는 뷰를 반환하는 역할을 계속하고, @RequestBody는 데이터를 뷰에 매핑하는 역할을 합니다.

1. 클라이언트로부터 받은 요청을 통해 Handler 어댑터를 통해 해당 요청을 처리할 수 있는 controller를 찾습니다.
2. controller는 service와 repository의 비즈니스 로직을 처리한 후 뷰 이름을 handlerAdapter에게 전달합니다.
3. 반환되는 객체는 Json으로 Serialize되어 사용자에게 반환됩니다. 이는 @ResponseBody 어노테이션으로 개발됩니다.

@Controller
@RequiredArgsConstructor
public class UserController {
    private final UserService userService;

    /**
     * Handles POST requests to create a new user from JSON data and renders the "userDetail" view.
     *
     * @param user the user data from the request body
     * @param model the model to hold attributes for the view
     * @return the name of the view to be rendered
     */
    @PostMapping("/users")
    public String createUser(@RequestBody User user, Model model) {
        User savedUser = userService.save(user);
        model.addAttribute("user", savedUser);
        return "userDetail"; // Return the name of the view
    }
}

@RestController

@RestController는 @Controller와 @ResponseBody를 결합한 어노테이션입니다. @RestController가 적용된 클래스는 RESTful 웹 서비스를 제공하며, 메서드의 반환 값이 바로 HTTP 응답 본문으로 전송됩니다. 따라서 @RestController는 일반적으로 JSON, XML과 같은 데이터를 직접 반환하는 데 사용됩니다. 뷰를 반환하지 않으며, 주로 API 서버에서 사용됩니다.

1. 클라이언트로부터 받은 요청을 통해 Handler 어댑터를 통해 해당 요청을 처리할 수 있는 controller를 찾습니다.
2. controller는 service와 repository의 비즈니스 로직을 처리한 후 뷰 이름을 handlerAdapter에게 전달합니다.
3. 반환되는 객체는 Json으로 Serialize되어 사용자에게 반환됩니다. 이는 @RestController 어노테이션으로 개발됩니다.

@RestController
@RequiredArgsConstructor
public class UserController {
    private final UserService userService;

    /**
     * Handles GET requests to retrieve the list of users as JSON.
     *
     * @return a list of users
     */
    @GetMapping("/json-users")
    public List<User> getUsers() {
        return userService.findAll();
    }
}

@Service

@Service 어노테이션은 서비스 계층에 사용됩니다. 서비스 계층은 비즈니스 로직을 처리하는 곳으로, 일반적으로 데이터베이스에서 데이터를 조회하고, 가공하여 컨트롤러로 전달하는 역할을 합니다. @Service는 주로 서비스 클래스를 나타내며, @Component의 특성을 그대로 가지고 있어 Spring 컨테이너에 의해 관리됩니다.

@Service
@RequiredArgsConstructor
public class UserService {
    private final UserRepository userRepository;

    public List<User> findAll() {
        return userRepository.findAll();
    }
}

@Repository

@Repository는 데이터 접근 계층에 사용됩니다. 이 어노테이션은 주로 데이터베이스와 상호작용하는 클래스를 나타냅니다. @Repository 어노테이션을 사용하면 Spring이 해당 클래스를 자동으로 데이터 접근 객체(DAO)로 인식하고, 예외 변환 기능을 제공합니다. @Repository는 @Service와 동일하게 @Component의 특성을 그대로 가지고 있어 Spring 컨테이너에 의해 관리되며, 데이터베이스와의 상호작용을 담당합니다.

// In-memory Database
@Repository
public class ItemRepository {

    private static final Map<Long, Item> store = new HashMap<>(); //static
    private static long sequence = 0L; //static

    public Item save(Item item) {
        item.setId(++sequence);
        store.put(item.getId(), item);
        return item;
    }
}


// JPA
@Repository
public interface UserRepository extends JpaRepository<User, Long> {
    List<User> findAll();
}

코드

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁

스프링 정리를 위한 포스팅입니다.
해당 포스팅은 Lombok 어노테이션 입니다.

Lombok이란?

Lombok은 Java 애플리케이션에서 보일러플레이트 코드(반복적인 코드)를 줄여주는 라이브러리입니다.

이를 통해 코드의 가독성을 높이고 유지보수를 쉽게 만들어 줍니다.

왜 Lombok을 사용해야 하는가?

• Java의 기본 클래스는 자주 사용되는 메서드(생성자, getter, setter, toString 등)를 수동으로 작성해야 합니다.
• Lombok은 이러한 반복적인 코드 생성을 자동화하여 개발 생산성을 크게 향상시킵니다.

Lombok 어노테이션 종류

@Getter / @Setter

• 클래스의 모든 필드에 대해 getter와 setter 메서드를 자동으로 생성합니다.

@Getter @Setter
public class Person {
    private String name;
    private int age;
}

@ToString

• 객체의 필드를 문자열로 변환하는 toString() 메서드를 자동으로 생성합니다.

@ToString 
public class Person { 
    private String name; 
    private int age; 
}

@NoArgsConstructor / @AllArgsConstructor

• 기본 생성자 및 모든 필드를 초기화하는 생성자를 자동으로 생성합니다.

@NoArgsConstructor
@AllArgsConstructor
public class Animal {
    int age;
    String name;
}

@Builder

• 빌더 패턴을 적용하여 객체 생성 시 가독성을 높입니다.

@Builder
public class Animal {
    int age;
    String name;
}

@Data

• @Getter, @Setter, @ToString, @EqualsAndHashCode, @RequiredArgsConstructor를 모두 포함하는 어노테이션입니다. 주로 DTO 객체에 사용됩니다.

@Data
public class Plant {
    private int height;
    private String origin;

    public Plant(int height, String origin) {
        this.height = height;
        this.origin = origin;
    }
}

Lombok 설치방법

spring에서 lombok을 설치하기 위해서는 maven 또는 gradle을 사용하면 됩니다. 저는 gradle을 사용하겠습니다. 

build.gradle에서 compileOnly 'org.projectlombok:lombok',  annotationProcessor 'org.projectlombok:lombok'

를 설정한 후에 gradle 프로젝트를 reload 하면 됩니다.

dependencies {
	// ...
	compileOnly 'org.projectlombok:lombok'
	annotationProcessor 'org.projectlombok:lombok'
}

예제 확인

public class Test {
    public static void main(String[] args) {
        // @Getter, @Setter
        Person person = new Person(1, 3, 4, 5, 8);
        System.out.println(person.getShoes()); // getShoes() automatically generated
        person.setShoes(84); // setShoes() automatically generated
        System.out.println(person.getShoes());

        // @ToString
        System.out.println("person.toString: " + person.toString()); // toString() automatically generated

        // @NoArgsConstructor / @AllArgsConstructor
        Animal tomy = new Animal(20, "tomy");
        Animal aymee = new Animal(); // Default constructor automatically generated
        System.out.println("tomy = " + tomy); // toString() automatically generated
        System.out.println("aymee = " + aymee); // toString() automatically generated

        // @Builder
        Animal hiro = Animal.builder().age(7).name("hiro").build(); // Using builder pattern
        System.out.println("hiro.toString() = " + hiro); // toString() automatically generated

        // @EqualsAndHashCode, @RequiredArgsConstructor
        Plant plant1 = new Plant(2, "korea");
        Plant plant2 = new Plant(2, "korea");

        // @Data
        System.out.println("plant1 equals plant2: " + plant1.equals(plant2)); // true, since fields are the same
        System.out.println("plant1 hashCode: " + plant1.hashCode()); // Same hashCode for equal objects
        System.out.println("plant2 hashCode: " + plant2.hashCode()); // Same hashCode for equal objects

        // @RequiredArgsConstructor automatically generates a constructor with final fields
        Plant plant3 = new Plant(3, "japan"); // Constructor with height and origin fields
        System.out.println("plant3: " + plant3); // toString() automatically generated
    }
}

다음과 같이 모든 어노테이션에 대해 결과를 확인할 수 있습니다.

코드

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

그리디 문제는 대부분 정렬과 조합을 이룬 문제가 많습니다. 따라서 가장 무거운 사람과 가장 무게가 작은 사람을 태워야 최대 limit를 채울 수 있습니다.

소스코드

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        Arrays.sort(people);
        int index = 0;
        
        for (int i = people.length - 1; i >= index; i--) {
            if (people[i] + people[index] <= limit) {
                index++;
            }
            answer++;
        }

        return answer;
    }
}

코드 설명

• 초기화
  • answer: 최소 보트 수를 저장하는 변수로 초기값은 0입니다.
  • index: 가장 가벼운 사람의 인덱스를 나타내는 변수로 초기값은 0입니다.
  • Arrays.sort(people): people 배열을 오름차순으로 정렬하여 무게가 가벼운 사람부터 무거운 사람 순으로 정렬합니다.
• for (int i = people.length - 1; i >= index; i--) { if (people[i] + people[index] <= limit) { index++; } answer++; }
  
  • i는 가장 무거운 사람의 인덱스를 가리킵니다. i는 배열의 끝에서 시작하여 index까지 감소합니다.
  • if (people[i] + people[index] <= limit): 가장 무거운 사람(people[i])과 가장 가벼운 사람(people[index])의 합이 limit 이하인지 확인합니다.
    • 조건이 true인 경우, 두 사람을 한 보트에 태울 수 있으므로 index를 1 증가시켜 다음으로 가벼운 사람을 가리키도록 합니다.
  • answer++: 보트를 사용한 횟수를 증가시킵니다. 무거운 사람(people[i])은 항상 보트에 태워지므로 answer는 무조건 증가합니다.
• return answer;
  • 최소 보트 수를 반환합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

연속된 숫자들 중에 가장 큰 수를 구하는 문제였습니다. 스택을 이용하여 나왔던 숫자들 중에 가장 큰 수를 구하였습니다.

소스코드

import java.util.*;

class Solution {
    public String solution(String number, int k) {
        int len = number.length();
        Stack<Character> answer = new Stack<>();
        
        for(int i = 0; i < len; i++) {
            char cur = number.charAt(i);
            while(!answer.isEmpty() && answer.peek() < cur && k-- > 0) {
                answer.pop();
            }
            answer.push(cur);
        }
        
        StringBuilder result = new StringBuilder();
        while (!answer.isEmpty()) {
            result.append(answer.pop());
        }
        
        if (k > 0) {
            return result.reverse().toString().substring(0, result.toString().length() - k);
        }
        
        return result.reverse().toString();
    }
}

코드 설명

• 변수 초기화
  
  • len: number 문자열의 길이.
  • answer: 각 문자를 저장하고, 조건에 따라 제거 및 추가하여 최종 결과를 만들기 위한 Stack.
  • cur: 현재 반복에서 number의 각 문자를 나타내는 변수.
  • result: 최종 결과를 역순으로 저장한 후, 다시 정방향으로 반환하기 위한 StringBuilder.
• while(!answer.isEmpty() && answer.peek() < cur && k-- > 0) { answer.pop(); } answer.push(cur);
  
  • answer 스택이 비어있지 않고 answer의 맨 위 문자(peek())가 현재 문자 cur보다 작고 k가 0보다 크면 스택의 맨 위 문자를 제거(pop())합니다.
  • 현재 문자인 cur을 answer 스택에 추가합니다.
• while (!answer.isEmpty()) { result.append(answer.pop()); }
  스택에 남아 있는 문자들을 result에 추가합니다. 이때 pop()을 사용하기 때문에 result는 역순으로 문자가 추가됩니다.
• if (k > 0) { return result.reverse().toString().substring(0, result.toString().length() - k); }
  
  • k가 남아 있는 경우, 결과 문자열에서 k개의 문자를 제거합니다.
  • result.reverse()를 통해 정방향으로 만든 후, substring()으로 마지막 k개의 문자를 잘라 반환합니다.
• return result.reverse().toString();
  • k가 0일 경우, result를 정방향으로 뒤집어 반환합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

커서의 위치를 찾는 것이 포인트였습니다. 아무리해도 정답이 안되어서 서치를 진행하였는데 전체 왕복 횟수를 계산하는 로직입니다.

소스코드

class Solution {
    public int solution(String name) {
        int answer = 0;
        int len = name.length();

        int index;
        int move = len;
        
        for(int i = 0; i < len; i++){
            answer += Math.min(name.charAt(i) - 'A', 'Z' - name.charAt(i) + 1);
            
            index = i + 1;
            while(index < len && name.charAt(index) == 'A'){
                index++;
            }
            
            move = Math.min(move, i * 2 + len - index);
            move = Math.min(move, (len - index) * 2 + i);
        }
        
        return answer + move;
    }
}

코드 설명

• for(int i = 0; i < len; i++) { answer += Math.min(name.charAt(i) - 'A', 'Z' - name.charAt(i) + 1); }
  
  • name.charAt(i) - 'A'는 'A'부터 현재 문자까지 위쪽 방향으로 이동할 때의 이동 횟수입니다.
  • 'Z' - name.charAt(i) + 1은 'Z'에서 반대 방향으로 이동하여 현재 문자에 도달하는 경우의 이동 횟수입니다.
  • 이 두 값 중 최소값을 취해 answer에 더합니다.
• 좌우 이동 횟수 계산
  • index는 현재 위치 i에서 시작하여, 연속된 'A' 구간의 끝을 찾기 위해 사용됩니다.
  • index가 문자열의 끝(len)에 도달하거나 'A'가 아닌 문자를 만나면 반복문을 종료합니다.
• move = Math.min(move, i * 2 + len - index); move = Math.min(move, (len - index) * 2 + i);
  
  • move는 현재까지 구한 좌우 이동의 최소값을 유지합니다.
  • i * 2 + len - index는 첫 번째 위치에서 i까지 이동한 후 다시 돌아와 남은 부분을 탐색하는 경우의 이동 거리입니다.
  • (len - index) * 2 + i는 반대 방향으로 탐색하다가 다시 i까지 돌아오는 경우의 이동 거리입니다.
  • 두 가지 방식 중 최소 이동 횟수를 move에 갱신합니다.
• return answer + move;
  • answer는 상하 이동 횟수의 총합이고, move는 최소 좌우 이동 횟수입니다. 이 둘을 합하여 최소 조이스틱 조작 횟수를 반환합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

그리디접근법으로 문제를 풀었습니다. 그리디는 정렬을 필요로하는 문제가 많습니다. 최적의 해를 구해야하기 때문입니다.

소스코드

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int len = lost.length;
        int answer= n - len;
        Set<Integer> clothes = new HashSet<Integer>();
        boolean[] visited = new boolean[len];
        
        for(int num : reserve) {
            clothes.add(num);
        }
        
        Arrays.sort(lost);
        for(int i = 0; i < len; i++) {
            if(clothes.contains(lost[i])) {
                answer++;
                visited[i] = true;
                clothes.remove(lost[i]);
            }
        }


        for(int i = len - 1; i >= 0; i--) {
            if (visited[i]) continue;
            
            if(clothes.contains(lost[i] + 1)) {
                clothes.remove(lost[i] + 1);
                answer++;
            } else if(clothes.contains(lost[i] - 1)) {
                clothes.remove(lost[i] - 1);
                answer++;
            }
        }


        return answer;
    }
}

코드 설명

• 초기화
  • n: 전체 학생 수.
  • len: lost 배열의 길이 (즉, 체육복을 잃어버린 학생들의 수).
  • answer: 체육수업에 참여할 수 있는 학생의 수 (초기값은 전체 학생 수에서 체육복을 잃어버린 학생 수를 뺀 값으로 설정됨).
  • clothes: 여벌 체육복을 가진 학생들의 번호를 저장할 HashSet 객체.
  • visited: lost 배열의 각 학생들이 여벌 체육복을 빌려서 해결되었는지 확인하는 배열.
• Set<Integer> clothes = new HashSet<Integer>(); for(int num : reserve) { clothes.add(num); }
  • reserve 배열을 순회하여 여벌 체육복을 가진 학생들의 번호를 clothes HashSet에 추가합니다. 이로써 여벌 체육복을 가진 학생들을 빠르게 찾을 수 있게 됩니다.
• for(int i = 0; i < len; i++) { if(clothes.contains(lost[i])) { answer++; visited[i] = true; clothes.remove(lost[i]); } }
  • 체육복을 잃어버린 학생 중 여벌 체육복이 있는 학생을 처리합니다.
• 두번째 for문
  • 여벌 체육복을 빌려주지 않은 학생들에게 체육복을 빌려주는 부분입니다.
  • visited[i]가 false인 학생들에 대해 여벌 체육복을 빌려줄 수 있는지 확인합니다.
  • lost[i] + 1 또는 lost[i] - 1이 여벌 체육복을 가진 학생 목록(clothes)에 있으면 해당 학생에게 체육복을 빌려줍니다.
  • 이때 clothes.remove(lost[i] + 1) 또는 clothes.remove(lost[i] - 1)로 여벌 체육복을 빌려준 학생을 제거하고, answer를 증가시킵니다.