1. 문제에 대하여 📦문제 링크: https://www.acmicpc.net/problem/17837(1) 조건 분석 📊A. 말에 대한 규칙말은 각자 나아가려는 방향이 있다.하나의 칸에 여러 말이 있을 시, 윷놀이처럼 기존에 있던 말이 새로 해당 칸에 온 말을 업는다. (stack)하나의 말이 자신의 방향으로 움직일 때 업힌 말들도 같이 움직인다. (이떄 자신의 나아가려는 방향은 바뀌지 않는다.)말들은 자신이 나아갈 다음 칸의 색깔에 따라 행동이 미세하게 바뀐다.B. 보드 칸 별 규칙흰 칸을 밟을 경우, 업은 말 전부 같이 움직이는 거 외에 특이 사항 없음빨간 칸을 밟을 경우, 자신을 포함한 업은 말들의 위치가 거꾸로 되어야 한다.(exA->B->C (TOP) 순으로 업혀 있었다면, C -> B -..

1. 문제에 대하여 📦문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42747(1) 조건 분석 📊현재 확인 중인 논문의 인용횟수가 h번 이상, 전체 논문 중 h번 이상 인용된 논문의 수도 h개 이상이 될 수 있는 h값의 최대값을 구하라2. 코드가 나오기까지 🛠️KEY WORD: 정렬 정렬로 풀면 된다는 것은 명확했는데, 문제는 저 문장을 어떻게 해석할 것이냐다.내가 잘못 풀었던 지점까지 더해서, 설명하면 두 가지로 나뉠 수 있을 것 같다.오름차순으로 전체 논문의 인용횟수를 정렬이제 배열의 첫 번째 논문부터 순회하며 2번을 시행한다.2-1 현재 조회 중인 논문의 인용 횟수 확인, 이후 그 오른쪽 논문의 수를 확인하여,인용 횟수 2..

1. 문제에 대하여 📦문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42746(1) 조건 분석 📊배열에 주어진 숫자들을 일렬로 나열해서 최대값을 만들어야 한다.[6, 10, 2] -> 62102. 코드가 나오기까지 🛠️KEY WORD: 정렬, Comparator배열 진행은 다음과 같이 한다. a, b 가 있다고 했을 때,ab, ba 구조의 숫자를 만든다 .이 둘의 대소관계를 비교해서 내림차순으로 정리한다.이를 위해서 Arrays.sort() 를 사용했고, int를 Integer Wrapper Class로 교환했다.이렇게 한 이유는 Arrays.sort()에 두번째 인자인 Comparator를 오버라이딩할 경우, 첫 번째 인자가 객..

1. 문제에 대하여 📦문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/427483. 코드 🌐import java.util.*;class Solution { public int[] solution(int[] array, int[][] commands) { int [] answer = new int [commands.length]; for(int i = 0; i 4. 트러블 슈팅 or 배운 점📝없음.

1. 문제에 대하여 📦문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42628(1) 조건 분석 📊이중 우선순위 큐는 다음 연산이 가능한 자료구조를 의미한다.I 숫자: 형태의 명령어는 큐에 주어진 숫자를 삽입D 1: 큐에서 최댓값을 삭제D -1: 큐에서 최소값을 삭제2. 코드가 나오기까지 🛠️KEY WORD: 우선순위 큐, HashMap maxHeap, minHeap Java에는 최대값과 최소값을 ArrayDeque처럼 머리와 꼬리에서 동시에 뺄 수 있는 자료 구조가 없기 때문에, 우선순위 큐를 두 개 활용하여야 한다.이때 많은 사람들이 궁금해할 것은 '어떻게 이 둘의 Sync를 맞출 거냐' 는 것일 거다.만약 숫자 내림차순 ..

1. 문제에 대하여 📦문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42627(1) 조건 분석 📊Job의 요소로는, 작업의 번호, 작업의 요청 시각, 작업의 소요 시간이 있다. Job은 매 초마다, 대기큐에 적재된다.대기큐는 다음과 같은 약속으로 내부 우선순위가 정해진다.소요 시간이 짧을수록 우선순위가 높다.소요 시간이 같다면 요청 시각이 빠를수록 우선순위가 높다.소요시간, 요청시각이 같다면, 작업 번호가 작을수록 우선순위가 높다.디스크는 하나의 일을 그것의 소요시간만큼 해낸다.이때, 임의의 작업이 그것의 요청시각부터 끝날때까지 걸린 시간을 a라고 했을 때, 모든 작업의 a의 평균을 구하라. 2. 코드가 나오기까지 🛠️KEY WO..

1. 문제에 대하여 📦문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42626(1) 조건 분석 📊주어진 모든 음식의 스코빌 지수가 K를 넘어설 때까지 가장 안 매운 두 음식을 합친다.음식을 합치는 공식은 다음과 같다.섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)2. 코드가 나오기까지 🛠️KEY WORD: 우선순위 큐맵기 오름차순으로 줄 세운다.큐 맨 앞의 음식이 전체 음식 중 스코빌 지수 최소값임으로 이것이 K보다 높으면 모든 음식이 K보다 지수가 높다는 것이다. (이때 계산 반복문을 탈출한다.)두 개 뽑아서 합친다.예외 처리:큐 안에 음식이 하나 이하로 남..

1. 문제에 대하여 📦문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42584(1) 조건 분석 📊매초 주식 가격이 하나씩 나온다.하나의 주식 가격이 그 밑으로 떨어지지 않은 기간을 구하여라[!example][3,1,2,3] 으로 각 초마다의 주식 가격이 주어졌을 경우,0초의 주식 가격은 그 다음 초에 1로 바로 떨어진다. 따라서 가격이 떨어지지 않은 기간은 1초이다.반면 1초대의 주식가격은 주식 가격 배열이 끝날 때까지 그보다 밑으로 떨어지지 않는다.2. 코드가 나오기까지 🛠️KEY WORD: STACK 활용 STOCK이란 클래스를 만든다. 멤버변수는 해당 주식 가격이 나왔던 초(index)와 가격(price)이다.STACK에 ..

1. 문제에 대하여 📦문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42583(1) 조건 분석 📊대기 중인 트럭이 순서대로 다리를 지난다. 다리는 길이와 내구도 무게가 존재하는데, 최대 그 길이 수만큼의 트럭만 올라갈 수 있으며, 올라간 트럭의 무게 합이 다리의 내구도 무게를 넘어서면 안된다. 트럭은 1초에 다리를 한 칸씩 건넌다. 한칸 = 다리의 길이/1 2. 코드가 나오기까지 🛠️KEY WORD: 큐 활용 모든 대기 트럭이 다리를 지날 때까지 반복해야한다.반복의 기준은 초단위이다. 1초마다 버스가 움직이고, 새로운 버스가 다리에 들어오기 때문이다. 문제에 제시된 조건 그대로 구현하면 되는 것이라서, 추가 설명은 SUDO CO..

1. 문제에 대하여 📦문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42587(1) 조건 분석 📊각 프로세스는 무조건 우선순위가 높은 순으로 실행된다.이때 인수로 주어진 숫자가 원래 대기 큐 상 위치인 프로세스가 실행되는 순서는 언제일까?2. 코드가 나오기까지 🛠️KEY WORD: 큐 활용 프로세스의 실행 우선순위가 높은 것부터 내림차순한 우선순위 큐 만들기(우선순위 큐는 '실행 대기 중인 프로세스 중 우선순위가 높은 순' 이다.프로세스의 원래 위치를 담은 일반 큐 만들기우선순위 큐의 peek()의 우선순위 == 프로세스의 poll()의 우선순위이면, 현재 프로세스 실행해도 된다. 이때 해당 프로세스는 이미 실행 후 종료했으므..

1. 문제에 대하여 📦문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12909(1) 조건 분석 📊( 문자로 열렸으면 반드시 ) 로 닫혀야지만 올바른 괄호 라고 부를 수 있다.문제에서 주어진 예시 문자열이 올바르면 true, 아니면 false를 출력하라.2. 코드가 나오기까지 🛠️KEY WORD: 스택 활용 사전 설정: top = stack의 맨 윗부분을 가리킴(이 들어오면 top++ 이후 해당 자리에 새로운 값 집어넣기)이 들어오면 현재 top 위치의 값 지우고, top-- 하기 ) 가 들어왔는데, top == -1 이면, 이미 현재 문자는 자신의 짝이 없다는 것이므로 false를 출력전체계산 이후에 stack이 비어있다면, 모..

1. 문제에 대하여 📦문제 링크: http://school.programmers.co.kr/learn/courses/30/lessons/42586(1) 조건 분석 📊각 기능은 진도가 100%일 때 배포가 가능하다.기능마다 순서가 있고, 후순위 기능이 먼저 진도 100%가 되었어도, 선순위가 아직 진도 100%가 아니면 기다려야 한다.선순위가 100%가 되면, 그것의 연속된 후순위 진도 100%인 것도 같이 배포된다.(즉 특정 날짜에 [100%, 100%,, 0%, 100%] 로 되어 있는 경우, 첫 기능과 두 번재 기능만 배포 되고, 4번째 기능은 3번째가 100%가 될 때까지 기다려야 한다.)2. 코드가 나오기까지 🛠️KEY WORD: 큐 활용문제에서 제시한 그대로 구현하면된다.필자는 큐를 활용했..

1. 문제에 대하여 📦문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12906(1) 조건 분석 📊동일한 수가 연속으로 나오면 제거 해야한다.근데 연속되지 않으면 수가 중복되어 나와도 상관 없다.예시[ 1, 2, 2, 0, 2] 로 나와있다면, 제거되고 남은 배열은 [ 1, 2, 0, 2] 이다. 2. 코드가 나오기까지 🛠️KEY WORD: STACK 활용 JAVA에서 기본 제공하는 자료구조 STACK을 활용하지 않고, 배열을 활용하여 푼다. 이유는 자료구조 클래스 이용으로 드는 오버헤드를 제거하기 위함이다.JAVA의 STACK 클래스는 vector를 상속받아 모든 메서드를 동기화(syncronized)하기 때문에, 단일 스레드 ..

1. 문제에 대하여 📦문제 링크: https://www.acmicpc.net/problem/16987(1) 조건 분석 📊계란이 횡으로 존재하고, 순차적으로 하나씩 손에 쥔다.손에 쥔 계란과 행에 아직 존재하는 계란 중 하나를 부딪힌다. 그러면 각각의 내구도가 서로의 무게만큼 깎인다.내구도가 0 이하로 내려가면 깨진다.손에 쥘 차례가 된 계란이 이미 깨져 있으면 넘어간다.최대한 계란을 많이 깼을 때 그 갯수를 구하라.2. 코드가 나오기까지 🛠️KEY WORD: 백트래킹 이걸 백트래킹으로 풀지 않으면 중복순열로 풀어야 한다. 왜냐하면, 손에 쥔 계란마다 때릴 계란을 고를텐데, 손에 쥔 계란마다 때릴 계란은 무조건 하나여야 하지만, 맞는 계란은 복수의 계란에게서 맞을 수 있기 때문이다. 아무리 $N \..

1. 문제에 대하여 📦문제 링크: https://www.acmicpc.net/problem/14891(1) 조건 분석 📊날이 8개인 톱니바퀴가 4개 존재하고, 날마다 N극, S극이 있다.해당 톱니바퀴들은 횡으로 나열되어 있고, 서로의 3시와 9시 날의 극이 서로에게 영향을 준다.현재 내가 조회 중인 톱날의 3시와 그것의 오른쪽 톱날의 9시가 서로 전자극 영향을 받는다.현재 내가 조회 중인 톱날의 9시와 그것의 왼쪽 톱날의 3시가 서로 전자극 영향을 받는다.특정 톱니바퀴는 시계방향, 반시계방향으로 회전할 수 있다. 한 번의 회전당 날이 한 번 위치를 바꾼다.톱니바퀴가 회전하면, 그것과 영향을 받는 이웃 톱니바퀴가 서로 3시, 9시 방향에서 전자극이 다르면, 이웃 받는 톱니바퀴는 반대로 돌아간다.(문제 ..

1. 문제에 대하여 📦문제 링크: https://www.acmicpc.net/submit/13460(1) 조건 분석 📊격자판을 기울이면, 기울어진 쪽 끝까지 이동한다. (한 칸씩 x) 만약 구멍으로 Red 구슬, Blue 구슬 둘 다 들어가면 이건 실패로 간주한다. 기울인 거 한번 == 움직임 한 번으로 간주한다. 2. 코드가 나오기까지 🛠️KEY WORD: 시뮬레이션, BFS 개빡구현 시뮬레이션이다. 필자가 봤을 때, 구현이 어려운 포인트를 집어봤다.방문처리를 어떻게 할 것인지기울임 = 움직임 한 번 체크는 어떻게 할 것인지구슬 두 개가 하나의 좌표로 모이는 경우RED가 구멍에 들어갔을 때, Blue가 구멍에 들어갔을 떄, 둘 다 들어갔을 때 처리 하나씩 살펴보자.(1) 방문 처리를 어떻게 할..

1. 문제에 대하여 📦문제 링크: https://www.acmicpc.net/problem/14712(1) 조건 분석 📊배열 내에 2 * 2짜리 부분 배열 모든 값이 1이면 넴모넴모 라고 한다.배열 내 각 좌표에 1 아니면 0을 둘 수 없을 때, 넴모넴모가 없는 경우의 수를 구하라2. 코드가 나오기까지 🛠️KEY WORD: 백트래킹배열의 한 좌표씩 0과 1을 두어보면서 확인하면 된다.끝까지 계산한 뒤에, 넴모넴모 있는지 여부를 체크하면, 계산 과정에서 이미 무효한 경우의 수도 끝까지 세어야함으로 비효율적이다.따라서 계산 과정에서 넴모넴모를 만나면 그 이후의 경우의 수를 거치지 않는다. 이런 식으로 그때 그때 계산하면, 훨씬 효율적이다.(1) 시간복잡도 분석 ⏳$N \times M 따로 시간복잡도를 ..

1. 문제에 대하여 📦문제 링크: https://www.acmicpc.net/problem/6443(1) 조건 분석 📊영어 단어가 n개 주어짐.하나의 영어 단어마다 거기서 나올 수 있는 글자조합을 사전순으로 나타내기중복 제외2. 코드가 나오기까지 🛠️KEY WORD: 순열, np (next permutation)(1) 순열로 푸는 법인수로 받은 문자열의 각 자리마다 방문배열을 두는 순열 풀이는 '메모리 초과'가 난다.메모리 초과가 나는 이유는 4. 트러블 슈팅에 기록해두었으니 참고하길 바란다.해당 풀이에서 주의해야할 점은 서로 다른 글자간에는 순서가 있지만, 같은 글자간에는 순서가 없다는 것이다. 예를 들어 aba를 차례대로 두는 경우의 수에서경우의 수 별 각 글자의 순서aba1회1232회321위의..

1. 문제에 대하여 📦문제 링크: https://www.acmicpc.net/problem/3980(1) 조건 분석 📊2차원 배열로 11명의 선수의 포지션 별 능력치가 주어진다.만약 members(i)(j) = k 라면, i번 선수의 j 포지션 능력치는 k라는 뜻이다. 만약 members(i)(j) = 0 라면, i번 선수는 j 포지션에서 뛸 수 없다.11명의 선수를 포지션에 잘 배치해서 능력치 합계의 최대치를 출력하라.2. 코드가 나오기까지 🛠️KEY WORD: 순열, 백트래킹 순열로 포지션 별 선수 뽑기이때 현재 조회 중인 선수가 해당 포지션에서 뛸 능력이 없다면 넘어감 -> 백트래킹base-case에서 선수들의 포지션별 능력치 합계를 낸다.최대치를 갱신한다.(1) 시간복잡도 분석 ⏳11! =..

1. 문제에 대하여 📦문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/84512(1) 조건 분석 📊A ~ UUUUU 까지의 단어가 사전 순으로 정렬되어 있을 때 인수로 들어오는 단어는 순서 상 몇 번인지 출력하라.2. 코드가 나오기까지 🛠️KEY WORD: 중복 순열, 정렬 문자가 5개 이하라 중복 순열 사용해도 시간 초과가 나지 않을 것 같았다.따라서 다음과 같이 풀었다.모든 중복 순열 구하기 (5개 중 1개 뽑기, 2개 뽑기… 5개 뽑기)정렬원하는 값의 index 출력 (1) 시간복잡도 분석 ⏳전체 문자 개수가 5개 이하라서 중복 순열을 사용해도 괜찮다.3. 코드 🌐(1) SUDO CODE 💬의사 코드는 위의 풀이 설명과 ..

1. 문제에 대하여 📦문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/86971(1) 조건 분석 📊하나의 연결된 트리가 나온다. 해당 트리의 간선 중 하나를 끊었을 때, 트리가 2분할될텐데, 해당 2분할된 트리간의 정점 차이를 최소화 하라.2. 코드가 나오기까지 🛠️KEY WORD: 완전탐색, bfs 간선의 최대 개수가 99개라서, 하나씩 끊어보면서 해도 될 거 같아, 완전 탐색을 활용했다. 다음과 같이 진행된다.인접 리스트 만들기 (양방향 그래프여야함 주의) 순회하면서 지울 간선을 하나 선택하기해당 간선을 지우고, 나눠진 왼쪽과 오른쪽에 대해서 BFS를 돌며 각각이 보유한 정점 개수 세기정점 개수 간의 차를 구해서 차이 최소값 ..