문제 링크https://www.acmicpc.net/problem/1339  풀이- 완전 탐색 + 비트마스킹, 그리디 풀이- 각 알파벳을 0 ~ 9 숫자로 중복 없이 치환하여서 최대값을 구하는 문제 (같은 알파벳은 같은 숫자로 바껴야 하고, 중복 숫자x) 처음 완전 탐색 + 비트 마스킹으로 풀이했다. 그런데 공간복잡도와 시간복잡도가 너무 높이 나왔다.그래서 그리디 풀이 방법을 고민했는데, 아이디어가 전혀 떠오르지 않아 블로그를 참고하여 풀이했다 1) 완전 탐색 + 비트 마스킹- 중복을 제외한 알파벳을 구한다 - 알파벳별로 9~0 사이의 숫자를 할당하면서 완전 탐색을 수행한다- 이때 숫자 사용여부를 비트 마스킹 기법을 사용하였다 ( 9 ~ 0 자리의 비트를 표현하면 되므로 int 로 충분)- idx 가 알..

문제 링크 https://www.acmicpc.net/problem/10597 풀이- 백트래킹 사용- 정답은 구했으나 boolean[] visited 배열을 사용하는 것과 최대 수가 50인걸 파악하지 못한 풀이로 시간 초과 발생- 잘못 풀이한 부분에 대한 이력 남김 문제 설명과 같이 1 ~ N까지의 숫자로 이루어진 순열을 구해야한다- N = 10인 경우 1 부터 10 까지의 수가 중복 없이 모두 포함되어 있어야 한다는 의미- "kriii의 순열은 최소 1개 최대 50개의 수로 이루어져 있다."에서 (러프하게)최대 수가 50까지 라는 것을 파악할 수 있다- 연산을 편하게 하기 위해서 int[] nums 배열을 선언 후 숫자 초기화를 수행하였다 백트래킹 수행할 함수를 아래와 같이 선언하였다(idx >= 배열..

문제 링크https://www.acmicpc.net/problem/2661  풀이- 백트래킹 사용- 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다- 인접한 두 개의 부분 수열이 서로 다르면서 좋은 수열 중 가장 작은 값을 찾는다 ①재귀를 호출할 때 항상 1 ~ 3을 순차적으로 순회하기 때문에 처음 종료 조건(길이가 N인)에 부합하는 값이 최소값임이 보장된다for(int i = 1; i   *좋은 수열이기 위한 유효성 검사 관련하여 ② 이전 값(prev)를 재귀 호출시 파라미터로 전달하고 for문에서 다음으로 연결할 값과 같은 경우(prev == i) continue③ 이전 값(prev)과 다른 경우 해당 숫자를 문자열..

문제 링크 https://www.acmicpc.net/problem/2580  풀이- 백트래킹, 비트 마스킹으로 문제 해결 문제를 한번만 읽고 풀다가 유효성 검사에서 3 * 3 그리드를 누락하여 "틀렸습니다"를 맛 보았다..🥹스도쿠의 필드가 0인 영역을 채울 때 유효성 검사를 총 3가지를 수행해야 했다 ① 행② 열③ 3 * 3 그리드 영역 rows, cols, boxes 각 배열을 사용하여 비트 마스킹을 표현하고, 유효성 검사를 하도록 하였다private static long[] rows;private static long[] cols;private static long[] boxes; 입력 데이터 초기화시  값이 0인 경우 리스트에 좌표 정보를 담고, 나머지의 경우 비트 마스킹 표기를 할 수 있도록 ..

문제 링크https://www.acmicpc.net/problem/19237 풀이개인적으로 상어 시리즈 문제 중에서 쉬운 편이었다고 생각한다구현 요구사항이 복잡해서 이해하는 수고가 필요할 뿐이지 반복문만으로 풀이 가능하였다  처음에 이해가 어려웠던게 아래의 상어의 방향별 우선순위 표였다문제에서 1, 2, 3, 4는 각각 위, 아래, 왼쪽, 오른쪽을 의미할 때①번 상어는 처음 오른쪽 방향을 바라보기 때문에 이동 가능한 위치를 탐색할 때 → ← ↑ ↓ 순으로 "빈칸" 또는 "자기 냄새나는 영역"을 찾는다 입출력 예시도 상어의 방향별 우선순위 때문에 처음에 알아보기 쉽지 않았지만, 두번 풀이하니 적응이 된다 입출력 예시 1에서5 4 4          // n m k (n : n * n, m : 상어 마리 수..

문제 링크 https://www.acmicpc.net/problem/19236 풀이백트래킹이 약한 나에게 있어 정말 실수 연발했던 문제였다 (그래도 백트래킹 재미있다) ① 입력 데이터 초기화 후 상어가 `(0, 0)` 에 물고기를 먹고 그 방향을 가진다 ② 모든 물고기들이 이사를 시작한다- 작은 번호부터 순차적으로 이사- 이동 가능한 위치를 찾을 때 까지 반 시계 방향으로 제자리 회전하면서 빈칸 또는 물고기를 찾아 위치를 교환한다- 상어가 있거나, 맵의 경계를 벗어난 경우 다음 위치로 회전- 만약 이사 가능한 위치가 없다면 제자리를 유지한다③ 상어가 먹이를 탐색한다- 상어는 빈칸으로 이동 불가하고 이동하는 도중에 있는 물고기는 먹지 않는다- 이때, 큰 물고기를 먹는다고 항상 최적의 해를 보장하지 않는다 ..

문제 링크https://www.acmicpc.net/problem/16236 풀이- 구현(시뮬레이션), BFS 격자형 그래프 탐색 문제 - BFS와 2중 for문 만으로 충분하게 풀이 가능한 문제 요구사항 및 절차 ① 현재 상어 위치에서 잡아 먹을 수 있는 물고기까지의 최단 경로 거리를 구한다 - 이때 상어의 크기 이상인 물고기가 있는 칸은 지나갈 수 없다 (상어 크기 )- multi source bfs로 최단 거리를 구함 (시간 복잡도 O(V + E)) ② 최단 거리 정보에서 가장 가까운 물고기 한마리를 선택 (없으면 break문으로 종료)- 여러 마리인 경우 가장 위에 있는 물고기 중 가장 왼쪽에 있는 물고기를 선택- 처음에 정렬을 사용하는 방법을 생각했는나, 그럴 필요 없이 2중 for문으로 최단 ..

문제 출처https://school.programmers.co.kr/learn/courses/30/lessons/1843# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 풀이- 동적 프로그래밍 (dynamic progamming)- bottom-up 방식 풀이  이 문제에서 주의할 점은 사칙연산에서 +는 결합 법칙이 성립하지만, -는 결합법칙이 성립하지 않는다는 부분이다 그렇기 때문에 각 구간별 최대값, 최소값을 구한 후 경우의 수를 고려해야 한다 출처. 나무 위키한 식에서 연산이 두 번 이상 연속될 때, 앞쪽의 연산을 먼저 계산한 값과 뒤쪽의 연산을 ..

문제 출처 https://school.programmers.co.kr/learn/courses/30/lessons/42895# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 풀이- 동적 프로그래밍 (Dynamic Programming)- 숫자 N과 사칙연산을 사용해서 number가 만들어지는 N의 사용횟수(1 ~ 8개) 최소값을 구하는 문제- List 컬렉션에 Set 자료구조를 사용하여 중복을 제거하고, 연산 결과를 자리수마다 담을 수 있도록 하였다List> data = new ArrayList();for(int i = 0; i ());}  우선 첫 자..

문제 출처 https://school.programmers.co.kr/learn/courses/30/lessons/42898 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 풀이- 동적 프로그래밍 (Dynamic Programming) 문제 - 시간 복잡도 : O(NM) - 격자형 그래프가 주어졌을 때 (1,1) -> (n, m)으로 이동하는 경우의 수를 구하는 문제- 이때 이동 방향은 오른쪽과 아래쪽으로만 이동가능하다 ① dp 배열을 정의하고, 물 웅덩이 영역을 -1로 표시한다 (이때 puddles가 m,n으로 주어져서 주의 필요)int row = n;..

문제 출처 https://school.programmers.co.kr/learn/courses/30/lessons/43236 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 풀이- 처음 int[] rocks에서 n개의 바위를 제거하는 조합을 구하는 방식을 생각했으나 50,000C25,000으로 시간 초과 예상 - 이진 탐색 중 매개변수 탐색으로 할 경우 N * log(1억) = 50,000 * 30 시간 복잡도로 풀이 가능 절차- (중요*) int[] rocks를 오름차순 정렬 (ex. [2, 11, 14, 17, 21] )- L과 R의 범위를 지정- 바..

문제 출처 https://school.programmers.co.kr/learn/courses/30/lessons/42627 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 풀이습관처럼 우선 순위 큐에 다 넣고, 정렬을 했었는데 경쟁을 할 때 다음 노드들의 값을 갱신 어떻게 해야 할지에서 막혀서 많은 시간 낭비를 하였다 (습관과 사고를 고쳐야 하는데 .. ) 예제 입력 jobs : [[0, 3], [1, 9], [2, 6]]result : 9 단순히 작업 시간 순으로 정렬한다고 해서 결과값을 구할 수 없었다10ms(= (3 + 11 + 16) / 3)  ..

문제 출처 https://school.programmers.co.kr/learn/courses/30/lessons/42626 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 풀이모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 스코빌 지수 가장 적은 두 가지 음식을 섞어 새로운 음식을 만든다 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) - K 이상 음식을 만들 수 있는 최소 턴 수 (만약 모두 섞었는데 못 구하는 경우 -1 리턴) - 우선 순위 큐, PriorityQueue 사용..

문제 출처 https://school.programmers.co.kr/learn/courses/30/lessons/87694 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  문제 풀이- 격자형 그래프 문제 (BFS)- rectangle의 원소는 각 직사각형의 [좌측 하단 x, 좌측 하단 y, 우측 상단 x, 우측 상단 y] 좌표 형태로 주어진다- 직사각형 외곽 테두리를 통해 시작 (x, y) 에서 도착 (x,y) 까지 최단 거리를 구한다  문제 예시1에서 (3,5) -> (4,5)로 가야하는데 (3,6)으로 가버려서 15(오답)이 나와 시간 소비를 많이 했다..

문제 출처https://school.programmers.co.kr/learn/courses/30/lessons/84021 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 풀이 요약 1. game_board의 빈 영역(0)과 table의 블록 영역(1)을 구한다2. 빈 영역에 블록이 끼워지는지 회전하며 최대 4번 비교한다3. 블록이 빈 영역에 끼워질 경우 결과값에 블록 크기를 누적하고, 사용처리한다 (2-3 반복)  ① game_board 의 빈 영역(0), table 에 블록 영역(1)을 BFS 로 구한다List> emptySpace = new Arra..

문제 출처https://school.programmers.co.kr/learn/courses/30/lessons/42584 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  문제 풀이초 단위로 기록된 주식 가격이 담긴 배열 prices가 주어질때 가격이 떨어지지 않는 기간은 몇초인지 return- 제한 사항 int[] prices의 길이는 2 이상 100,000 이하 - O(n^2)으로 풀이시 O(10^10) 발생 가능- 스택을 사용하여 O(N) 풀이, 인덱스 번호를 스택에 넣는다는 아이디어를 생각하지 못했다. prices : [1, 2, 3, 2, 3]ret..

문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/181857 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 풀이int[] arr 주어질 때 길이가 2의 거듭 제곱이 되도록 하고, 빈 공간은 정수 0으로 채운다 비트 연산자를 사용해서 2의 거듭 제곱 길이를 구한다① arr 길이가 4인 경우 : 4 & 3 == 0 이 true가 되서 4가 반환② arr 길이가 6인 경우 : n보다 커질때까지 result 값을 2배씩 증가해서 8을 반환private int size(int n) { if((..

문제 링크 https://www.acmicpc.net/problem/21942 문제 풀이직접 풀이 못함, 월별 일수 계산하는 방법 알게 되어 기록 - 문자열로 된 날짜 데이터 변환이 어려운 문제였다.- 구현 로직은 Map 자료구조를 사용하여 상대적으로 간단했다- 시간복잡도: O(N)  (Map 자료구조를 사용해서 O(1)에 추가/삭제 가능)  [핵심 로직]- Map에 닉네임과 부품(key) 정보가 없는 경우 대여 이므로 HashMap 에 데이터 추가 한다- Map에 닉네임과 부품(key) 정보가 있는 경우 반납 이므로 HashMap 제거 후 패널티 계산 수행한다- 벌금의 경우에도 Map 자료구조 사용하여 {key: 닉네임, value: 벌금} 형태로 기록한다  실수 1. 최대치 long- 문제에서 yyy..