전체 글

조이스틱https://school.programmers.co.kr/learn/courses/30/lessons/42860풀이알파벳 변경처음 알파벳 A에서 위로 가는 횟수 vs 아래로 가는 횟수 -> 더 작은 값for (int i = 0; i 커서 이동문자 길이 n -> 기본 이동(`move`): n - 1중간에 A 없음 -> 그냥 오른쪽으로 커서 이동중간에 A 있음 -> 돌아가는 게 나을 수도 있음ex. JAN오른쪽으로만 이동: 0 -> 1 -> 2 => 2칸뒤로 돌아서 이동: 0 -> 왼쪽 -> 2 => 1칸 오른쪽 갔다가 돌아오기: `i * 2 + (n - next)`오른쪽: i / 되돌아오기: i / 왼쪽으로 끝까지: n - next왼쪽 갔다가 돌아오기: `(n - next) * 2 + i`왼쪽:..

큰 수 만들기https://school.programmers.co.kr/learn/courses/30/lessons/42883풀이앞자리가 클수록 전체 수가 커짐(`k > 0`) + (스택의 top(`stack.peekLast()`) `stack.pollLast()`: 스택 pop`k--`현재 숫자 pushfor (char n : number.toCharArray()) { while (!stack.isEmpty() && k > 0 && stack.peekLast() 예시number: 1924 / k: 21빈 스택 -> pushstack = [1] / k = 29top(1) pop k = 1빈 스택 -> pushstack = [9] / k = 12top(9) > 2 -> Xpush stack = [9..

숫자 변환하기 https://school.programmers.co.kr/learn/courses/30/lessons/154538풀이BFS`Queue q = new ArrayDeque()``int[] dist = new int[y + 1]``dist[v]`: v에 도착하기까지의 최소 연산 횟수`Arrays.fill(dist, -1)`: 방문 X로 초기화 가능한 3가지 연산x에 n 더하기: `cur + n`x에 2 곱하기: `cur * 2`x에 3 곱하기: `cur * 3`-> y 넘어가면 의미 X + 방문 안 한 경우(-1)만 탐색if (cur + n 코드import java.util.*;class Solution { public int solution(int x, int y, int n) { ..

1517 - 버블 소트https://www.acmicpc.net/problem/1517문제N개의 수로 이뤄진 수열 A[1], A[2], ..., A[N]버블 소트: 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방식ex. 3 2 1 -> 2 3 1 -> 2 1 3 -> 1 2 3입력첫째 줄: N (1 다음 줄: N개의 정수 A[1], A[2], ..., A[N] (0 출력: swap 횟수풀이버블 정렬에서 발생하는 swap 횟수 = 역순 쌍(inverse) 개수 합병 정렬(Merge Sort)배열을 반으로 분할 -> 각 절반을 재귀적으로 정렬 -> 정렬된 두 배열 병합(merge)시간 복잡도: O(N log N) mergeSort(lt, rt)[lt ~ rt] 구간 정렬`lt >= rt`: 원소가 1개 ..

백준 3109 - 빵집https://www.acmicpc.net/problem/3109문제빵집이 있는 곳은 RxC 격자로 표현할 수 있음/ 첫째 열은 근처 빵집의 가스관이고, 마지막 열은 원웅이의 빵집빵집과 가스관 사이에 건물이 있을 수 있고, 건물이 있는 경우 파이프를 놓을 수 없음가스관과 빵집을 연결하는 모든 파이프라인은 첫째 열에서 시작해야 하고, 마지막 열에서 끝나야 함각 칸은 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 다각선으로 연결할 수 있고, 각 칸의 중심끼리 연결가스관과 빵집을 연결하는 파이프라인을 여러 개 설치하는데 이 경로는 겹칠 수 없고, 서로 접할 수 없음 = 각 칸을 지나는 파이프는 하나여야 함입력첫째 줄: R, C (1 다음 R개 줄: 빵집 근처 모습 (`x`: 건물/ `.`: 빈..

17143 - 낚시왕https://www.acmicpc.net/problem/17143문제RxC인 격자판에서 낚시왕이 상어 낚시/ 격자판의 각 칸은 (r, c)로 나타낼 수 있는데 r은 행, c는 열이고 (R, C)는 가장 오른쪽 아래칸에는 상어가 최대 1마리 들어있을 수 있고 상어는 크기와 속도를 가지고 있음낚시왕은 처음에 1번 열의 한 칸 위에 있음1초 동안 순서대로 일어나며, 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하면 이동 멈춤1. 낚시왕 오른쪽으로 한 칸 이동2. 낚시왕이 있는 열에 있는 상어 중 땅과 제일 가까운 상어 잡음/ 상어 잡으면 격자판에서 사라짐3. 상어 이동상어는 입력으로 주어진 속도로 이동하고, 속도의 단위는 칸/초상어가 이동하려고 하는 칸이 격자판의 경계를 넘는 경우 방향을 ..