C++ TIL day 13

1. string 관련 함수 정리

• 어제 코딩테스트를 풀다가 다른 사람들의 풀이를 보던 도중, 내가 잘 쓰지 않는 함수들을 발견해서 이번 기회에 기억해보려고, 정리해 보았다.

https://gbleem.tistory.com/21

string 관련 함수들 (tolower, isalpha, transform)

2. 람다식

• 위에서 말한 string 관련 함수들에 대해 공부하던 도중, 람다식을 쓰는 예제가 있어서 정리를 해보게 되었다. (C++공부를 하다보면, 화수분처럼 궁금한게 계속 튀어나오네요..)

https://gbleem.tistory.com/22

Lambda Expressions

3. 코딩 테스트

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

프로그래머스

• 오늘 오전 코드카타 시간에는 프로그래머스 level 2의 삼각 달팽이 문제를 풀었다.

문제 이미지

• 이것과 비슷한 문제를 예전 코딩테스트에서 풀게 되었는데, 그 때 풀지 못해서 공부해 두었던 개념을 이용해서 해결을 했다.
• 이 문제는 결론적으로 dx dy를 잘 써서, 아래와 같은 그림으로 배열을 구성하면 되는 문제이다.

• dx dy 테크닉
  • bfs나 2차원 배열에서 격자를 돌아다는 종류의 문제들은 dx dy를 잘 이용해서 풀면, 생각보다 쉽게 해결할 수 있다.
  • dx dy 테크닉에서 기억할 것
    • 내가 가고자 하는 방향을 순서대로 적어두기 (시계방향, 반시계 방향 등)
    • 헷갈리지 않으려면 아래의 방향을 잘 기억하기
      • x가 증가하는 방향은 행이 증가하는 방향
      • y가 증가하는 방향은 열이 증가하는 방향
      • 아래 코드에서는 (1,0), (0,1) (-1, -1) 순서로 이동할 텐데 이방향은 각각 아래의 의미를 뜻한다.
        • (1,0) 아래로 (행이 증가)
        • (0,1) 오른쪽으로 (열이 증가)
        • (-1,-1) 왼쪽 대각 위로 (행과 열이 감소)
• 코드 해석
  • 위에서 말한 것 처럼 dx dy는 우리가 이동할 방향을 뜻한다.
    • (1,0), (0,1), (-1,-1) 순서로 배치한 이유는 달팽이의 이동 경로가 아래 -> 오른쪽 -> 왼쪽위 대각선 이므로
    • dir이라는 변수를 통해 경로가 바뀌는 순간 dx, dy의 값을 바꿔주면 되기 때문이다.
  • nx, ny는 다음 스텝에서 우리가 갈 위치를 뜻한다.
    • 이때 우리는 언제 달팽이의 방향이 바뀌는지 체크해야 한다.
    • 다음 스텝으로 갈 위치에 이미 숫자가 있거나, n의 갯수를 넘어설 때 방향을 바꿔주어야 한다.
    • 그래서 이 두 가지 경우에 dir + 1을 통해 쉽게 이동하는 모습을 구현할 수 있다.

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int board[1002][1002];
int dx[3] = { 1, 0, -1 };
int dy[3] = { 0, 1, -1 };

vector<int> Print(int n)
{
    vector<int> ans;

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (board[i][j] != 0)
                ans.push_back(board[i][j]);
        }
    }
    return ans;
}

vector<int> solution(int n)
{
    vector<int> answer;

    int total = 0;
    for (int i = 1; i <= n; ++i)
        total += i;

    pair<int, int> cur = { 0, 0 };
    int dir = 0;
    board[0][0] = 1;

    for (int i = 1; i < total; ++i)
    {
        int nx = cur.first + dx[dir];
        int ny = cur.second + dy[dir];

        if (board[nx][ny] != 0)
        {
            dir = (dir + 1) % 3;
            nx = cur.first + dx[dir];
            ny = cur.second + dy[dir];
        }
        else if (nx >= n || ny >= n)
        {
            dir = (dir + 1) % 3;
            nx = cur.first + dx[dir];
            ny = cur.second + dy[dir];
        }

        board[nx][ny] = board[cur.first][cur.second] + 1;
        cur = { nx, ny };
    }

    answer = Print(n);

    return answer;
}