꼽행착오

Spring Framework 를 사용해 많지는 않은 프로젝트를 진행해 봤는데, 정작 Spring 자체에 대한 공부는 뒷전으로 한 것 같다는 생각이 문득 들었다. 내부적으로 어떻게 동작하는 지 알고 싶어 공부를 하고자 했는데 어떻게 공부를 시작해야 할 지 잘 모르겠어서 일단 책을 구입했다.

공부하기 위한 책으로 스프링 5 레시피 라는 책을 구입했는데, 그 내용에 대해서 앞으로 정리하면서 공부를 진행해 보려 한다.

Spring Core

Spring IoC / POJO

IoC (Inversion of Control ; 제어의 역전) 는 스프링 프레임워크의 심장부라고 할 수 있는데, IoC 컨테이너는 POJO 를 구성하고 관리하는 역할을 수행한다. IoC 는 DI (Dependency Injection ; 의존성 주입) 이라고도 불리는데 객체 간의 의존성이 발생하는 것을 IoC 컨테이너가 관리하는 것이라 이해했다.

일반적으로 객체의 생성과 실행은 다음의 순서를 따른다.

1. 객체 생성
2. 의존성 객체 생성
   클래스 내부에서 생성할 객체의 생성자 호출 등을 통해 직접 생성
3. 의존성 객체의 메소드 호출

하지만 스프링에서는 객체의 생성을 IoC 컨테이너 (Spring 의 BeanFactory, ApplicationContext) 에서 수행하고 생성된 객체를 주입하는 다음과 같은 순서를 따른다.

1. 객체 생성
2. 의존성 객체 주입
   스스로 생성하지 않고, 스프링에서 생성한 객체를 주입받음
3. 의존성 객체의 메소드 호출

이러한 방식으로 객체의 의존성을 주입받는 것을 제어의 역전이라 표현하며, 이를 통해 객체 간의 결합도를 줄이고 유연성을 높인 코드를 작성할 수 있게 해 가독성을 높이고, 코드 중복을 줄이고, 유지보수를 편하게 할 수 있다 한다.

특히, 스프링이 모든 의존성 객체를 실행 시 모두 생성하고 필요한 곳에 주입하는 이와 같은 방식은 각각의 Bean 들이 싱글턴 패턴의 특징을 가지도록 하며 제어의 흐름을 개발자가 갖지 않고 스프링이 맡아 작업을 처리하게 된다.

# Reference.

SNS 시스템을 구축하기 위해서 꼭 필요한 것이, 게시물을 저장하는 것이다. 그 저장소는 RDB 가 될 수도 있고, NoSQL DB 가 될 수도 있고, 분산 파일시스템과 같이 단순 파일로 저장하는 것이 될 수도 있다. 그 중 나는 NoSQL DB 를 사용해 프로젝트를 진행해 보려고 한다.

우선, NoSQL 을 선택하게 된 가장 큰 이유는 개인적으로 NoSQL DB 에 대한 이해가 부족한 것 같아 공부를 할 필요성을 느꼈는데 단순히 이론만 보고 공부하는 것은 직접 사용하면서 배우는 것보다 내용을 익히기에는 빠를 수 있지만 공부하는 것이 금방 지칠 것 같아서이다. 내가 알고 있는 NoSQL 의 특징은 정해진 Schema 가 존재하지 않는다는 것인데, 이러한 특징이 정확히 어떤 것을 의미하는 지 그것으로 인한 장점이 어떤 것이 있는 지를 공부하고 정리하려고 한다.

NoSQL 이란 ?

NoSQL 이란 게 우선 어떤 것일까. MongoDB 사이트에서 설명하기로는, SQL (Structured Query Language) 만을 사용하지 않는 Database 라 한다. 관계형 데이터베이스는 일반적으로 표 형식으로 데이터를 정의한다. 데이터 간의 관계를 통해 데이터를 정의한다고 생각되는데, 이와 달리 NoSQL DB 는 데이터 모델에 따라서 다양한 유형으로 데이터를 정의한다.

NoSQL DB 는 이러한 특징이 있지만, 한 마디로 이를 정리하자면 "관계형 데이터베이스 이외의 형식으로 데이터를 저장하는 데이터베이스" 라고 할 수 있다. 그렇다고 NoSQL 데이터베이스가 관계형 데이터를 저장하지 않는다는 것은 아니다. RDB 의 방식과 다를 뿐이지 저장이 가능하고, 그 저장하는 형태가 단일 데이터 구조에 관련된 여러 데이터를 중첩해서 저장하는 방식이 될 수도 있다. NoSQL 데이터베이스는 저장소에 사용되는 스토리지의 비용이 크게 감소하면서 등장했다고 하는데, 이것의 등장으로 인해 기존처럼 데이터 저장에 있어 중복을 줄이기 위해 데이터 모델을 복잡하고 어렵게 작성할 필요가 줄었다고 한다.

NoSQL 데이터베이스는 개발자가 엄청난 양의 비정형 데이터를 저장할 수 있도록 지원하는데, 이러한 방식이 개발자에게 뛰어난 유연성을 제공하였다 한다. 특히, 애자일 방법론이 인기를 얻으면서 소프트웨어 개발자들이 변화하는 요구사항에 따라 발빠르게 데이터 모델에서 소프트웨어 전반에 이르기까지 반복과 변경을 신속하게 할 수 있는 능력이 필요해졌다 한다. NoSQL 데이터베이스가 바로 이러한 유연성을 제공하는 데이터베이스 구조였다.

# Reference.

https://www.mongodb.com/ko-kr/nosql-explained

Spring Framework 를 조금 더 사용해보고, 개인적으로 공부를 더 해보고 싶어서 Shop and Show 라는 프로젝트를 생각해 봤다. 내가 생각한 Shop and Show 는 일종의 SNS 로, 인별그램이 인기를 얻고 해당 SNS 의 인플루언서들이 상품을 판매(?) 하는 것에서 착안을 해서 생각하게 된 프로젝트다.

프로젝트의 내용은 간단히 설명하자면 다음과 같다. SNS 를 이용하다 보면 어떤 인플루언서가 본인의 마음에 든 상품이나 본인이 운영하고 있는 쇼핑몰에 있는 아이템을 판매하는 것을 많이 보게 된다. SNS 를 이용하는 많은 사용자들이 그것에 관심을 갖고 상품에 대한 구매를 고민하게 되는데 링크를 클릭해 보면 일반적인 쇼핑몰로 이동을 하게 되고 그 곳에서 상품에 대한 구매를 진행하게 된다.

내가 생각한 부분은 SNS 내에서 그러한 상품 관리를 같이 할 수 있으면 어떨까라는 것이었다. 어쨌든 상품을 판매하고 구매하기 위해서 쇼핑몰이 따로 있어야 하고, 이미 그러한 사업을 진행하고 있던 인플루언서가 아니라면 새로 사이트를 구축하는 비용을 필요로 한다. 내가 생각한 프로젝트는 SNS 내에 일종의 쇼핑몰을 구축하고 판매자는 그 쇼핑몰에 상품을 등록하기만 하면 되는, 굳이 사이트를 새로 구축하고 서버 관리를 할 필요가 없는 것이다.

추가적으로, 판매자가 SNS 에 사진을 올리고 그 사진의 태그를 통해 상품으로 바로 연결이 되게 한다던가 상품을 구매한 사람이 리뷰를 따로 달지 않고 SNS 에 게시글을 올림으로써 그 상품에 대한 리뷰를 등록하는 방식을 생각 중이다. 구매한 사람 입장에서는 따로 상품에 대한 리뷰를 남길 필요가 없고, SNS 에서 그 게시물을 보게 되는 사람들은 자신이 관심이 생긴 상품들에 대해 바로 확인할 수 있어 좋을 것 같다.

결국 내가 개발하고자 하는 이 시스템의 장점은, 판매자에게는 특별히 상품 판매를 위해 새로 쇼핑몰 사이트를 구축할 필요가 없어 상품 판매를 위한 허들을 낮출 수 있다는 점과 구매자에게는 일반적으로 사용하는 SNS 를 통해 자연스레 여러 상품들을 접할 수 있고 관심이 있는 상품이 있다면 그것에 대해 바로 구매를 할 수 있다는 점이 있을 것 같다. 이에 더해, 모든 사용자들은 이 시스템을 쇼핑몰 뿐만 아니라 SNS 로 이용하기 때문에 자신이 평소 관심이 있었던 인플루언서나 상품들에 대해 팔로우를 하고 상품에 대한 소식들을 쉽게 받아볼 수 있는 것으로 생각하고 있다.

이 외에 추가적인 정보는, 프로젝트를 진행하며 추가할 점이 생기게 된다면 작성할 예정이다. 이 카테고리에는 프로젝트를 진행하며 있었던 기술적인 이슈나 공부한 내용들, 혹은 프로젝트 자체에 대한 내용들이 작성될 예정이다.

이 문제는 개인적으로 공부를 위해 풀이한 문제이다.

일반적으로 달팽이 수열은, 아래와 같이 숫자가 달팽이 모양으로 증가하는 형태의 수열을 의미한다.

// size = 3
1 2 3
8 9 4
7 6 5

중첩된 달팽이 수열은, 여러 단계(?) 로 중첩된 달팽이 수열을 표현하고자 지은 이름인데 의도를 표현하기 적합한 이름인 지는 모르겠다. 간단하게 설명을 하자면 각 단계 별로 수열의 Size 가 주어지고 수열 안에 중첩된 또다른 수열이 존재하는 방식이다. 이를 위처럼 표현하면 다음과 같을 것 같다.

// size = [3, 2]
 1  2  3 10 11 12 
 8  9  4 17 18 13 
 7  6  5 16 15 14 
28 29 30 19 20 21 
35 36 31 26 27 22 
34 33 32 25 24 23

제일 위에서 size 가 3일 때의 달팽이 수열을 표현했는데, 이러한 달팽이 수열을 내부에 갖는 size 가 2인 달팽이 수열을 표현한 것이다.

이를 그림으로 표현하면 다음과 같을 수 있겠다.

중첩 달팽이 수열의 size 는 배열로 주어지고, 그 배열이 [3, 2] 와 같을 때의 모습은 위와 같다. 우선, (2 x 2) 의 크기를 갖는 달팽이 수열이 존재하게 된다. 총 4개의 수열로 구성된 이 달팽이 수열은, 각각이 (3 x 3) 의 크기를 갖는 달팽이 수열이다. 만약 size 가 [3, 2, 2] 와 같이 주어진다면 이 수열이 의미하는 바는 위의 수열 4개로 구성된 또다른 달팽이 수열이 될 것이다.

우선 이 문제를 해결하기 위해 기본적으로, 달팽이 수열을 만들 수 있어야 하는데 이는 방향 정보를 갖는 변수 하나를 사용함으로써 수열을 표현할 수 있다. 방향의 순서는 오른쪽, 아래, 왼쪽, 위 방향으로 4 가지 방향이 존재하게 되고 이 순서대로 값을 채워나갈 수 있다면 달팽이 수열을 만들 수 있다.

그리고 위와 같이 중첩된 수열을 표현하기 위해 재귀함수를 사용할 수 있는데, 각 단계 별로 전체 수열의 크기가 어떻게 되는 지, 초기 수열에서 현재 표현해야 하는 수열의 위치가 어디인 지 정보를 줌으로써 각 함수 호출 단계에서 현재 표현해야 할 수열의 정보를 알 수 있다.

이와 같이 문제를 풀이했을 때 작성한 코드는 다음과 같다.

#define pow(X) ((X) * (X))

int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};
int N;

void fill(vector<vector<int>>& matrix, int sy, int sx, int ey, int ex, int startNum) {
    int y = sy, x = sx, dir = 0, num = startNum;
    while (true) {
        if (y < sy || y > ey || x < sx || x > ex || matrix[y][x] != 0) {
            break;
        }
        matrix[y][x] = num++;
        int ny = y + dr[dir], nx = x + dc[dir];
        if (ny < sy || ny > ey || nx < sx || nx > ex || matrix[ny][nx] != 0) {
            dir = (dir + 1) % 4;
            ny = y + dr[dir], nx = x + dc[dir];
        }
        y = ny;
        x = nx;
    }
}

void solve(vector<vector<int>>& matrix, vector<int>& lengths, int idx, int sy, int sx, int n, int num) {
    if (idx == 0) {
        fill(matrix, sy, sx, sy + lengths[0] - 1, sx + lengths[0] - 1, num);
        return;
    }
    int length = lengths[idx];
    int offset = n / length;
    vector<vector<bool>> vis(length, vector<bool>(length, false));

    int i = 0, j = 0, dir = 0;
    int y = sy, x = sx;
    int nextNum = num;
    while (true) {
        if (vis[i][j])
            break;
        vis[i][j] = true;

        int ni, nj;
        ni = i + dr[dir];
        nj = j + dc[dir];
        if (ni < 0 || ni >= length || nj < 0 || nj >= length || vis[ni][nj]) {
            dir = (dir + 1) % 4;
            ni = i + dr[dir];
            nj = j + dc[dir];
        }

        solve(matrix, lengths, idx - 1, y, x, offset, nextNum);

        y += dr[dir] * offset;
        x += dc[dir] * offset;
        nextNum += pow(offset);

        i = ni;
        j = nj;
    }
}

vector<vector<int>> solution(vector<int> lengths) {
    N = 1;
    for (auto length : lengths) {
        N *= length;
    }

    vector<vector<int>> matrix(N, vector<int>(N, 0));
    solve(matrix, lengths, lengths.size() - 1, 0, 0, N, 1);
    return matrix;
}

주어진 문제는 위와 같다. 정수형 배열이 주어졌을 때, 배열의 부분 배열 중 Arithmetic Subsequence 를 만족하는 부분 배열의 개수를 찾는 것.

Arithmetic Subsequence 란, 배열 내 인접한 원소들이 모두 동일한 차이값을 갖는 것을 의미하는데 원소가 3개 이상일 때만 이 조건을 만족한다. 예를 들어 [1, 2, 3, 4, 5] 는 인접한 원소의 차가 1 로 모두 동일하므로 조건을 만족하지만 [1, 2, 2, 3, 4] 는 인접한 원소의 차가 동일하지 않아 조건을 만족하지 않는다.

문제의 해결을 위해 DP 알고리즘을 적용했는데 그 방법은 다음과 같다. 배열의 각 인덱스를 탐색하며 현 위치를 기준으로 이전 위치까지 일정한 차를 갖는 Arithmetic Subsequence 가 존재했는 지 확인한 뒤 존재한다면 그 값을 현재 위치에 저장한다. 그리고 만약 이전 위치에 저장된 값이 있는 경우 그 값을 저장한 뒤 추후 반환한다.

예를 들어 설명하자면, [1, 1, 2, 3, 4, 5] 라는 배열이 존재할 때 찾고자 하는 Arithmetic Subsequence 는 [1, 2, 3] (2개), [1, 2, 3, 4] (2개), [1, 2, 3, 4, 5] (2개), [2, 3, 4, 5], [3, 4, 5], [1, 3, 5] (2개) 로 모두 11 개가 존재한다.

위와 같이 각 인덱스의 값이 존재하게 되는데, 현재 인덱스를 i, 이전 인덱스를 j 라고 표현한다.

1) i = 1, j = 0
현재 인덱스보다 이전 인덱스가 항상 존재해야 로직이 동작하므로 i = 0 일 경우는 스킵한다. value[i] 와 value[j] 는 모두 1로 동일하므로 값의 차이가 0이다. 따라서 i 위치에서 0의 차이를 갖는 Subsequence 가 한 개 존재함을 저장한다. 두 개의 원소만 가지고 판단한 것이므로 i 위치에 저장된 값은 정답에 반영하지 않는다.

2) i = 2, j = 0

value[i] 는 2, value[j] 는 1이므로 원소의 차가 1이다. 따라서 i 위치에서 1의 차를 갖는 Subsequence 가 한 개 존재함을 저장한다.

3) i = 2, j = 1

2) 와 마찬가지로 i 위치에 Subsequence 가 한 개 존재함을 저장한다. 2), 3) 의 정보는 각각 개별 정보이므로 i 위치에 1의 차를 갖는 Subsequence 는 두 개 존재하는 것으로 저장된다.

4) i = 3, j = 2

j 가 0, 1 일 때는 생략을 했는데 i 가 3일 때 해당 정보는 정답에 반영되지 않기 때문이다. value[i] 와 value[j] 의 차는 1이고, j 위치에 저장된 subsequence 의 개수는 2개이다. 즉, i 에서 차가 1인 subsequence 의 개수는 2개가 발생한다. i 가 3이 되었을 때, subsequence 의 길이가 비로소 3 이상이 되므로 이를 정답에 반영한다.

이와 같이 현재 위치를 탐색하며 이전 위치들에서 발생한 subsequence 의 개수를 더해 나간다. 현재 위치에서 발생한 개수는 정답에 반영하지 않고 이전 위치에 값이 존재할 경우에만 정답에 반영하는데, 위에 간략히 언급한 것처럼 원소 두 개를 기준으로 탐색하고 있고, 현재 위치에서 발생한 subsequence 는 원소 두 개만을 기준으로 작성한 것이기 때문이다.

현재 위치에서 저장하고 다음 위치에서 현재 위치를 확인했을 때 subsequence 가 존재한다면 원소를 3개 이상 조회한 결과이므로 비로소 정답에 반영할 수 있게 된다.

위와 같은 풀이로 작성한 소스 코드는 다음과 같다. 

class Solution {
public:
    int numberOfArithmeticSlices(vector<int> &nums) {
        if (nums.size() < 3) {
            return 0;
        }
        int ans = 0;
        vector<map<int, int>> dp(nums.size()); // [index, [diff, count]]

        for (int i = 1; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                long delta = (long) nums[i] - nums[j];
                if (delta >= INT_MAX || delta <= INT_MIN) {
                    continue;
                }
                int diff = nums[i] - nums[j];
                dp[i][diff] = dp[i][diff] + 1;
                if (dp[j].find(diff) != dp[j].end()) {
                    dp[i][diff] += dp[j][diff];
                    ans += dp[j][diff];
                }
            }
        }
        return ans;
    }
};

위의 설명과 코드를 연결해 설명하자면, dp 라고 선언한 map 의 배열이 위에서 subsequence 의 개수를 저장하기 위한 수단이다. 배열을 인덱스 개수만큼 생성을 해서 각 인덱스마다 따로 subsequence 를 저장하도록 했고, subsequence 는 단순하게 [공통의 차가 얼마인지, 해당 위치에 저장된 subsequence 의 개수가 몇 개인지] 를 표현하도록 했다.

주어진 문제는 n 의 길이를 갖는 문자열과 정수 배열이 주어졌을 때, 특정 조건에 맞게 문자열을 shift 한 결과를 반환하는 것이다.

위의 <예제 1> 을 가지고 설명을 하자면 문자열 "abc" 와 정수 배열 {3, 5, 9} 가 주어졌을 때, 앞에서부터 부분 문자열 "a" 에 shift() 연산을 세 번 수행해 "dbc" 라는 문자열을 만들고, 그 다음은 "db" 에 대해 shift() 를 수행해 "igc" 를 만든 뒤 마지막으로 "igc" 에 대해 shift() 를 수행해 "rpl" 이라는 문자열을 만든다.

즉, 각 자리 별로 i 번째 자리의 문자는 총 shifts[i] + shifts[i + 1] + ... + shifts[n - 1] 만큼 shift() 연산을 수행하게 된다. 이 문제를 해결하기 위해 적용한 해결 방법은 맨 마지막 자리부터 shift() 연산을 수행하는 것이다.

'n - 1' 번째 문자는 shifts[n - 1] 만큼만 shift() 연산을 수행하므로 이를 수행하고 역순으로 shifts 값을 누적시키며 shift() 연산을 수행하도록 하면 문제를 해결할 수 있을 거라 생각했다. 또한, 주어진 조건에 shifts[i] 는 최대 10억의 값을 가질 수 있는데 shift() 연산의 결과는 항상 영어 소문자이므로 'a' ~ 'z' 까지만의 shift 만 가능하고 shift() 연산의 결과는 26번을 기준으로 동일하기 때문에 shifts[i] 의 값을 26 으로 나눈 나머지값을 가지고 shift() 를 수행하도록 했다.

추가적으로 25번의 shift 를 각 자리별로 일일히 수행하게 될 경우, 이 또한 불필요한 연산을 반복한다 생각했다. 현재 문자가 몇 번째 소문자인지만 확인한 뒤 몇 번의 shift 를 수행하는 지만 확인하면 되기 때문이다. 예를 들어, 'a' 라는 문자는 0 번째 소문자이고 5번의 shift() 연산을 수행한다면 'f' 라는 문자로 치환할 수 있다. 이러한 방식으로 문제를 해결할 수 있었고, 문제의 해결에 사용한 코드는 다음과 같다.

class Solution {
public:
    string shiftingLetters(string s, vector<int>& shifts) {
        int sum = 0;
        for (int i = s.size() - 1; i >= 0; i--) {
            sum = (sum + shifts[i]) % 26;
            s[i] = (s[i] - 'a' + sum) % 26 + 'a';
        }
        return s;
    }
};

주어진 문제는 위와 같이 히스토그램에서 가장 큰 넓이를 갖는 직사각형을 찾는 것이다.

가장 간단한 해결 방법은, 각 위치 별로 좌우로 확장시키며 가질 수 있는 최대 넓이를 확인하는 것인데 이러한 방법은 O(n^2) 의 시간복잡도를 갖는 해결 방법이기 때문에 사용할 수 없었다.

대신 문제의 해결을 위해 스택을 사용하는 방식을 적용할 수 있었다. 왼쪽부터 오른쪽으로 탐색하며 히스토그램 블록의 높이가 점차 증가하도록 스택을 관리한다. 히스토그램 블록의 높이가 지속적으로 증가한다면 계속해서 스택에 해당 위치를 저장하고, 높이가 감소할 경우 현재 스택에 저장된 최대 높이를 갖는 블록에 대해 넓이를 계산한다.

위의 <예제 1> 을 통해 설명을 보강하자면, 처음 스택은 빈 상태로 시작을 하고 첫 번째 인덱스를 저장하게 된다.

스택 : {0}, 최대 넓이 : 0

인덱스가 1일 때, 히스토그램의 높이는 스택에 저장된 인덱스 블록보다 낮으므로 현재까지의 넓이를 계산해 저장한다. 그 뒤 스택이 비어있으므로 인덱스를 다시 스택에 저장한다.

스택 : {}, 최대 넓이 : 2

그 뒤로는, 블록의 높이가 점차 높아지므로 계속해 스택에 인덱스를 저장한다.

스택 : {1, 2, 3}, 최대 넓이 : 2

인덱스가 4가 됐을 때, 다시 블록의 높이가 낮아지므로 높이를 계산한다. 이 때, 현재 탐색 중인 인덱스는 4이고 스택의 탑에 저장된 인덱스는 3, 그 다음 탑의 인덱스는 2이므로 인덱스 3의 높이를 가지고 계산할 수 있는 넓이는 하나의 블록 넓이 뿐이다.

스택 : {1, 2}, 최대 넓이 : 6

다시 인덱스 4에서, 블록의 높이가 아직 낮으므로 높이를 다시 계산한다. 현재 탐색중인 인덱스는 4, 스택의 탑에 저장된 인덱스는 2, 그 다음 인덱스는 1이므로 인덱스 2의 높이를 가지고 계산할 수 있는 넓이는 인덱스 2와 3의 블록 넓이이다. 따라서 넓이는 5 * 2 = 10 이 된다.

스택 : {1}, 최대 넓이 : 10

이러한 방식으로, 스택에 계속해 인덱스를 저장하고 높이를 계산하는 것을 반복하며 최대 넓이를 계산할 수 있다. 이러한 풀이 방식은, 인덱스를 0 에서 n - 1 까지 순차 탐색하며 저장 / 계산 최대 2번 연산을 수행하므로 O(2n) 의 시간 복잡도 (O(2n) 은 O(n) 으로 표현 가능하다) 를 갖는다고 볼 수 있다.

이러한 풀이 방식으로 작성한 소스 코드는 다음과 같다.

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> s;
        int maxArea = 0;
        for (int i = 0; i <= heights.size(); i++) {
            int h = i == heights.size() ? 0 : heights[i];
            if (s.empty() || h >= heights[s.top()]) {
                s.push(i);
            }
            else {
                int top = s.top();
                s.pop();
                int area = heights[top] * (s.empty() ? i : i - 1 - s.top());
                maxArea = maxArea > area ? maxArea : area;
                i--;
            }
        }
        
        return maxArea;
    }
};

주어진 문제는 위와 같다. 단방향 연결 리스트가 주어졌을 때, 이를 반전시키는 것.

문제의 해결 방법은 간단하지만 두 가지 방법으로 풀이가 가능하다. 반복문을 사용하는 방법과 재귀함수를 사용하는 방법.

먼저, 반복문을 사용하는 방법은 노드를 앞에서부터 탐색하면서 해당 노드를 새로운 리스트의 헤더 노드로 만드는 방법이다. 새로운 리스트의 헤더 노드를 현재 탐색중인 노드와 연결한 뒤 헤더 노드를 현재 탐색중인 노드로 변경한다. 이러한 방법으로 리스트의 순서를 뒤집을 수 있다.

아래는 반복문을 사용한 소스 코드이다.

class Solution {
public:
    ListNode *reverseList(ListNode *head) {
        ListNode* reversedHead = nullptr;
        ListNode* tmp = head;
        while (tmp != nullptr) {
            ListNode* next = tmp->next;
            tmp->next = reversedHead;
            reversedHead = tmp;
            tmp = next;
        }
        return reversedHead;
    }
};

다음은 재귀함수를 사용한 방법인데, 노드를 끝까지 먼저 탐색한 뒤 마지막 노드를 반전된 리스트의 헤더 노드로 만든다. 그 뒤 기존의 연결 방향을 반대로 바꾸는 방법으로 문제를 해결한다.

아래는 재귀함수를 사용한 소스 코드이다.

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !(head->next)) {
            return head;
        }
        ListNode* res = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return res;
    }
};

주어진 문제는 위 그림과 같다. 문자열을 원소로 갖는 배열 words 와 문장의 최대 폭을 의미하는 maxWidth 값이 주어졌을 때, 주어진 words 를 문장의 형태로 포맷팅하는 것. 

우선, 각 문장에 words 의 각 단어들을 그리디하게 패킹한 뒤, 남는 빈 공간들은 공백 문자로 채우는 것이 목표이다. 문제의 해결을 위해 각 단어들마다 한 문장에 포함될 수 있는 지 여부를 확인했다. 단계 별로 문장에 단어가 포함될 수 있는 경우 문장에 단어를 포함시킨 뒤 다음 단어를 탐색하고, 포함될 수 없는 경우 (현재 단어를 문장에 추가할 경우, 단어 사이의 공백이 한 문자 이상 들어갈 수 없을 때 포함될 수 없다고 판단한다.) 현재 문장을 주어진 포맷에 맞게 수정한 뒤 저장하고 새로운 문장에 단어를 추가하는 방식으로 문제를 해결한다.

문제의 조건으로, 마지막 문장의 경우는 단어의 개수에 상관 없이 좌측 정렬 (단어 사이의 공백은 한 개로 지정한 뒤, 문장의 뒤에 남는 공간을 모두 공백으로 채움) 하고, 문장에 하나의 단어만 존재하는 경우에도 좌측 정렬을 하도록 되어 있다.

위의 문제 해결 방법을 적용한 소스 코드는 다음과 같다.

class Solution {
public:
    vector<string> ans;

    string makeSentence(vector<string>& words, int maxWidth, bool option) {
        if (words.size() == 1 || option) {
            string sentence = "";
            for (int i = 0; i < words.size(); i++) {
                sentence += words[i];
                if (i != words.size() - 1) {
                    sentence += " ";
                }
            }
            while (sentence.length() < maxWidth) {
                sentence += " ";
            }
            return sentence;
        }
        
        int len = 0;
        for (auto word : words) {
            len += word.length();
        }

        int blankSpace = maxWidth - len;
        int eachBlank = blankSpace / (words.size() - 1);
        int leftBlank = blankSpace % (words.size() - 1);

        string sentence = "";
        for (int i = 0; i < words.size(); i++) {
            sentence += words[i];
            if (i == words.size() - 1)
                break;
            for (int k = 0; k < eachBlank; k++) {
                sentence += " ";
            }
            if (leftBlank) {
                sentence += " ";
                leftBlank--;
            }
        }

        return sentence;
    }

    void justify(vector<string>& curWords, int totalLength, vector<string>& words, int idx, int maxWidth) {
        if (idx == words.size()) {
            if (!curWords.empty()) {
                ans.push_back(makeSentence(curWords, maxWidth, true));
            }
            return;
        }

        if (totalLength + curWords.size() + words[idx].size() > maxWidth) {
            ans.push_back(makeSentence(curWords, maxWidth, false));
            curWords.clear();
            totalLength = 0;
        }

        curWords.push_back(words[idx]);

        justify(curWords, totalLength + words[idx].length(), words, idx + 1, maxWidth);
    }

    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> curWords;
        justify(curWords, 0, words, 0, maxWidth);

        return ans;
    }
};

소스 코드는 다른 문제들에 비해 길게 작성되었지만, 전체적인 구조는 위에서 설명한 바와 같다.

* makeSentence 로직 작성 시, Option 을 추가적으로 받도록 해 마지막 문장인 경우 문제의 추가 조건을 만족시킬 수 있도록 구현했다.

주어진 문제는 위와 같다. n 을 크기로 갖는 문자열 'keysPressed' 와 배열 'releaseTimes' 이 주어지는데 'keysPressed' 는 어떤 순간 어떤 키가 눌렸는 지, 'releaseTimes' 는 각 키가 떼진 순간의 시간을 의미한다.

i 번째로 눌린 키가 눌려진 기간은 releaseTimes[i] - releaseTimes[i - 1] 로 표현된다. (0 번째 키는 releaseTimes[0]) 주어진 정보를 바탕으로 가장 오랫동안 눌려진 키를 찾는 문제이다. 서로 다른 순간에 같은 키가 눌릴 수 있고, 같은 키가 눌린 시간은 각각의 시간으로만 평가하고 누적되지 않는다. 가장 오래 눌려진 키가 여러 개일 경우에는, 사전적으로 더 큰 값을 갖는 키를 정답으로 갖는다.

이 문제는, 단순히 0 번째부터 n - 1 번째까지 (0 - indexed) 각각의 키가 눌린 시간을 계산해 그 중 가장 큰 값을 찾도록 하는 방식으로 문제를 해결했고, 해결을 위해 작성한 소스 코드는 다음과 같다.

class Solution {
public:
    char slowestKey(vector<int> &releaseTimes, string keysPressed) {
        int len = keysPressed.length();
        char ans = keysPressed[0];
        int longestDuration = releaseTimes[0];

        for (int i = 1; i < len; i++) {
            int duration = releaseTimes[i] - releaseTimes[i - 1];

            if (duration > longestDuration || (duration == longestDuration && keysPressed[i] > ans)) {
                ans = keysPressed[i];
                longestDuration = duration;
            }
        }

        return ans;
    }
};