문제

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one. You must implement a solution with a linear runtime complexity and use only constant extra space.

비어 있지 않은 정수 nums 배열이 주어지면, 모든 요소가 하나를 제외하고 두 번 나타납니다. 그 하나를 찾으세요. 선형 런타임 복잡도를 가진 솔루션을 구현하고 상수 추가 공간만 사용해야 합니다.

✅ 선형 런타임 복잡도 알고리즘의 실행 시간이 입력 데이터 크기(n)에 비례해 증가하는 것으로, 입력 데이터의 크기가 커질수록 실행 시간도 그만큼 증가한다. 빅오 표기법 - $O(n)$

예시

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

Input: nums = [1]
Output: 1

제약사항

• 1 <= nums.length <= 3 * 10⁴
• 3 * 10⁴ <= nums[i] <= 3 * 10⁴
• Each element in the array appears twice except for one element which appears only once.
  • 한 번만 나타나는 한 요소를 제외하고 배열의 각 요소는 두 번 나타납니다.

작성한 코드

class Solution {
    public int singleNumber(int[] nums) {
        if(nums.length == 1) return nums[0];

        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        for (int key : map.keySet()) {
            if(map.get(key) == 1) return key;
        }

        return nums[0];
    }
}

문제를 읽고 먼저 단순하게 생각나는 대로 풀어본 코드이다.

제약사항이 nums.length 가 최대 3 * 10⁴ 이어서 $O(n²)$(= 10⁸) 가 넘지 않도록 한 번의 nums 반복을 돌렸다.

• nums 의 num 은 map 에 최대 2의 value 가 존재할 것이다.
• map 을 반복하면서 value 가 1 인 key 를 반환한다.

nums 에는 한 숫자당 최대 2번 들어가 있기 때문에 map에는 최소 nums.length / 2 만큼의 key 를 갖고 있을 것이다. nums.length 가 여러번 반복하는 최악의 상황은 면하지만 map 자체로도 상당히 많은 key를 가지고 있기 때문에 두 번의 반복문이 상당히 비효율적으로 느껴졌다.

Submit 해 봤더니 13ms 가 측정됐다. 🫨 13ms 는 그냥 넘어갈 수 없다 … 하지만 마땅한 다른 풀이가 떠오르지 않는다. 최소 실행시간으로 측정된 다른 사람들의 코드를 참고했다.

참고한 코드

class Solution {
    public int singleNumber(int[] nums) {
        int result=0;
        for(int num:nums){
            result ^=num;
        }
        return result;
    }
}

나는 사용한 적이 극히 드물었던 ^= 계산식을 사용했다.

한 숫자 당 2번의 중복이 있는 배열 내에서 중복이 없는 숫자를 거르기 위한 방법으로 해당 계산식을 도출해 낼 수 있다는 게 대단하다고 느껴지면서 아직 나는 좀 더 생각의 범위를 넓혀야되겠다는 생각이 들었다.

^= 는 XOR 연산으로, 아래와 같은 특징을 가진다.

• a ^ a = 0 : 동일한 숫자를 XOR하면 결과는 0이다.
• a ^ 0 = a : 어떤 숫자와 0을 XOR하면 결과는 원래 숫자이다.
• (a ^ b) ^ c = a ^ (b ^ c) : 순서에 관계 없이 교환과 결합이 자유롭다.

nums = {4, 1, 2, 1, 2} 일 경우 처리 순서는 아래와 같다.

• result = 0
• result ^= 4 → 0 ^ 4 = 4
• result ^= 1 → 4 ^ 1 = 5 (0100 ^ 0001 = 0101)
• result ^= 2 → 5 ^ 2 = 7 (0101 ^ 0010 = 0111)
• result ^= 1 → 7 ^ 1 = 6 (0111 ^ 0001 = 0110)
• result ^= 2 → 6 ^ 2 = 4 (0110 ^ 0010 = 0100)

4 ^ 1 ^ 2 ^ 1 ^ 2 는 교환법칙 및 결합법칙에 따라 1 ^ 1 ^ 2 ^ 2 ^ 4 로 보면 더 이해가 간다.

(1 ^ 1) = 0, (2 ^ 2) = 0 이기 때문에(같은 숫자의 XOR 연산 결과는 0이기 때문에) 두 번 중복해서 XOR 연산되는 숫자는 0으로 상쇄되고 중복되지 않는 숫자만 남게 되는 것이다.

생각의 확장이 필요하다고 느끼게 해준 문제와 풀이였다.

문제 출처

https://leetcode.com/problems/single-number/description/

구글에서 개발한 RPC 프레임워크로, 네트워크를 통해서 다른 시스템의 함수를 호출할 수 있게 해 준다. 클라이언트 애플리케이션은 다른 머신의 서버 애플리케이션의 함수를 로컬 함수처럼 호출해 사용할 수 있다. 클라이언트와 서버는 다양한 환경으로 구성되어 실행하고 통신할 수 있다. Java 로 gRPC 서버를 만들고 Go, Python 등으로 gRPC 클라이언트를 만들 수 있는 등, gRPC 에서 지원하는 모든 언어로 다양하게 환경을 구성할 수 있다.

핵심 개념

RPC (Remote Procedure Call)

로컬에서 함수를 호출하듯이, 다른 서버의 함수를 호출할 수 있게 하는 기술. 예를 들어, A서버에서 B서버의 calculate(a, b)를 호출하면, 네트워크를 통해 통신해서 결과를 받을 수 있다.

Protocol Buffers (Protobuf)

gRPC는 데이터를 직렬화 및 역직렬화 하기 위해 Protocol Buffers 라는 포맷을 사용한다. Protocol Buffers 는 JSON이나 XML보다 더 빠르고 작은 크기로 데이터를 처리한다. .proto파일로 메세지와 서비스를 정의하면 정의한 내용을 바탕으로 프로토콜 버퍼 컴파일러(protoc)를 통해 각 언어에 맞게 사용할 수 있는 코드가 자동으로 생성된다.

Proto3 버전은 더 많은 언어 지원과 새로운 기능이 추가되었다. 일반적으로 현재 기본 프로토콜 버퍼 버전인 proto2를 사용할 수 있지만, gRPC 사용 시 proto3를 사용하는 것을 추천한다고 안내하고 있다. proto3는 gRPC에서 지원하는 모든 언어를 사용할 수 있고, proto2 와 proto3간의 통신에 대한 호환성 문제를 피할 수 있다.

HTTP/2 기반

gRPC는 HTTP/2 프로토콜을 사용해 기존 HTTP/1.1보다 빠른 통신과 효율적인 데이터 전송을 제공한다. HTTP/1.1은 하나의 요청-응답만 처리할 수 있다. 요청마다 별도의 TCP 커넥션을 열어야 하고, 추가 요청은 이전 요청이 끝나야 처리할 수 있다. HTTP/2는 다중화(멀티플렉싱)를 지원해 하나의 TCP 연결로 여러 요청과 응답을 동시에 처리할 수 있다. 또 헤더 압축, 서버 푸시, 스트림 지원 등의 기능을 통해 대역폭을 효율적으로 사용하고 지연 시간을 줄인다.

• 멀티플렉싱 하나의 TCP 연결로 여러 요청과 응답을 주고 받을 수 있는 기술.
  만약 a, b, c 세 개의 요청을 보냈다면 a 가 끝날 때까지 b, c가 기다리지 않고 병렬 처리된다.
  지연 시간 감소와 네트워크 효율성을 증가시킬 수 있다.

• 헤더 압축 HTTP/1.1 은 요청마다 헤더를 전송해 중복 데이터가 많다. HTTP/2는 HPACK 방식으로 헤더를 압축해 전송 데이터를 줄인다.
  데이터 전송량이 감소하며 속도가 향상된다.

• 스트림 지원 스트림이라는 독립적인 데이터 채널을 통해서 요청과 응답을 처리한다.
  각 스트림은 순서와 우선순위를 가지고 있어 네트워크 자원을 효과적으로 사용한다.
  요청이 많더라도 네트워크 충돌 없이 유연한 처리가 가능하다.

• 서버 푸시 클라이언트가 요청하지 않아도 서버가 데이터를 클라이언트에게 전송할 수 있는 방식. 클라이언트가 추가 요청을 보내기 전에 필요한 리소스를 받을 수 있어 지연 시간이 감소하고 불필요한 요청을 줄여 네트워크의 자원을 절약한다.
  ex) 클라이언트가 웹 페이지의 html 을 요청하면 서버가 html 뿐만 아니라 해당 페이지에 필요한 css, javascript 파일도 미리 전송할 수 있다. 클라이언트는 필요한 파일을 기다릴 필요가 없어 페이지 로드 시간이 단축된다.

  다양한 통신 방식

• 단일 요청 및 응답 일반적인 함수 호출처럼 요청에 대한 응답을 받는다.

  rpc SayHello(HelloRequest) returns (HelloResponse);

• 서버 스트리밍 클라이언트가 요청하면 서버에서 여러 응답을 스트리밍으로 보낸다. 클라이언트가 요청을 보내면 서버가 여러 개의 응답을 순차적으로 스트리밍한다. 개별 RPC 호출 내에서 메세지 순서를 보장하며 클라이언트는 더이상 메세지가 없을 때까지 반환된 스트림을 읽는다.

• ex)* 영화 스트리밍 서비스에서 클라이언트가 한번 요청하면 서버는 영화 데이터를 지속적으로 보낸다.

  rpc LotsOfReplies(HelloRequest) returns (stream HelloResponse);

• 클라이언트 스트리밍 클라이언트가 여러 데이터를 보내고 서버는 단일 응답을 보낸다. 개별 RPC 호출 내에서 메세지 순서를 보장한다.

• ex)* 클라이언트가 센서 데이터를 실시간으로 서버에 전송한다.

  rpc LotsOfReplies(stream HelloRequest) returns (HelloResponse);

• 양방향 스트리밍 클라이언트와 서버가 데이터를 동시에 주고 받는다. 서버는 응답하기 전에 모든 클라이언트 메세지를 수신할 때까지 기다리거나, 메세지를 읽고 쓰기를 번갈아 가거나, 읽기와 쓰기를 조합할 수 있다. 각 스트림의 메세지 순서는 유지된다.

  rpc BidHello(stream HelloRequest) returns (stream HelloResponse);

스트리밍 데이터를 한번에 전송하는 대신, 일정한 간격으로 나누어 전송하는 방식

Stub

클라이언트와 서버 간 통신을 간단하게 만들어주는 자동 생성되는 코드로, Stub을 통해 클라이언트는 원격 서버의 함수를 로컬 함수처럼 호출할 수 있고 네트워크 관련한 복잡한 처리를 직접 구현하지 않아도 된다. Stub은 클라이언트와 서버 간의 _중간 인터페이스 역할_을 한다.

• 클라이언트 Stub
  • 서버의 함수 호출을 로컬 함수 호출처럼 사용할 수 있게 해주는 인터페이스
  • 클라이언트는 Stub을 통해서 네트워크 요청 및 응답 처리를 자동으로 수행한다.
  • 원격 호출 과정은 Stub내부에서 처리된다.
• 서버 Stub
  • 클라이언트 요청을 받아 해당 로직을 실행하고 응답을 보내는 역할을 한다.
  • 클라이언트로부터 받은 데이터를 역직렬화 해 실제 서버 함수로 전달한다. 함수 실행 후에는 결과를 직렬화 해 응답한다.

    동작 과정

1. .proto 파일 작성 - 서비스 정의 및 요청/응답 메세지 구조 작성

   syntac = "proto3";
   

message PersonRequest { int32 id = 1; }

message PersonResponse { string name = 1; int32 id = 2; string email = 3; }

service PersonService { rpc GetPerson (PersonRequest) returns (PersonREsponse); }

2. `protoc` 를 사용해 클라이언트와 서버의 `Stub` 코드 자동 생성
- ex) 클라이언트 : `PersonServiceGrpc.PersonServiceBlockingStub`
- ex) 서버 : `PersonServiceGrpc.PersonServiceImplBase`
3. 클라이언트 `Stub`호출
`Stub`을 통해 서버의 함수를 호출하고, 요청 데이터를 직렬화 해 네트워크로 전송

4. 서버 `Stub` 처리
클라이언트로부터 요청 데이터를 받아 디코딩, 실제 구현된 함수 로직을 수행하고 결과를 반환
### Stub 의 종류
|종류|동작|
|---|---|
|Blocking Stub|동기 방식으로 동작.|
|Async Stub|비동기 방식으로 동작.<br>서버의 응답을 기다리지 않고 요청을 보낸 후, 콜백 함수를 통해 결과 처리|
|Future Stub|비동기 호출의 결과를 `Future`객체로 반환.<br>클라이언트가 나중에 결과 확인 가능|
## 장점과 단점
gRPC는 `Protocol Buffers` 와 `HTTP/2` 덕분에 더 빠르고 효율적이다. Java, Python, Go, C++ 등 다양한 언어로 사용 가능하며, `.proto` 파일로 자동화된 코드로 클라이언트와 서버 코드를 쉽게 생성한다. 또 단일 요청부터 양방향 스트리밍까지 다양한 통신을 지원하고 있어 각각의 서비스 요구사항에 맞게 설계할 수 있어 유연성이 높다.

하지만 gRPC를 활용하기 위한 추가 학습이 필요하다. 단순 CRUD 서비스에서는 과도한 도입일 수 있다. 브라우저는 웹소켓이나 RESTful API 를 통해야 사용이 가능한데, 브라우저 클라이언트와의 직접 통신이 필요한 경우 REST보다 불편할 수 있다. 또 `grpccurl`, `Postman` 등의 추가 도구 없이는 디버깅이 어렵다.
## RESTful API 와 gRPC의 차이
|기능|RESTful API|gRPC|
|---|---|---|
|통신 프로토콜|HTTP/1.1|HTTP/2|
|데이터 형식|JSON|Protocol Buffers (바이너리 형식)|
|성능|텍스트 기반으로 상대적으로 느림|바이너리 기반으로 빠르고 효율적|
|코드 생성|직접 작성 필요|`.proto` 파일로 자동 생성
|다중 언어 지원|언어간 표준 없음|다양한 언어에서 동일한 방식으로 사용 가능|
|유연성|단일 요청-응답|스트리밍, 양방향 통신 등의 다양한 방식 지원|
gRPC 공식 FAQ에 의하면, gRPC가 REST와 비교해 아래와 같이 기술하고 있다.
>**Why is gRPC better/worse than REST? **
gRPC largely follows HTTP semantics over HTTP/2 but we explicitly allow for full-duplex streaming. We diverge from typical REST conventions as we use static paths for performance reasons during call dispatch as parsing call parameters from paths, query parameters and payload body adds latency and complexity. We have also formalized a set of errors that we believe are more directly applicable to API use cases than the HTTP status codes.

### **HTTP/2** 기반의 HTTP 시맨틱
gRPC는 `HTTP/2` 기반으로 동작하며, `HTTP` 의 기본적인 동작 원칙을 따른다.
하지만 gRPC는 _풀-듀플렉스 스트리밍_(클라이언트와 서버가 동시에 데이터를 주고받을 수 있는 기술, 양방향 스트리밍) 을 명시적으로 지원한다.
### REST의 전형적인 관례
gRPC는 **정적 경로(static path)**를 사용한다. 이는 **_Call Dispatch_** 의 성능을 높이기 위해서다.
> **Call Dispatch**
클라이언트 요청을 서버에서 적절한 서비스나 메서드로 매핑하는 방식
- REST: 동적 경로를 파싱하고 경로 및 매개변수에 따라 호출할 핸들러를 찾는다.
- gRPC: 정적 경로를 사용해 추가적인 파싱 과정 없잉 서비스와 메서드를 즉시 매핑한다.

정적 경로는 고정된 URL 형식을 사용한다. 경로의 구조가 일정하고 요청마다 변하지 않는다. gRPC는 서비스 호출 경로를 `.proto`파일에 정의된 고정 경로를 사용한다. 서비스 이름과 메서드 이름으로 구성되며 요청 데이터는 페이로드로 전달된다.

service Calculator { rpc Add (AddRequest) returns (AddResponse); }

// 경로 : /Calculator/Add

동적 경로는 경로에 변수나 매개변수를 포함할 수 있다.

/users/{id}/orders/{orderId}

``` REST는 경로, 쿼리 매개변수, 페이로드에서 데이터를 파싱하는데, 이러한 방식은 지연 시간과 복잡성을 증가시킬 수 있어 gRPC는 REST의 관례를 따르지 않는다.

표준화된 에러 처리 방식

gRPC는 API 사용 사례에 더 적합하다고 판단한 표준화된 에러 세트를 정의해 사용한다. REST에서 일반적으로 사용하는 HTTP 상태 코드보다 더 직관적이고 API에 적합한 에러 코드 체계를 제공한다.

REST 의 HTTP 상태 코드는 gRPC의 에러 코드와 아래와 같이 매핑할 수 있다.

• 400 Bad Request -> INVALID_ARGUMENT
• 401 Unauthorized -> UNAUTHENTICATED
• 403 Forbidden -> PERMISSION_DENIED
• 404 Not Found -> NOT_FOUND
• 500 Internal Server Error -> INTERNAL

특히 HTTP 상태 코드 500은 gRPC에서 INTERNAL, UNAVAILABLE, DATA_LOSS 등으로 더 명확히 구분할 수 있다.

gRPC 는 낮은 지연 시간과 높은 확장성으로 분산 시스템 및 MSA 구조에서 효율적으로 활용할 수 있다. 단순한 구조의 시스템에서 적용하기에 과도할 수 있지만, 여러 서비스 간 통신이 빈번하고 대규모 서비스 간의 통신을 효율적으로 다루기 위해서 다양한 설계 방식을 적용하는 데에 최적화 할 수 있는 기술로 활용할 수 있다.

실제 업무에 도입해서 사용했을 때 크게 와닿았던 부분은 엄격한 인터페이스 관리가 가능하다는 점이었다. 서버와 클라이언트가 .proto 파일에 정의된 내용이 동일하지 않으면 (필드 번호가 변경되거나, 데이터 타입이 변경되는 등) Stub 메서드 호출 시점에 에러가 발생한다. 당시에 프로젝트를 진행하면서 배포와 픽스를 반복하며 속도감 있게 진행했는데, 반영된 변경사항을 조금 더 빠르게 인지할 수 있었고 하나의 파일로 정의된 작업 내용을 파악할 수 있어 업무 소통에 유연함을 더할 수 있었다. 처음 .proto파일을 작성하는 것이 처음에는 꽤나 귀찮(...)았지만, 활용에 익숙해지면서 gRPC 동작 방식과 핵심 개념, 이점을 이론적으로 이해하고 기술의 목적에 기반해 설계에 맞게 적용할 수 있는 스킬을 갖추기 위해 정리하였다.

참고

https://grpc.io/docs/

아키텍처 구성

사용자가 요청을 보낼 때는 EC2 를 통해 요청을 보내고, EC2 내부에서 프로세스와 Redis 가 통신하도록 세팅한다. 또 RDS 를 활용해 외부에서 데이터베이스 통신할 수 있도록 구성한다.

인프라 구성

EC2 생성 설정

대부분의 옵션은 디폴트로 두고 몇몇 옵션만 설정해 주었다. 특히 인스턴스 유형을 t3a.small 로 변경해 생성했는데, t2.micro 에서 Spring Boot, Redis 를 다 돌리기엔 성능이 모자라다고 한다. 또 VPC 보안 그룹에서 8080 포트가 접근 가능한 보안 규칙을 추가한다.

RDS 생성 설정

RDS 또한 대부분의 옵션을 디폴트로 둔다. MySQL 로 초기 데이터베이스 옵션을 로컬에서 생성한 데이터베이스명과 동일하게 설정했다. 생성 후에는 보안 그룹에서 3306 포트를 열어주는 인바운드 규칙을 추가한다.

EC2 인스턴스 내에 jdk, Redis 설치

sudo apt update
sudo apt install redis
sudo apt install openjdk-17-jdk

EC2 에 로컬 환경에서 작업한 프로젝트 이동

EC2에서 코드를 clone 하기 전에 profile 을 분리한다. public repository 로 커밋했기 때문에 데이터베이스 정보는 별도로 EC2 내부에서 환경 변수를 설정했다.

spring:
  config:
    activate:
      on-profile: prod
  datasource:
    url: ${DB_URL}
    username: ${DB_USER}
    password: ${DB_PASSWORD}

EC2 에서 git clone 후 jar 파일을 실행한다.

./gradlew clean build -x test

프로젝트 디렉토리의 /build/libs 내에 생성된 jar 파일을 확인할 수 있다.

jar 파일을 실행하면 정상적으로 실행 완료됨을 확인할 수 있다.

결과

기대한 대로 성능 차이가 있는지 postman 으로 API 를 요청해보자.

첫번째 요청

2.13s 의 소요시간 확인.

두번째 요청

39ms 의 소요시간 확인. 캐싱되어 조회 속도가 확연히 줄어들었다.

Redis 에 저장된 데이터 확인

의도대로 EC2 에 설치한 Redis 에 데이터가 저장되어 있음을 확인할 수 있다.

실무 환경에서는 Azure 로 구성되어 있어서 AWS 에 대한 지식이 부족한데, 실습 해 보면서 EC2 인스턴스와 RDS에 대한 추가적인 학습이 필요하다고 느꼈다. 일단 익혀보고 필요한 부분은 더 학습해 봐야지 ...

학습에 참고한 강의

https://inf.run/Pupon

• 키는 일반 텍스트일 수도 있고 해시 값일수도 있다. 성능상의 이유로 키는 짧을수록 좋다.
• 값은 문자열일 수도 있고, 리스트, 객체 일수도 있다. 보통 값으로 무엇이 오든 상관하지 않는다.

아마존 DynamoDB, memcached, Redis 등이 키-값 저장소의 예다.

단일 서버 키-값 저장소

한 대의 서버만 사용하는 키-값 저장소를 설계하는 가장 직관적인 방법은, 키-값 쌍 전부를 메모리에 해시 테이블로 저장하는 것이다. 이 방법은 빠른 속도를 보장하고 있긴 하지만 모든 데이터를 메모리 안에 두는 것이 불가능할 수도 있다는 약점을 가지고 있다. 이에 대한 개선책으로는 아래와 같은 것이 있다.

• 데이터 압축 (compression)
• 자주 쓰이는 데이터만 메모리에 두고 나머지는 디스크에 저장

이러한 개선책으로도 단일 서버로는 부족해지는 상황이 온다. 많은 데이터를 저장하려면 분산 키-값 저장소(distributed key-value store) 를 만들 필요가 있다.

분산 키-값 저장소

키-값 쌍을 여러 서버에 분산시키기 때문에 분산 해시 테이블이라고도 불린다.

분산 시스템을 설계할 때는 CAP 정리를 이해하고 있어야 한다.

CAP 정리

CAP 정리는 데이터 일관성, 가용성, 파티션 감내 라는 세 가지 요구사항을 동시에 만족하는 분산 시스템을 설계하는 것은 불가능하다는 정리다. 세 요구사항 중 두 가지를 충족하려면 나머지 하나를 희생해야 하는 트레이드오프를 고려해야 한다.

파티션 감내에서 등장하는 네트워크 파티션은 네트워크 장애로 인해 분산 시스템의 일부 노드들이 통신할 수 없는 상태가 되는 상황이다. 분산 시스템의 네트쿼크가 분리된 상태로 볼 수 있는데, 이 때문에 네트워크 통신 장애가 발생해 데이터 동기화나 요청 문제가 발생할 수 있다.

[예시 상황] - 여러 서버(A, B, C, D)가 서로 통신하며 데이터를 동기화하고 있다고 가정 - 갑자기 네트워크 장애가 발생하여 서버 A와 B는 서로 통신할 수 있지만, 서버 C와 D는 다른 네트워크 섹션에 갇혀 A와 B와 통신하지 못하는 상황

A -- B
X   X (네트워크 장애)
C -- D

이 경우, A와 B는 서로 통신할 수 있지만, C와 D는 A, B와 분리된 네트워크 파티션에 속해 서로 통신할 수 없다. 즉, 네트워크가 둘로 분리된 상태이다.

세 요구사항 중 두 가지를 충족할 경우의 시스템 별 차이

• CA 시스템
  • 일관성과 가용성을 만족하는 키-값 저장소. 파티션 감내는 지원하지 않지만 통상 네트워크 장애는 피할 수 없는 일로 여겨지기 때문에 분산 시스템은 반드시 파티션 문제를 감내할 수 있도록 설계되어야 한다. 사실상 실세계에서는 존재하지 않는 시스템으로 볼 수 있다.
• CP 시스템
  • 일관성과 파티션 감내를 만족하는 키-값 저장소. 가용성을 희생한다. CP 시스템에서는 네트워크 장애가 발생할 경우 각 노드의 데이터 일관성을 보장하기 위해 장애 상황에서 몇 클라이언트의 통신이 제한될 수 있다. 금융 시스템이나 거래 시스템 등 데이터 무결성이 중요한 경우에 적합하다.
• AP 시스템
  • 가용성과 파티션 감내를 만족하는 키-값 저장소. 일관성을 희생한다. 네트워크 파티션 동안에도 모든 클라이언트 요청에 가능한 한 응답을 제공한다. 동기화 되지 않는 데이터를 반환하더라도 장애가 발생한 노드 외의 정상 상태의 노드는 계속 읽기 연산을 수행한다. 소셜 미디어나 검색 엔진처럼 서비스 연속성이 중요한 경우에 적합하다.

해시 키 재배치 문제 (rehash)

해시 키 재배치 문제는 안정 해시 기술로 풀고자 하는 문제이다. N 개의 캐시 서버가 있을 경우, 균등하게 부하를 나누기 위해서는 보편적으로 아래의 해시 함수를 사용한다.

$serverIndex = hash(key) % N*$

특정 키가 보관된 서버를 알아내기 위해, 나머지 연산을 f(key) % N 과 같이 적용한 결과를 활용할 수 있다. 예를 들어 hash(key0) % 4 = 1 이면, 클라이언트는 캐시에 보관된 데이터를 가져오기 위해 서버 1에 접속해야 한다.

이 방법은 서버 풀 (server pool) 의 크기가 고정되어 있을 때, 그리고 데이터 분포가 균등할 때는 잘 동작하지만 서버가 추가되거나 기존 서버가 삭제될 경우에 문제가 생긴다. 예를 들어 기존 서버 1 이 동작을 중단한다면 서버 풀의 크기는 3으로 변동된다. 그 결과로 키에 대한 해시 값은 변하지 않지만 나머지 연산을 적용해 계산한 서버 인덱스 값은 달라질 것이다. 이렇게 될 경우 문제가 있던 서버 1 에 보관되어 있던 키 뿐만 아니라 대부분의 키가 재분배된다. 서버 1이 죽으면 대부분 캐시 클라이언트가 엉뚱한 서버에 접속하게 되며, 그 결과로 대규모 캐시 미스가 발생하게 될 것이다. 안정 해시는 이 문제를 효과적으로 해결하는 기술이다.

안정 해시

“안정 해시(consistent hash) 는 해시 테이블 크기가 조정될 때 평균적으로 오직 k/n 개의 키만 재배치하는 해시 기술이다. k 는 키의 개수이고, n 은 슬롯(slot) 의 개수다. 이와 달리 대부분의 전통적 해시 테이블은 슬롯의 수가 바뀌면 거의 대부분의 키를 재배치한다.” - 위키피디아

해시 공간과 해시 링

해시 함수 f 로는 SHA-1 를 사용하고, 그 함수의 출력 값 범위는 x0, x1, … , xn 과 같다고 하자. (SHA-1 의 해시 공간(hash table) 범위는 0 ~ 2^160 - 1 까지로 알려져 있다.) 일렬로 x0 부터 xn 까지 공간을 나열하고 양쪽을 구부려 만나도록 접으면 해시 링(hash ring) 이 만들어진다.

해시 링 위에 해시 서버와 해시 키를 어느 지점에 배치하게 되면, 해당 키의 위치로부터 시계 방향으로 링을 탐색해 나가면서 가장 먼저 만나는 서버에 해시 키를 저장한다. 서버 조회 시에도 동일하게 해당 키의 위치로부터 탐색해 나가며 가장 먼저 만나는 서버가 해시 키가 저장된 서버이다.

만약 서버를 추가하게 되면 키 가운데 일부만 재배치하게 된다. 서버를 추가한 후 어떠한 키는 가장 먼저 만나게 되는 서버가 달라질 수 있으며, 이런 경우에 해당하는 키만 재배치 되고 나머지 키는 기존과 같은 서버에 남는다. (재배치 되지 않는다.) 서버 제거 시에도 키 가운데 일부만 재배치 되며 나머지 키는 영향이 없다.

기본 구현법의 두가지 문제

안정 해시 알고리즘은 MIT 에서 처음 제안되었으며, 기본 절차는 다음과 같다.

• 서버와 키를 균등 분포(uniform distribution) 해시 함수를 사용해 해시 링에 배치한다.
• 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버이다.

이 접근법에는 두 가지 문제가 있다.

1. 서버가 추가되거나 삭제되는 상황을 감안하면 파티션(인접한 서버 사이의 해시 공간)의 크기를 균등하게 유지하는 게 불가능하다. 어떤 서버는 굉장히 작은 해시 공간을 할당 받고, 어떤 서버는 굉장히 큰 해시 공간을 할당 받는 상황이 가능하다. 예를 들어 s0 과 s2 사이의 s1이 삭제되었을 경우 s2의 파티션이 다른 파티션 대비 거의 두 배로 커질 수 있다.
2. 키의 균등 분포를 달성하기 어렵다. 예를 들어 k1 의 시계 방향으로 s0, s1 가 있다면 가장 먼저 만나는 s0 에 k1 가 저장되고 s1 에는 아무 데이터도 저장되지 않을 것이다. k2, k3, k4 의 위치 사이에 서버가 존재하지 않으면 k4 다음에 존재하는 서버에 대부분의 키가 저장될 것이다.

이러한 문제를 해결하기 위해 제안된 기법이 가상 노드(virtual node) 또는 복제(replica) 기법이다.

가상 노드 (virtual node)

가상 노드는 실제 노드 또는 서버를 가리키는 노드로서, 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다.

s0 과 s1 은 각각 3개의 가상 노드를 갖는다고 하자. s0 을 링에 배치하기 위해 s0 하나만 쓰는 대신, s0_0, s0_1, s0_2 의 세 개의 가상 노드를 사용한다. 따라서 각 서버는 하나가 아닌 여러 개 파티션을 관리해야 한다. 키의 위치로부터 시계 방향으로 링을 탐색하다 최초로 만나는 가상 노드가 해당 키를 저장할 서버가 된다.

가상 노드의 개수를 늘리면 키의 분포는 점점 더 균등해진다. 표준 편차(standard deviation)가 작아져 데이터가 고르게 분포되기 때문이다. 표준 편차는 데이터가 어떻게 퍼져 나갔는지를 보이는 척도다. https://tom-e-white.com/2007/11/consistent-hashing 에 따르면 100200 개의 가상 노드를 사용했을 경우 표준 편차 값은 평균의 510% 사이다. 가상 노드의 개수를 더 늘리면 표준 편차의 값은 더 떨어진다. 그러나 가상 노드 데이터를 저장할 공간은 더 많이 필요하게 될 것이다. 이에 대한 tradeoff 가 필요하며 시스템 요구사항에 맞도록 가상 노드 개수를 적절히 조정해야 할 것이다.

재배치할 키 결정

서버가 추가되거나 제거되면 데이터 일부를 재배치 해야 한다. 어느 범위의 키들이 재배치 되어야 하는지 확인할 수 있다. 서버가 추가되거나 제거되면 반시계 방향에 있는 이전 서버 이후에 배치되어 있는 키들이 영향을 받는다.

안정 해시의 이점

• 서버가 추가되거나 삭제될 때 재배치되는 키의 수가 최소화된다.
• 데이터가 보다 균등하게 분포되므로 수평적 규모 확장성을 달성하기 쉽다.
• 핫스팟(hotspot) 키 문제를 줄인다. 특정한 샤드(shard) 에 대한 접근이 지나치게 빈번하면 서버 과부하 문제가 생길 수 있다. 안정 해시는 데이터를 좀 더 균등하게 분배하기 때문에 이런 문제가 생길 가능성을 줄인다.

안정 해시 실사용 예시

• 아마존 다이나모 데이터베이스(DynamoDB) 의 파티셔닝 관련 컴포넌트
• 아파치 카산드라 (Apache Cassandra) 클러스터에서의 데이터 파티셔닝
• 디스코드 채팅 어플리케이션
• 아카마이(Akamai) CDN
• 매그레프(Megrev) 네트워크 부하 분산기

캐시(Cache)

원본 저장소(Database) 보다 빠르게 가져올 수 있는 임시 데이터 저장소

캐싱(Caching)

캐시(임시 데이터 저장소)에 접근해 데이터를 빠르게 가져오는 방식

데이터 캐싱 전략

Cache Aside

데이터를 조회할 때 Redis 를 먼저 쳐서 데이터를 조회하고, 조회하고자 하는 데이터가 저장되어 있지 않으면 DB 에서 조회해 오는 방식

Write Around

데이터를 저장할 때 Redis 에 반영하지 않고 DB 에만 데이터를 저장

문제점

Cache Aside 는 조회에 초점을 맞추고, Write Around 는 저장에 초점을 맞추고 있어 두 전략을 같이 사용하는데, 이 때 문제가 될 수 있는 점이 2가지가 있다.

• DB와 Redis 에 저장된 데이터가 다를 수 있다. 즉 데이터 일관성이 보장되지 않을 수 있다.
• 캐시 저장 공간은 DB(Disk) 보다 작다.

데이터 동기화를 위해 DB 수정 사항이 있을 때마다 Redis 까지 반영하게 되면 성능 부하가 커지게 되기 때문에, 캐싱 서버를 활용할 때 이러한 문제를 해결하기 위해서 아래와 같은 케이스의 데이터를 기준으로 활용하는 것이 좋다.

• 자주 조회되는 데이터
• 잘 변하지 않는 데이터
• 실시간으로 변경이 반영되지 않아도 될 데이터

또한 Redis 의 TTL 기능을 활용해서, 적절한 주기로 데이터를 동기화할 수 있도록 한다. 데이터가 만료되면 Cache Miss 가 발생하기 때문에 새롭게 DB 에서 조회한 후에 Redis 에 저장한다. 또 자주 사용하지 않는 데이터는 TTL 에 의해 자동으로 삭제될 것이기 때문에 저장 공간에 대한 여유도 확보할 수 있다.

Spring Boot + Redis

프로젝트 설정

• Gradle
• Java 17
• Spring Boot 3.3.5
• MySQL version 8.* 이상
• Dependency Spring Boot DevTools Spring Web Spring Data JPA MySQL Driver

조회 성능을 테스트할 수 있는 간단한 조회 API 를 구현했다. 해당 API 에 캐싱을 적용할 수 있도록 Redis 설정을 추가한다.

• RedisConfig
• RedisCacheConfig

RedisConfig

Redis 연결을 설정한다. spring data redis 에서 제공하는 Lettuce 라이브러리를 활용해 Redis 연결을 관리하는 Bean 을 등록한다.

@Configuration
public class RedisConfig {
    @Value("${spring.data.redis.host}")
    private String host;

    @Value("${spring.data.redis.port}")
    private int port;

    @Bean
    public LettuceConnectionFactory lettuceConnectionFactory() {
            // Redis 서버의 호스트, 포트 설정
            return new LettuceConnectionFactory(host, port);
        }
}

RedisCacheConfig

Spring 의 캐싱 기능을 활성화하고 Redis 를 캐시 저장소로 사용하기 위한 추가 설정을 작성한다. RedisCacheConfiguration 을 통해 캐시 저장 방식과 TTL 설정을 추가했다. 정의된 캐시 설정을 적용한 RedisCacheManager 빈을 등록해 board 도메인의 캐싱을 위한 boardCacheManager 을 생성한다.

@Configuration
@EnableCaching // Spring Boot 의 캐싱 활성화
public class RedisCacheConfig {

    @Bean
    public CacheManager boardCacheManager(RedisConnectionFactory redisConnectionFactory) {
            RedisCacheConfiguration redisCacheConfiguration = 
                    RedisCacheConfiguration
                        .defaultCacheConfig()
                        .serializeKeysWith( // Redis 에 Key 를 저장할 때 String 으로 직렬화해 저장
                                RedisSerializationContext.SerializationPair.fromSerializer(
                                        new StringRedisSerializer()
                                ))
                        .serializeValuesWith( // Redis 에 Value 를 저장할 때 Json 으로 직렬화해 저장
                                RedisSerializationContext.SerializationPair.fromSerializer(
                                        new Jackson2JsonRedisSerializer<Object>(Object.class)
                                ))
                        .entryTtl(Duration.ofMinutes(1)); // TTL 설정

        return RedisCacheManager
                            .RedisCacheManagerBuilder
                            .fromConnectionFactory(redisConnectionFactory)
                            .cacheDefaults(redisCacheConfiguration)
                            .build();
        }
}

BoardService

Spring 의 @Cacheable 을 사용하면 Cache Aside 전략을 적용할 수 있다. 예를 들어 1페이지에서 10개의 board 를 조회하는 요청이 오면 Redis 에 boards:page:1:size:10 key 로 저장된 데이터가 있는지 확인하고, 데이터가 없다면 내부 로직을 수행한다. Redis 에 저장되어 있을 경우 메서드를 실행하지 않고 Redis 에서 해당 value 를 바로 반환한다.

@Cacheable(cacheNames = "getBoards", key = "'boards:page:' + #page + ':size:' + #size", cacheManager = "boardCacheManager")
    public List<Board> getBoards(int page, int size) {
        Pageable pageable = PageRequest.of(page - 1, size);
        Page<Board> boards = boardRepository.findAllByOrderByCreatedAtDesc(pageable);
        return boards.getContent();
    }

결과

첫번째 요청

애플리케이션을 실행하고 첫 요청은 Redis 에 아무 데이터도 저장되어 있지 않기 때문에 아래와 같은 로그를 확인할 수 있다. Redis 에 데이터가 없어 DB select 후 캐싱되었다.

두번째 요청

첫번째 요청에서 Cache miss 가 발생했기 때문에 두번째 요청 시에는 아래와 같은 로그를 확인할 수 있다. Redis 에서 boards:page:1:size:10 key 로 저장된 데이터를 조회했다.

redis-cli 로 데이터 확인

Redis 에 정상적으로 데이터가 저장된 것을 확인할 수 있다.

캐싱 전 후 성능 비교

첫번째 요청과 두번째 요청의 속도 차이를 비교해보자. postman 으로 캐싱 전후의 수치를 확인할 수 있다.

첫번째 요청 - 286ms 소요

두번째 요청 - 6ms 소요

학습에 참고한 강의

https://inf.run/Pupon

목적

market-api 에서 store-api 로 가게 정보를 요청한다고 가정해 보자. store-api 로 가게 정보 조회 시에 아래와 같은 에러가 발생한 경우이다.

• Caused by: org.apache.http.NoHttpResponseException: store-api.store:80 failed to respond

NoHttpResponseException 이 발생한 원인으로는 store-api 의 불안정한 서버 상태로 일시적인 통신 문제가 발생했을 가능성이 있기 때문에 재시도를 수행해 보고, 최대 재시도 횟수를 넘기면 클라이언트에서 에러를 처리할 수 있도록 하고자 한다.

물론 에러가 발생한 store-api 의 문제 해결도 필요하지만 클라이언트에서 이러한 상황이 발생했을 경우 어떻게 핸들링할지를 목적으로 한다!

Open Feign Retryer

Spring Cloud Open Feign Document Feign 은 기본적으로 Retryer.NEVER_RETRY 상태의 Bean 이 생성되어 Retry 를 시도하지 않기 때문에 Retry 를 시키려면 추가적인 설정이 필요하다. Feign 이 제공하는 Retryer 은 IOException 이 발생한 경우에만 처리되어 일시적인 네트워크 관련 예외로 처리하고 ErrorDecoder 에서 throw 된 모든 RetryableException 을 처리한다.

아래와 같이 정의해 보았다.

• 재시도는 아래의 경우 100ms 간격으로 5번 재시도한다.
  • NoHttpResponseException 이 발생
  • 503 httpStatus

재시도가 필요한 경우는 주로 일시적이고 간헐적인 장애로 인해 요청이 실패했을 때이며, 이러한 장애가 해결될 가능성이 있는 상황에서 유용하다. 그러나 서버가 장기적으로 문제가 있거나 요청이 항상 실패하는 상황에서는 재시도가 오히려 부하를 가중시키고, 문제를 해결하지 못할 수 있기 때문에 이러한 상황에서는 다른 적절한 대응 전략을 고려하는 것이 중요하다.

FeignRetryConfiguration (Retryer)

Retryer 인터페이스는 Feign 클라이언트에서 요청 재시도 로직을 정의하는 데 사용된다.

기본적으로 Retryer.Default라는 기본 구현을 제공하는데, 이 기본 구현은 재시도를 하지 않고 예외를 바로 전파한다. 이 기본 구현을 토대로 커스텀 구현을 통해 재시도 횟수와 대기 시간을 설정할 수 있다.

Retryer 의 continueOrPropagate(RetryableException e) 는 재시도를 수행할지, 예외를 전파할지 결정한다. RetryableException 이 인자로 전달되기 때문에 Feign 클라이언트에서 그 외의 Exception 이 발생할 경우 continueOrPropagate() 를 타지 않는다.

@Slf4j
public class FeignRetryConfiguration {
    @Bean
    public Retryer retryer() {
        return new CustomRetryer();
    }
    public static class CustomRetryer implements Retryer {
        private final int maxAttempts;
        private final long backoff;
        private int attempt;
        public CustomRetryer() {
            this(100, 5);// 100ms씩 5번 시도
        }
        public CustomRetryer(long backoff, int maxAttempts) {
            this.backoff = backoff;
            this.maxAttempts = maxAttempts;
            this.attempt = 1;
        }
        @Override
        public void continueOrPropagate(RetryableException e) {
            if (attempt++ >= maxAttempts) {
                log.error("Retry failed after {} attempts to {}", maxAttempts, e.request().httpMethod() + " " + e.request().url());
                throw e;
            }
            log.info("Retry attempt #{} after exception: {}, request: {} ", attempt, e.getMessage(), e.request().httpMethod() + " " + e.request().url());
            try {
                TimeUnit.MILLISECONDS.sleep(backoff);
            } catch (InterruptedException ignored) {
                Thread.currentThread().interrupt();
            }
        }
        @Override
        public Retryer clone() {
            return new CustomRetryer(backoff, maxAttempts);
        }
    }

FeignExceptionErrorDecoder (ErrorDecoder)

ErrorDecoder는 Feign 클라이언트 라이브러리에서 사용하는 인터페이스로, HTTP 응답에서 오류가 발생했을 때 해당 오류를 해석하여 예외를 생성하는 역할을 한다.

Feign 클라이언트 호출이 실패할 때 (에러 코드 4xx, 5xx 반환 시) decode() 가 호출되고, 별도로 커스텀 하지 않을 경우 기본 구현에 따라 Feign 클라이언트에서 반환한 Exception 을 반환한다.

문제가 되었던 store-api 에서 FeignException 이 발생했을 때 발생한 exception 이 NoHttpResponseException 이거나 HttpStatus 가 SERVICE_UNAVAILABLE(503) 일 경우 Retry 를 수행할 수 있도록 FeignExceptionErrorDecoder 를 추가해보자.

public class RetryableExceptionErrorDecoder implements ErrorDecoder {
    private final ErrorDecoder defaultErrorDecoder = new Default();
    @Override
    public Exception decode(String methodKey, Response response) {
        Exception e = defaultErrorDecoder.decode(methodKey, response);
        if(response.status() == 503 || e instanceof NoHttpResponseException) {
            throw new RetryableException(
                    response.status(),
                    response.reason(),
                    response.request().httpMethod(),
                    null,
                    response.request()
            );
        }
        return e;
    }
}

FeignClient configuration 설정

Feign 클라이언트의 configuration 설정에 FeignRetryConfiguration, RetryableExceptionErrorDecoder 클래스를 추가한다.

@FeignClient(name = "storeApi", url = "${api.service.store.url}", configuration = {FeignRetryConfiguration.class, RetryableExceptionErrorDecoder.class})
public interface StoreApiClient {
  ...
}

Feign 클라이언트에서 적용할 Configuration class 에 @Configuration 을 붙이고, @SpringBootApplication 또는 @ComponentScan 에서 탐색 가능한 경로에 있다면 모든 Feign 클라이언트에 적용된다.

클라이언트별로 적용되어야 할 경우 @Configuration 을 제거하고 @FeignClient 의 configuration 속성으로 명시할 수 있다. 특정 클라이언트의 독립적인 설정이 되는 만큼 설정한 클라이언트 수 만큼의 중복된 Bean 이 생성된다.

테스트

아래의 케이스를 검증해보자.

• 재시도 정책에 적용한 100 ms 간격으로 5번의 재시도를 수행하는가?

  @Test
  @DisplayName("서버 응답이 없습니다.")
  void feignClientRetry() { stubFor(get(urlEqualTo("/store")).willReturn(aResponse().withFault(Fault.EMPTY_RESPONSE)));
    assertThrows(FeignException.class, () -> storeApiClient.getStore());
    verify(5, getRequestedFor(urlEqualTo("/store")));
  }

  재시도 로직이 수행되는 로그를 확인한다.

• 재시도 중 정상 응답을 받을 경우 Exception 반환 없이 재시도를 중단하는가?

    @Test
    @DisplayName("재시도 중 store-api 가 통신에 성공하면 응답을 반환합니다.")
    void success() {
        // given
        stubFor(get(urlEqualTo("/store"))
                .inScenario("Retry Scenario")
                .whenScenarioStateIs(STARTED)
                .willReturn(aResponse().withFault(Fault.EMPTY_RESPONSE))
                .willSetStateTo("Attempt 1 Failed"));
  
        stubFor(get(urlEqualTo("/store"))
                .inScenario("Retry Scenario")
                .whenScenarioStateIs("Attempt 1 Failed")
                .willReturn(aResponse().withFault(Fault.EMPTY_RESPONSE))
                .willSetStateTo("Attempt 2 Failed"));
  
        // 세 번째 시도 시 성공하는 스텁 설정
        stubFor(get(urlEqualTo("/store"))
                .inScenario("Retry Scenario")
                .whenScenarioStateIs("Attempt 2 Failed")
                .willReturn(aResponse()
                        .withHeader("Content-Type", "application/json")
                        .withStatus(HttpStatus.OK.value())
                        .withBody(new Store())));
  
        // when
        Store store = storeApiClient.getStore();
  
        // then
        assertThat(store).isNotNull();
        verify(3, getRequestedFor(urlEqualTo("/store")));
    }

  3번의 재시도를 수행한 로그를 확인하고 정상 응답을 받아 검증에 통과함을 확인한다.

FeignClient의 retryer를 설정하여 요청을 여러 번 재시도하는 것은 일시적인 네트워크 문제나 서버 상태에 따른 오류를 해결하는 데 유용할 수 있지만, 재시도가 항상 최선의 선택은 아니다. 근본 원인을 분석하고 백오프 전략이나 서킷 브레이커 패턴과 같은 추가적인 방법도 고려할 수 있다.

참고

https://docs.spring.io/spring-cloud-openfeign/docs/current/reference/html/

*출처 - * https://school.programmers.co.kr/learn/courses/30/lessons/142086

문제

문자열 s가 주어졌을 때, s의 각 위치마다 자신보다 앞에 나왔으면서, 자신과 가장 가까운 곳에 있는 같은 글자가 어디 있는지 알고 싶습니다. 예를 들어, s="banana"라고 할 때, 각 글자들을 왼쪽부터 오른쪽으로 읽어 나가면서 다음과 같이 진행할 수 있습니다.

b는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다. a는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다. n은 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다. a는 자신보다 두 칸 앞에 a가 있습니다. 이는 2로 표현합니다. n도 자신보다 두 칸 앞에 n이 있습니다. 이는 2로 표현합니다. a는 자신보다 두 칸, 네 칸 앞에 a가 있습니다. 이 중 가까운 것은 두 칸 앞이고, 이는 2로 표현합니다. 따라서 최종 결과물은 [-1, -1, -1, 2, 2, 2]가 됩니다.

문자열 s 가 주어질 때, 위와 같이 정의된 연산을 수행하는 함수 solution을 완성해주세요.

제한사항

• 1 ≤ s의 길이 ≤ 10,000
• s은 영어 소문자로만 이루어져 있습니다.

  입출력 예

  s	result
  banana	[-1, -1, -1, 2, 2, 2]
  foobar	[-1, -1, 1, -1, -1, -1]
  ### 풀이
  맨 처음에는 s문자열에서 현재 위치한 문자의 이전 존재여부를 확인하고, 존재하는 만큼의 개수를 리턴하는 것으로 파악했다. (문제를 잘 읽자..)
  문제를 잘 읽어보면 a는 자신보다 두 칸 앞에 a가 있습니다. 이는 2로 표현합니다. 라고 되어 있다.
  자신이 위치한 곳에서, 앞에 얼마만큼의 위치에 같은 문자가 존재하는지 차수를 리턴해야 한다.

  전달 받은 s를 char 타입의 배열로 변환하고 ( = stringToChar 배열), 그 배열을 돌며 HashMap( = splitCheck)에 담는다. (key = 현재 문자, value = 현재 문자의 인덱스 값) 이 때 HashMap에 담기 전에 해당 문자가 HashMap에 이미 담겨 있는지 확인하고,

• 존재한다면 * 해당 문자의 인덱스에서 HashMap 내 현재 문자와 같은 key의 value값(이전 인덱스 값)를 빼준 숫자를 answer에 넣고,
• 존재하지 않다면* -1를 담는다.

import java.util.*;

class Solution {
    public int[] solution(String s) {
        int[] answer = new int[s.length()];
        char[] stringToChar = s.toCharArray();

        HashMap<Character, Integer> splitCheck = new HashMap<>();

        for (int i = 0; i < stringToChar.length; i++) {
            if (splitCheck.containsKey(stringToChar[i])) {
                answer[i] = i - splitCheck.get(stringToChar[i]);
            } else {
                answer[i] = -1;
            }
            splitCheck.put(stringToChar[i], i);
        }

        return answer;
    }
}

*출처 - *https://leetcode.com/problems/island-perimeter/

문제

row x col로 된 grid가 주어진다. grid[i][j]가 1이라면 땅, 0은 물을 나타낸다. 한 칸은 가로/세로로 연결되고 대각선으로 이동할 수 없다. grid에는 완전히 물로 둘러싸여 있고 하나의 섬(연결된 하나 이상의 육지 -> grid[i][j] == 1)이 있다. grid는 호수가 없다. (육지 내에 뜬금없이 물이 있다던가 하는) 하나의 칸은 한 변의 길이가 1인 정사각형이다. grid는 직사각형이고 너비와 높이는 100을 초과하지 않는다. 섬의 둘레를 출력하라.

입출력 예

Example 1 Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]] Output: 16

Example 2 Input: grid = [[1]] Output: 4

Example 3 Input: grid = [[1,0]] Output: 4

제한사항

• row == grid.length
• col == grid[i].length
• 1 <= row, col <= 100
• grid[i][j] is 0 or 1.
• There is exactly one island in grid. grid 안에 정확한 하나의 섬이 있다.

풀이

BFS와 DFS에 많이 약하다고 느껴져서 이번만큼은 풀이를 보지 않고 풀어보기로 결심했다.

문제를 처음 보고 육지(1)와 인접한 변이 아닌 나머지 변의 수를 어떻게 구할지부터 머리가 아파왔다.. 어떤 grid가 들어오든 정확히 계산될 수 있게 하려면 육지를 기준으로 할 지, 물을 기준으로 할 지, 기준을 잡는다면 어떻게 계산할지 노트로 주구장창 그려보며 고민했다.

1. x, y좌표가 상하좌우로 이동할 수 있는 거리를 계산할 int[][] move를 전역으로 선언한다.
2. grid의 한 칸씩 반복하며 값이 1인(육지) 칸의 x값와 j값을 찾고 bfs()메서드로 보낸다. 값이 0인(물) 칸은 계산하지 않는다.
3. bfs메서드는 grid와 x값(i), y값(j)을 전달받는다.
4. x값(i), y값(j)으로 Position 객체를 생성한다.
5. move 길이만큼 반복하며 현재 위치에서 상, 하, 좌, 우로 이동했을 시 의 nowX, nowY를 두고 grid[nowX][nowY]가 유효한 위치인지(따로 boolean체크로 뺐다.), 그 위치가 몇 개의 육지와 인접해있는지 확인한다.
6. 인접한 육지의 개수를 카운트(cnt)한다.
7. 계산할 변의 개수를 구하기 위해 4 - cnt해주었다. (4개의 변에서 육지와 붙어 있는 변의 개수를 빼준다.)
8. return된 수를 더하고 출력한다.

class Solution {
    static int[][] move = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; // 상하좌우
    public int islandPerimeter(int[][] grid) {
        int sideLength = 0;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    sideLength += bfs(grid, i, j);
                }
            }
        }

        return sideLength;
    }

    private static int bfs(int[][] grid, int xValue, int yValue) {
        int cnt = 0;
        Position position = new Position(xValue, yValue);
        int x = position.x;
        int y = position.y;

        for (int i = 0; i < move.length; i++) {
            int nowX = x + move[i][0];
            int nowY = y + move[i][1];

            if (chk(nowX, nowY, grid.length, grid[0].length) && (grid[nowX][nowY] == 1)) cnt++;
        }

        return 4 - cnt;
    }

    private static boolean chk(int x, int y, int x_length, int y_length) {
        if (x < 0 || y < 0 || x >= x_length || y >= y_length) return false;
        else return true;
    }
}

class Position {
    int x;
    int y;

    Position(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

결과

맨날 머리 싸매던 BFS를 혼자 풀어보고 통과했다는 것에 감격한 새벽이었다.. ✨

*출처 - * https://school.programmers.co.kr/learn/courses/30/lessons/43165

문제

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

풀이

DFS 문제를 잘 파악할 수 있는 문제 중 하나라고 생각한다. 0부터 시작해서 index가 numbers의 길이까지 덧셈을 지속하고, index가 numbers 끝까지 간다면 더한 합계(sum)와 타켓한 숫자와 같은지 확인한다. 같으면 answer++, 같지 않다면 덧셈하는 dfs문을 빠져나온 후 뺄셈을 진행하는 dfs로 내려가 계산한다. return;을 만날 경우 현재 index단계에서 한단계 전으로 돌아가 뺄셈(또는 덧셈)을 진행하는 것.

class Solution {
    static int answer;
    public int solution(int[] numbers, int target) {
        answer = 0;
        dfs(0, 0, numbers, target);
        return answer;
    }

    void dfs(int sum, int idx, int[] numbers, int target) {
        if(idx == numbers.length) {
            if(sum == target) {
                answer++;
            }
            return;
        }
        dfs(sum + numbers[idx], idx+1, numbers, target);
        dfs(sum - numbers[idx], idx+1, numbers, target);
    }
}

어려운 DFS 😣

출처 - https://leetcode.com/problems/longest-palindrome/

문제

소문자 또는 대문자로 구성된 문자열 s가 있다. 해당 문자로 만들 수 있는 가장 긴 회문의 길이를 반환한다.

입력 예

Example 1 Input: s = "abccccdd" Output: 7 -> 만들 수 있는 가장 긴 회문은 dccaccd로, 길이는 7이다.

Example 2 Input: s = "a" Output: 1 -> 만들 수 있는 가장 긴 회문은 a로, 길이는 1이다.

제한사항

• 1 <= s.length <= 2000
• s는 영문 대소문자로만 구성된다.

풀이

1. 문자열 내의 문자들을 HashMap에 담고 value로 카운트한다.
2. *문자의 개수가 짝수일 경우: * 양쪽으로 나누어 붙일 수 있다. (ex- a의 개수가 4이면, aa__aa 처럼 회문이 되도록 한다.) 따라서 개수 그대로 answer에 더해준다.
3. *문자의 개수가 홀수일 경우: * boolean 플래그를 두고, 플래그가 false일 경우 answer에 개수를 더해준 후 플래그를 true로 바꿔준다. (ex- b의 개수가 5이면, bbbbb처럼 중간을 기준으로 회문이 되도록 한다.)
4. 이후에 문자 개수가 홀수가 나온다면, 개수에서 -1해준 값을 answer에 더해준다. 최대한 긴 회문이 나오기 위해!

class Solution {
    public int longestPalindrome(String s) {
        int answer = 0;
        HashMap<String, Integer> hm = new HashMap<>();
        boolean odd = false;
        for (String str : s.split("")) {
            hm.put(str, hm.getOrDefault(str, 0) + 1);
        }

        for (String str : hm.keySet()) {
            if (hm.get(str) % 2 == 0) {
                answer += hm.get(str);
            } else {
                if (odd == true) {
                    if(hm.get(str) > 1) answer += hm.get(str) - 1;
                } else {
                    answer += hm.get(str);
                    odd = true;
                }
            }
        }
        return answer;
    }
}

결과

출처 - https://leetcode.com/problems/isomorphic-strings/

문제

두 개의 문자열 s와 t가 동형인지 확인하는 문제이다. (s의 문자를 t로 대체할 수 있는 경우)

입력 예

Example 1 Input: s = "egg", t = "add" Output: true Example 2 Input: s = "foo", t = "bar" Output: false Example 3 Input: s = "paper", t = "title" Output: true

제한사항

• 1 <= s.length <= 5 * 104
• t.length == s.length
• s와 t는 유효한 아스키 문자로 구성된다.

풀이

s의 문자들과 t의 문자들을 순차적으로 Array에 담고 문자에 해당하는 index를 StringBuilder로 붙여주었다. 최종 s의 숫자순서와 t의 숫자순서가 같을 경우 동형이므로 true를 반환하고, 아닐 경우 false를 반환했다. 처음엔 그냥 숫자로 붙이다가 25 21 0과 25 2 10 처럼 숫자는 다르지만 붙였을 때 구분할 수 없는 경우를 확인하고 숫자 끝에 ,를 붙여 구분지었다.

class Solution {
    public boolean isIsomorphic(String s, String t) {
        List<String> srr = new ArrayList<>();
        List<String> trr = new ArrayList<>();

        StringBuilder sbS = new StringBuilder();
        StringBuilder sbT = new StringBuilder();

        for (String sword : s.split("")) {
            if (!srr.contains(sword)) srr.add(sword);
            sbS.append(srr.indexOf(sword)).append(",");

        }
        for (String tword : t.split("")) {
            if(!trr.contains(tword)) trr.add(tword);
            sbT.append(trr.indexOf(tword)).append(",");

        }

        if(sbS.toString().equals(sbT.toString())) return true;
        else return false;
    }
}

결과

혼자 생각한 대로 풀었더니, 통과는 되었지만 시간이 다소 걸린다. 소요시간을 조금 더 줄일 수 있는 방법이 무엇인지 다른 풀이를 찾아보았다.

다른 풀이

class Solution {
    public boolean isIsomorphic(String s, String t) {
        char[] srr = s.toCharArray();
        char[] trr = t.toCharArray();

        // 문자열 길이가 다른 경우 false
        if(srr.length != trr.length) return false;

        char[] sChar = new char[256];
        char[] tChar = new char[256];

        // 아스키코드에 해당하는 index에 문자 저장
        for (int i = 0; i < s.length(); i++) {
            char sc = srr[i];
            char tc = trr[i];

            if (sChar[sc] == 0 && tChar[tc] == 0) {
                sChar[sc] = tc;
                tChar[tc] = sc;
            } else {
                // 서로 대응되는 문자가 다를 경우 false
                if (sChar[sc] != tc || tChar[tc] != sc) {
                    return false;
                }
            }
        }
    }
    return true;
}

문자열 길이만큼 한번만 반복하면서 동시에 문자가 같은지에 대한 여부도 판단하니 훨씬 빠르다. 아스키코드에 대한 제한사항이 들어간 이유가 있구나.. 싶었던 풀이 👏

AWS

Amazon Web Service

아마존에서 제공하는 클라우드 서비스로, 서버와 네트워크 등의 인프라를 빌려 사용할 수 있고 사용한 시간 만큼만 비용을 지불한다.

서비스를 배포하기 위한 서버를 두는 방식으로 크게 On-premise, Cloud Computing 이 있다. On-premise는 자체적으로 서버를 두고 운용하는 방식이고 Cloud Computing은 IT리소스를 인터넷을 통해 온디맨드로 제공하고, 사용한 만큼 비용을 지불한다. (ex- AWS, Google Cloud, Azure, 네이버 클라우드 플랫폼 등)

온디맨드 수요에 따라서 제품 또는 서비스를 제공한다. 소비자의 요구사항에 따라 즉시 제공, 공급하는 주문형 방식.

AWS를 왜 쓸까?

제공하는 서비스의 규모가 점점 커져 사용자가 늘어나면 그만큼의 트래픽을 수용 가능한 확장이 필요하다. On-premise방식으로 직접 서버를 구입하고 설치할 경우 직접 관리가 가능하고 보안도 상대적으로 높지만, 늘어난 만큼 자원의 낭비가 발생할 가능성이 높고 비용과 시간이 많이 소모된다.

Cloud Computing방식은 필요한 만큼의 자원을 늘리거나 줄일 수 있는 유연성이 높다. 특히 AWS의 AWS Auto Scaling은 Scale In/Out 기능을 정책에 따라 조정해주는 서비스를 제공한다. 또 사전에 사용량을 예상하고 미리 지불하거나 장기적으로 약정하지 않고 사용한 만큼 비용을 지불하기 때문에 상대적으로 비용이 저렴하다. 인터넷 접속이 가능하다면 서버에 대한 관리도 즉각 처리하고 몇 분만에 전 세계에 배포가 가능해 속도 측면에서도 뛰어나다. 하나의 예로 NETFLIX는 MSA로 전환하며 모든 도메인을 각각 다른 서버로 나누기 위해 클라우드를 선택해 유연성을 확보했다.

On-premise와 Cloud Computing 중 제공하는 서비스의 구조에 따라 어느 방식이 더 나을지 판단해서 적합한 것을 선택해야 할 것이다.

AWS VPC (Virtual Private Cloud)

• 사용자가 정의한 가상 네트워크 서비스로, 구성 요소를 이용해서 원하는 형태의 네트워크망을 구축할 수 있다.

• 울타리 안에 우리의 서버를 가두고, 설정한 인터넷 게이트웨이를 통해 통신 (대문 역할)
  VPC별로 네트워크를 구성하고 각각의 VPC에 따라 다르게 네트워크를 설정할 수 있다. 이 때 각각의 VPC는 완전히 독립된 네트워크처럼 작동한다.

[VPC 내의 용어]

• subnet : VPC를 특정 범위로 나눈 범위
• public subnet : 인터넷 게이트웨이를 통해서 직접 연결이 가능한 구역 (인터넷 연결 O)
• private subnet : 인터넷과 연결되어 있지 않은 구역
• Route Table : 목적지의 위치가 정의된 집합 테이블. 네트워크 요청에 맞는 목적지에 도달하도록 방향을 맞춰주는 이정표 역할을 한다.
• Internet Gateway : VPC와 인터넷을 연결해주는 문
• NAT Gateway : 네트워크 주소 변환을 통해서 private subnet에 인터넷 통신을 연결하는 게이트웨이로 public subnet 상에서 동작
• VPC endpoint : NAT, Internet Gateway 등을 통하지 않고 AWS의 서비스를 비공개로 연결이 가능하게 하는 서비스

  AWS API Gateway

  서버의 대문과 같은 역할로, 규모에 관계없이 API를 생성, 게시, 유지, 모니터링 및 보호하기 위한 서비스. 여러 서버와의 통신 전에 마주치는 하나의 입구와 같기 때문에 로깅, 액세스 제어, 모니터링, 트래픽 관리, CORS 지원, 인증 등의 통일된 설정이 가능하다.

API Gateway는 자신만의 주소를 설정하고 내에 여러 경로를 설정할 수 있다. 이 경로별로 어떤 API 서버와 연결할 지 결정한다.

예를 들어 API가 특정 서버와 통신할 수 있게 코드가 짜여져 있다고 가정해보면 아래와 같을 것이다.

이 때, 만약 animal.com 서버가 없어졌다거나 animal.com이 fruit.com에 통합된다면 animal.com으로 짜여진 모든 코드들을 수정해야 하는 일이 발생한다.

이 때 이러한 비용을 줄여줄 수 있는 것이 API Gateway 이다. API Gateway를 추가해 주소를 설정하고(test.com) API 서버와 통신할 경로를 설정해준다. (fruit.com = apple / animal.com = bear / vegetable.com = carrot 등으로 이름 붙여주기)

이렇게 되면 중간에 animal.com 서버가 없어지거나 다른 곳과 통합되어 path를 수정해야 할 일이 발생해도 API Gateway에서 경로를 바꾸어 주면 된다. 여기까지가 제일 기본이 되는 구성이고 AWS의 API Gateway 페이지에서 인증, CORS 등의 작업을 추가로 해줄 수 있다.

AWS ELB (Elastic Load Balancing)

다수의 트래픽을 자동으로 분산시켜 안정적인 서버 환경을 운용할 수 있도록 해주는 서비스로, 특정 요청이 왔을 때 요청을 임의로 나누어 여러 대의 EC2인스턴스의 부하를 분산한다.

AWS S3 (Simple Storage Service)

이미지, 동영상 등과 같은 정적 파일들을 용이하게 관리할 수 있는 저장소 느낌의 스토리지 서비스

AWS S3에 파일을 업로드하게 되면, 한 곳에만 업로드 되는 것이 아닌 여러 대의 컴퓨터에 자동 분산되어 동일하게 저장된다. 이 여러 대의 컴퓨터들은 서로 멀리 떨어져 있어, 특정한 한 대가 죽어도 업로드 된 파일은 안전하다. 데이터의 손실이 발생해도 자동으로 복원할 수 있기 때문에 내구성이 높다고 AWS에서는 표현하고 있다. 또한 파일 보관 뿐 아니라 인터넷에 연결되어 있어 어디서든 다운로드 받거나 파일 서버로 사용이 가능하다. 단일 파일당 최소 1바이트 ~ 최대 5TB의 데이터를 저장하고 서비스 할 수 있으며 파일의 저장 개수에는 제한이 없다. 그 외로 버전관리, 데이터 처리, 로그, 쿼리 지원, 호스팅 등의 기능을 제공한다.

[S3 내의 용어]

• 객체 : 저장된 데이터(파일) 하나를 객체로 표현
• 버킷 : 연관된 객체들을 그룹화하여 관리하는 디렉토리. 버킷 단위로 region를 지정할 수 있고 그룹화된 객체들을 대상으로 인증과 접속 제한을 걸 수 있다.

S3에 대해 알아보면서 흥미롭게 느껴졌던 BitTorrent. S3는 BitTorrent 프로토콜을 지원한다. BitTorrent는 파일을 가지고 있는 여러 컴퓨터들로부터 조금씩 파일을 다운받은 후, 이것을 붙여 완전한 파일로 받을 수 있는 시스템이다.

S3는 가용성이 높고 안정적인 파일 호스팅을 제공하지만 비용이 비싸다. 대용량 파일을 S3에 배포해야 할 경우 비용이 많이 들 수 있어 BitTorrent 프로토콜을 사용해 배포할 경우 비용을 크게 절감할 수 있다.

배포할 버킷에 파일을 업로드하고, 업로드 된 파일을 선택해서 나오는 페이지 하단의 객체 URL을 브라우저에 붙여넣은 후 끝에 ?torrent를 추가한다. 이렇게 해서 다운로드 된 파일을 BitTorrent클라이언트를 사용해 다운로드 할 수 있다.

AWS Cloud Front

AWS 내의 캐시 서버라고 볼 수 있다. AWS Edge Location을 사용해서 CDN서비스를 제공한다.

웹 브라우저(클라이언트)에서 서버로 요청이 전송되면 서버는 프로그래밍 언어를 통해 HTML코드를 생성하고 응답한다. 서버는 요청이 들어올 때 마다 응답을 위해 처리하는 과정을 거치는데, 만약 웹 페이지 중 자주 변경되지 않는 페이지가 있다면 해당 페이지에 사용자 요청이 자주 들어올 때마다의 앞전과 같은 처리 과정은 꽤나 비효율적일 것이다. (그에 따른 시간과 비용은 덤..)

AWS Cloud Front는 이러한 비효율적인 과정을 개선해준다. 서버가 들어온 요청에 대한 컨텐츠를 클라이언트에게 전송하면 Cloud Front는 응답 컨텐츠를 캐시에 저장해 갖고 있는다. 이후에 같은 요청이 들어온다면 서버까지 가지 않아도 Cloud Front에서 캐시에 저장되어 있던 html컨텐츠를 응답처리한다. 이로 인해 더 많은 요청을 처리할 수 있고 속도도 매우 빨라진다.

S3와 Cloud Front를 같이 쓰는 이유 클라이언트가 S3의 객체를 가져오려면 S3를 방문해야 하는데.. S3는 사용요금이 꽤 세다. 만약 페이지의 데이터(이미지 등)가 거의 변경되지 않는 데이터라면 Cloud Front를 활용해서 데이터를 캐시에 저장해두고 사용하는 것이 훨씬 비용을 절약할 수 있다.

Cloud Front는 기본 설정으로 CDN(Content Delivery Network)이 켜져 있다. CDN 서비스로 전세계 어디에 있든 빠르게 접속할 수 있다.

AWS Secret Manager

민감한 DB 정보, 보안 인증 정보, API 키 등의 보안 정보를 안전하게 암호화하고 중앙 집중식으로 감사할 수 있도록 도와주는 서비스

AWS Secret Manager는 기존의 애플리케이션 환경설정 파일 내에 하드코딩해서 관리하는 방식을 보완한다. 외부로 유출되어야 하지 않고 소수의 인원만 알고 있어야 하는 비밀 값들을 Secret Manager에 저장해두고 애플리케이션에서 AWS의 API를 호출해 받아가는 방식이다. 한 곳에서 보안성 높게 집중적으로 관리한다고 생각하면 되겠다.

이렇게 되면 보안되어야 하는 민감한 정보가 더이상 코드에 존재하지 않아 정보의 손상을 막는다. 사용자는 지정한 일정에 따라 Secret Manager가 자동으로 보안 정보를 교체하도록 구성할 수 있다.

게임개발자인 "죠르디"는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다. "죠르디"는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다. 게임 화면은 "1 x 1" 크기의 칸들로 이루어진 "N x N" 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 "5 x 5" 크기의 예시입니다). 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 모든 인형은 "1 x 1" 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다. 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓이게 되는 데, 이때 바구니의 가장 아래 칸부터 인형이 순서대로 쌓이게 됩니다. 만약 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 터뜨려지면서 바구니에서 사라지게 됩니다. 크레인 작동 시 인형이 집어지지 않는 경우는 없으나 만약 인형이 없는 곳에서 크레인을 작동시키는 경우에는 아무런 일도 일어나지 않습니다. 또한 바구니는 모든 인형이 들어갈 수 있을 만큼 충분히 크다고 가정합니다.

게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 moves가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• board 배열은 2차원 배열로 크기는 "5 x 5" 이상 "30 x 30" 이하입니다.
• board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다. ▪ 0은 빈 칸을 나타냅니다. ▪ 1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다.
• moves 배열의 크기는 1 이상 1,000 이하입니다.
• moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.

입출력 예

풀이

• 아래부터 차곡차곡 쌓이고 맨 위의 인형이 잡혀나가니 Stack을 활용하자.
• 0은 인형이 없다는 표시니까 stack에 넣을 때 아예 걸러버리자.
• boardStack - 인형들이 들어있는 칸
• basket - 뽑은 인형을 쌓을 바구니
• stack에는 board의 각 배열의 0번째 수, 1번째 수, ... , N번째 수를 모아 쌓는다고 보면 되겠다.
• moves를 돌며

1. basket이 비어 있으면 → 뽑은 인형이 같은지 확인할 필요가 없기 때문에 그대로 push
2. basket이 비어 있지 않으면 → 뽑은 인형(boardStack의 칸의 제일 위에 있는 숫자)이 basket의 맨 위에 있는 인형과 같은지 확인 → 같으면 basket에 넣지 않고 pop 하고 answer+=2 / 같지 않다면 push
3. 뽑은 인형 위치(boardStack.get(m)) pop

결과

public int solution(int[][] board, int[] moves) {
        int answer = 0;
        ArrayList<Stack<Integer>> boardStack = new ArrayList<>();
        Stack<Integer> basket = new Stack<>();

        for (int j = 0; j < board.length; j++) {
            Stack<Integer> stack = new Stack<>();
            for (int i = board.length - 1; i >= 0; i--) {
                if(board[i][j] != 0) stack.add(board[i][j]);
            }
            boardStack.add(j, stack);
        }

        for (int m : moves) {
            m = m - 1;
            if (!boardStack.get(m).isEmpty()) {
                int top = boardStack.get(m).peek();
                if (!basket.isEmpty()) {
                    if (basket.peek() == top) {
                        basket.pop();
                        answer += 2;
                    } else basket.push(top);
                } else basket.push(top);
                boardStack.get(m).pop();
            }
        }
        return answer;
    }

정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers의 길이는 2 이상 100 이하입니다.

• numbers의 모든 수는 0 이상 100 이하입니다.

  입출력 예

  numbers	result
  [2,1,3,4,1]	[2,3,4,5,6,7]
  [5,0,2,7]	[2,5,7,9,12]
  ### 입출력 예 설명

• 입출력 예 #1 2 = 1 + 1 입니다. (1이 numbers에 두 개 있습니다.) 3 = 2 + 1 입니다. 4 = 1 + 3 입니다. 5 = 1 + 4 = 2 + 3 입니다. 6 = 2 + 4 입니다. 7 = 3 + 4 입니다. 따라서 [2,3,4,5,6,7] 을 return 해야 합니다.

• 입출력 예 #2 2 = 0 + 2 입니다. 5 = 5 + 0 입니다. 7 = 0 + 7 = 5 + 2 입니다. 9 = 2 + 7 입니다. 12 = 5 + 7 입니다. 따라서 [2,5,7,9,12] 를 return 해야 합니다.

풀이

• HashSet에 서로 다른 인덱스의 값을 더한 수를 담는다.
• HashSet을 List로 변환하고 오름차순 정렬 해준다.

결과

public int[] solution(int[] numbers) {
        int[] answer = {};
        HashSet<Integer> set = new HashSet<>();
        ArrayList<Integer> list = new ArrayList();

        for (int i = 0; i < numbers.length-1; i++) {
            for (int j = i+1; j < numbers.length; j++) {
                set.add(numbers[i] + numbers[j]);
            }
        }
        for (int i : set) {
            list.add(i);
        }
        Collections.sort(list);
        answer = new int[list.size()];
        for (int j = 0; j < answer.length; j++) {
            answer[j] = list.get(j);
        }
        return answer;
    }

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

스마트폰 전화 키패드의 각 칸에 다음과 같이 숫자들이 적혀 있습니다. 이 전화 키패드에서 왼손과 오른손의 엄지손가락만을 이용해서 숫자만을 입력하려고 합니다. 맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 시작하며, 엄지손가락을 사용하는 규칙은 다음과 같습니다.

1. 엄지손가락은 상하좌우 4가지 방향으로만 이동할 수 있으며 키패드 이동 한 칸은 거리로 1에 해당합니다.
2. 왼쪽 열의 3개의 숫자 1, 4, 7을 입력할 때는 왼손 엄지손가락을 사용합니다.
3. 오른쪽 열의 3개의 숫자 3, 6, 9를 입력할 때는 오른손 엄지손가락을 사용합니다.
4. 가운데 열의 4개의 숫자 2, 5, 8, 0을 입력할 때는 두 엄지손가락의 현재 키패드의 위치에서 더 가까운 엄지손가락을 사용합니다. 4-1. 만약 두 엄지손가락의 거리가 같다면, 오른손잡이는 오른손 엄지손가락, 왼손잡이는 왼손 엄지손가락을 사용합니다.

순서대로 누를 번호가 담긴 배열 numbers, 왼손잡이인지 오른손잡이인 지를 나타내는 문자열 hand가 매개변수로 주어질 때, 각 번호를 누른 엄지손가락이 왼손인 지 오른손인 지를 나타내는 연속된 문자열 형태로 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers 배열의 크기는 1 이상 1,000 이하입니다.
• numbers 배열 원소의 값은 0 이상 9 이하인 정수입니다.
• hand는 "left" 또는 "right" 입니다. ▪ "left"는 왼손잡이, "right"는 오른손잡이를 의미합니다.
• 왼손 엄지손가락을 사용한 경우는 L, 오른손 엄지손가락을 사용한 경우는 R을 순서대로 이어붙여 문자열 형태로 return 해주세요.

입출력 예

풀이

• 1~0까지의 키패드 숫자를 좌표에 담는다. (*은 10, #은 12)
• 각 엄지손가락이 누른 위치를 leftIndex, rightIndex에 각각 저장한다.
• 숫자가 2, 5, 8, 0일 경우, 해당 숫자와 leftIndex, rightIndex의 거리를 계산한다. 한 칸당 거리가 1이므로 해당 x좌표 거리((해당 숫자 - index) / 3의 절댓값) , y좌표 거리((해당 숫자 - index) % 3의 절댓값)를 더해 더 가까운 거리를 판단한다.

결과

public String solution(int[] numbers, String hand) {
        String answer = "";
        StringBuilder sb = new StringBuilder(answer);
        int left = 10;
        int right = 12;

        for (int i : numbers) {
            if ((i == 1) || (i == 4) || (i == 7)) {
                sb.append("L");
                left = i;
            } else if ((i == 3) || (i == 6) || (i == 9)) {
                sb.append("R");
                right = i;
            } else {
                if(i == 0) i = 11;

                int lDistance = (Math.abs(i - left) / 3) + (Math.abs(i - left) % 3);
                int rDistance = (Math.abs(i - right) / 3) + (Math.abs(i - right) % 3);

                if (lDistance == rDistance) {
                    if ("right".equals(hand)) {
                        sb.append("R");
                        right = i;
                    } else {
                        sb.append("L");
                        left = i;
                    }
                } else if (lDistance > rDistance) {
                    sb.append("R");
                    right = i;
                } else {
                    sb.append("L");
                    left = i;
                }

            }
        }
        answer = sb.toString();
        return answer;
    }

출처 -https://school.programmers.co.kr/learn/courses/30/lessons/67256

카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 가입하는 유저들이 카카오 아이디 규칙에 맞지 않는 아이디를 입력했을 때, 입력된 아이디와 유사하면서 규칙에 맞는 아이디를 추천해주는 프로그램을 개발하는 것입니다.

다음은 카카오 아이디의 규칙입니다.

• 아이디의 길이는 3자 이상 15자 이하여야 합니다.
• 아이디는 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.) 문자만 사용할 수 있습니다.
• 단, 마침표(.)는 처음과 끝에 사용할 수 없으며 또한 연속으로 사용할 수 없습니다.

"네오"는 다음과 같이 7단계의 순차적인 처리 과정을 통해 신규 유저가 입력한 아이디가 카카오 아이디 규칙에 맞는 지 검사하고 규칙에 맞지 않은 경우 규칙에 맞는 새로운 아이디를 추천해 주려고 합니다.

신규 유저가 입력한 아이디가 newid 라고 한다면,

1단계 : newid 모든 대문자를 대응되는 소문자로 치환합니다. 2단계 : newid에서 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)를 제외한 모든 문자를 제거합니다. 3단계 : newid에서 마침표(.)가 2번 이상 연속된 부분을 하나의 마침표(.)로 치환합니다. 4단계 : newid에서 마침표(.)가 처음이나 끝에 위치한다면 제거합니다. 5단계 : newid가 빈 문자열이라면, new_id에 "a"를 대입합니다. 6단계 : newid의 길이가 16자 이상이면, newid의 첫 15개의 문자를 제외한 나머지 문자들을 모두 제거합니다. 만약 제거 후 마침표(.)가 newid의 끝에 위치한다면 끝에 위치한 마침표(.) 문자를 제거합니다. 7단계 : newid의 길이가 2자 이하라면, newid의 마지막 문자를 newid의 길이가 3이 될 때까지 반복해서 끝에 붙입니다.

신규 유저가 입력한 아이디를 나타내는 new_id가 매개변수로 주어질 때, "네오"가 설계한 7단계의 처리 과정을 거친 후의 추천 아이디를 return 하도록 solution 함수를 완성해 주세요.

제한사항

• new_id는 길이 1 이상 1,000 이하인 문자열입니다.
• new_id는 알파벳 대문자, 알파벳 소문자, 숫자, 특수문자로 구성되어 있습니다.
• new_id에 나타날 수 있는 특수문자는 -_.~!@#$%^&*()=+[{]}:?,<>/ 로 한정됩니다.

입출력 예

처리 과정을 단계별로 제공해줘서 설명에 맞게 짜기만 하면 되었기 때문에 크게 어렵지 않게 재밌게 풀 수 있었다. 뭔가 하나의 기능을 만드는 느낌의 문제!

결과

public String solution(String new_id) {
        String answer = "";
        answer = seven(six(five(four(three(two(one(new_id)))))));
        return answer;
    }

    // 1단계
    static String one(String id) {
        for (char s : id.toCharArray()) {
            if(s >= 65 && s <= 90) id = id.replace(s, (char) (s + 32));
        }
        return id;
    }

    // 2단계
    static String two(String id) {
        for (char s : id.toCharArray()) {
            if(!(s >= 97 && s <= 122)
                    && !(s >= 48 && s <= 57)
                    && s != 45
                    && s != 46
                    && s != 95) {
                id = id.replace(String.valueOf(s), "");
            }
        }
        return id;
    }

    // 3단계
    static String three(String id) {
        while (id.contains("..")) {
            id = id.replace("..", ".");
        }
        return id;
    }

    // 4단계
    static String four(String id) {
        if(!id.equals("") && id.charAt(0) == 46) id = id.substring(1, id.length());
        if(!id.equals("") && id.charAt(id.length()-1) == 46) id = id.substring(0, id.length()-1);
        return id;
    }

    // 5단계
    static String five(String id) {
        if(id.equals("")) return "a";
        return id;
    }

    // 6단계
    static String six(String id) {
        if(id.length() >= 16) id = id.substring(0, 15);
        return four(id);
    }

    // 7단계
    static String seven(String id) {
        if(id.length() <= 2) {
            String lastStr = id.substring(id.length() - 1, id.length());
            while(id.length() < 3) {
                id += lastStr;
            }
        }
        return id;
    }

** 출처 - ** https://school.programmers.co.kr/learn/courses/30/lessons/72410

어떤 정수들이 있습니다. 이 정수들의 절댓값을 차례대로 담은 정수 배열 absolutes와 이 정수들의 부호를 차례대로 담은 불리언 배열 signs가 매개변수로 주어집니다. 실제 정수들의 합을 구하여 return 하도록 solution 함수를 완성해주세요.

제한사항

• absolutes의 길이는 1 이상 1,000 이하입니다. ▪ absolutes의 모든 수는 각각 1 이상 1,000 이하입니다.

• signs의 길이는 absolutes의 길이와 같습니다. ▪ signs[i] 가 참이면 absolutes[i] 의 실제 정수가 양수임을, 그렇지 않으면 음수임을 의미합니다.

  입출력 예

  absolutes	signs	result
  [4,7,12]	[true,false,true]	9
  [1,2,3]	[false,false,true]	0
  ### 입출력 예 설명

• 입출력 예 #1 signs가 [true,false,true] 이므로, 실제 수들의 값은 각각 4, -7, 12입니다. 따라서 세 수의 합인 9를 return 해야 합니다.

• 입출력 예 #2 signs가 [false,false,true] 이므로, 실제 수들의 값은 각각 -1, -2, 3입니다. 따라서 세 수의 합인 0을 return 해야 합니다.

결과

public int solution(int[] absolutes, boolean[] signs) {
        int answer = 0;
        for (int i = 0; i < absolutes.length; i++) {
            if (signs[i] == true) answer += absolutes[i];
            else answer += absolutes[i] * -1;
        }
        return answer;
    }

*출처 - * https://school.programmers.co.kr/learn/courses/30/lessons/76501

로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다.

순위	당첨 내용
1	6개 번호가 모두 일치
2	5개 번호가 일치
3	4개 번호가 일치
4	3개 번호가 일치
5	2개 번호가 일치
6 (낙첨)	그 외
로또를 구매한 민우는 당첨 번호 발표일을 학수고대하고 있었습니다. 하지만, 민우의 동생이 로또에 낙서를 하여, 일부 번호를 알아볼 수 없게 되었습니다. 당첨 번호 발표 후, 민우는 자신이 구매했던 로또로 당첨이 가능했던 최고 순위와 최저 순위를 알아보고 싶어졌습니다.
알아볼 수 없는 번호를 0으로 표기하기로 하고, 민우가 구매한 로또 번호 6개가 44, 1, 0, 0, 31 25라고 가정해보겠습니다. 당첨 번호 6개가 31, 10, 45, 1, 6, 19라면, 당첨 가능한 최고 순위와 최저 순위의 한 예는 아래와 같습니다.
- 순서와 상관없이, 구매한 로또에 당첨 번호와 일치하는 번호가 있으면 맞힌 걸로 인정됩니다.
- 알아볼 수 없는 두 개의 번호를 각각 10, 6이라고 가정하면 3등에 당첨될 수 있습니다.
(3등을 만드는 다른 방법들도 존재합니다. 하지만, 2등 이상으로 만드는 것은 불가능합니다.)
- 알아볼 수 없는 두 개의 번호를 각각 11, 7이라고 가정하면 5등에 당첨될 수 있습니다.
(5등을 만드는 다른 방법들도 존재합니다. 하지만, 6등(낙첨)으로 만드는 것은 불가능합니다.)

민우가 구매한 로또 번호를 담은 배열 lottos, 당첨 번호를 담은 배열 win_nums가 매개변수로 주어집니다. 이때, 당첨 가능한 최고 순위와 최저 순위를 차례대로 배열에 담아서 return 하도록 solution 함수를 완성해주세요.

제한사항

• lottos는 길이 6인 정수 배열입니다.
• lottos의 모든 원소는 0 이상 45 이하인 정수입니다.
• 0은 알아볼 수 없는 숫자를 의미합니다.
• 0을 제외한 다른 숫자들은 lottos에 2개 이상 담겨있지 않습니다.
• lottos의 원소들은 정렬되어 있지 않을 수도 있습니다.
• win_nums은 길이 6인 정수 배열입니다.
• win_nums의 모든 원소는 1 이상 45 이하인 정수입니다.
• win_nums에는 같은 숫자가 2개 이상 담겨있지 않습니다.
• win_nums의 원소들은 정렬되어 있지 않을 수도 있습니다.

** 풀이 **

• lottos의 숫자 중 win_nums에 들어 있는 숫자와 같을 경우의 lottoCount
• lottos의 숫자 중 0인 숫자의 zeroCount
• lottos의 0은 특정 번호로 가정할 필요 없이 최고 순위 = 0의 개수(가정한 숫자가 모두 맞았다고 칠 경우) + lottoCount / 최저 순위 = lottoCount
• 만약 zeroCount가 6개면 최고, 최저 순위로 생각했을 때 다 맞거나 or 다 틀리거나 이므로 최고 순위 = 1 / 최저 순위 = 6
• lottos 중 맞은 숫자와 0의 개수까지 더해도 1 이하일 경우 체크하기

결과

import java.util.*;
public int[] solution(int[] lottos, int[] win_nums) {
        int[] answer = {};
        answer = new int[2];
        int zeroCount = 0;
        int lottoCount = 0;

        HashMap<Integer, Integer> lottoMap = new HashMap<>();
        lottoMap.put(6, 1);
        lottoMap.put(5, 2);
        lottoMap.put(4, 3);
        lottoMap.put(3, 4);
        lottoMap.put(2, 5);

        for (int j : lottos) {
            if (j == 0) {
                zeroCount++;
            } else {
                for (int w : win_nums) {
                    if(w == j) lottoCount++;
                }
            }
        }

        if (zeroCount == 6) {
            answer[0] = 1;
            answer[1] = 6;
        } else {
            int max = lottoCount + zeroCount;
            int min = lottoCount;
            if(max <= 1) answer[0] = 6;
            else answer[0] = lottoMap.get(max);
            if(min <= 1) answer[1] = 6;
            else answer[1] = lottoMap.get(min);
        }
        return answer;
    }

** 출처 - ** https://school.programmers.co.kr/learn/courses/30/lessons/77484

두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ left ≤ right ≤ 1,000

  입출력 예

  left	right	result
  13	17	43
  24	27	52
  ### 입출력 예 설명

• 입출력 예 #1 다음 표는 13부터 17까지의 수들의 약수를 모두 나타낸 것입니다.

• 입출력 예 #2 다음 표는 24부터 27까지의 수들의 약수를 모두 나타낸 것입니다.

풀이

• left부터 right까지 반복하면서, 각 숫자의 약수의 개수를 구하고 짝수/홀수를 판단해서 answer에 계산해준다.

결과

public int solution(int left, int right) {
        int answer = 0;
        for (int i = left; i <= right; i++) {
            int sqrt = (int) Math.sqrt(i);
            int count = 0;
            for (int j = 1; j <= sqrt; j++) {
                if (i % j == 0) {
                    count += 2;
                    if (j * j == i) {
                        count--;
                    }
                }
            }
            if (count % 2 == 0) {
                answer += i;
            } else answer -= i;
        }
        return answer;
    }

** 출처 - ** https://school.programmers.co.kr/learn/courses/30/lessons/77884