돌고 돌아 기본

프로그래머스 68645번 - 삼각 달팽이 요구사항 1. 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 반환하라. 요구사항 분석 및 풀이과정 위 사진에서 주어진 삼각형(n=4)을 우리가 다루는 이차원 배열의 형태로 시각화해보면 다음과 같습니다. 이렇게 이차원 배열로 시각화한 후, 기존 삼각형에서 반시계 방향으로 달팽이 채우기를 시각화해보겠습니다. 달팽이 채우기를 위해서 칸을 이동하는 방향에 규칙성이 보이시나요? 1번 화살표 방향 -> 2번 화살표 방향 -> 3번 화살표 방향 -> 1번 화살표 방향 -> ... -> 지금은 n = 4 일 때의 삼각형이지만, n에 따라 그려보시면 1번, 2번, 3번..

프로그래머스 12973번 - 짝지어 제거하기 요구사항 1. 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾은 후 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 2. 1번 과정을 반복해서 문자열을 모두 제거할 수 있으면 1을, 아니면 0을 반환하라. 요구사항 분석 및 풀이과정 연속된 문자열을 모두 제거하는 문제이며 전형적인 스택 문제입니다, 올바른 괄호 쌍을 찾을 때 스택을 사용하는 방법과 동일한 방법으로 구현하면 됩니다. 1. 문자열의 첫 문자부터 순회하여 만약 스택이 비었다면 문자를 추가합니다. 2. 스택이 비어있지 않다면 스택의 가장 위의 문자와 현재 문자가 같은지 확인합니다. (같은 알파벳 2개 붙어있는 짝을 확인하는 작업) 3. 같다면 스택의 가장 위의 문자를 제거하고, 현재 문자도 스택에 넣지 ..

프로그래머스 12914번 - 멀리 뛰기 요구사항 1. 한 번에 1칸 또는 2칸을 뛸 수 있을 때, n개의 칸을 건너 끝에 도달하는 방법의 수를 1234567로 나눈 나머지를 반환하라. 요구사항 분석 및 풀이과정 1. n개의 칸을 건너 끝에 도달하는 방법의 수를 dp[n]이라고 정의하면 다음과 같습니다. dp[n] = dp[n-2] + dp[n-1] ( n >= 3 ) dp[1] = 1 ( 1칸 ) dp[2] = 2 ( 1칸 + 1칸, 2칸 ) n개의 칸을 건너 끝에 도달하는 경우 마지막에 2칸을 뛰어 끝에 도달하는 경우와, 1칸을 뛰어 끝에 도달하는 경우가 있습니다. 마지막에 2칸을 뛰는 경우는 마지막 2칸을 제외한 n-2 개의 칸을 건너오는 경우의 수이고, 마지막에 1칸을 뛰는 경우는 마지막 1칸을 제..

프로그래머스 17680번 - [1차]캐쉬 요구사항 1. LRU 캐시 교체 알고리즘을 기반으로 주어진 도시 이름들을 조회할 때 걸리는 실행 시간을 측정하여 반환하라. 2. 캐시 히트(cache hit) 일 경우 실행시간은 1, 캐시 미스(cache miss) 일 경우 실행시간은 5이다. 요구사항 분석 및 풀이과정 LRU 캐시 교체 알고리즘은, 캐시의 크기가 꽉 찼을 경우 가장 오래된 캐시 데이터를 삭제하고, 새로운 데이터를 캐싱하는 알고리즘입니다. 자세한 알고리즘이 궁금하다면 여기를 참고해주세요. 우리는 LRU 캐시 교체 알고리즘을 리스트를 이용하여 구현할 것입니다. 리스트의 가장 앞부분은 캐시에 가장 오래된 데이터가 존재하며, 가장 뒷부분으로 갈수록 최근에 캐시에 저장된 데이터가 존재하는 방식입니다. 리..

프로그래머스 42578번 - 위장 요구사항 1. 스파이가 가진 의상으로 입을 수 있는 서로 다른 옷의 조합의 수를 반환하라. 2. 스파이는 하루에 최소 한 개의 의상은 입습니다. 요구사항 분석 및 풀이과정 1. 각 의상 종류마다 의상을 선택할 수 있는 경우의 수는 입지 않는 경우를 포함해서 총 "의상의 수 + 1"입니다. 2. 스파이가 입을 수 있는 서로 다른 옷의 조합의 수는 "모든 의상 종류에 대한 경우의 수를 곱한 값에서 1을 뺀 값"입니다. 1을 빼는 이유는 스파이는 하루에 최소 한 개의 의상은 입어야 하기 때문에, 모든 의상을 입지 않는 경우를 빼줘야 합니다. 3. 각 의상 종류마다 몇 가지 의상이 있는지를 기록하여 경우의 수를 구합니다. 소스코드 작성 import java.util.Map; i..