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를 돌며 각각이 보유한 정점 개수 세기정점 개수 간의 차를 구해서 차이 최소값 ..

1. 문제에 대하여 📦문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/87946(1) 조건 분석 📊k = 체력던전 = 던전은 행이 n개, 열이 2개 인 2차원 배열 던전[i][0] : i 번째 던전에 들어가기 위한 최소 체력 (입장 자격 요건)던전[i][1]: i 번째 던전을 클리어 했을 때 깎이는 체력2. 코드가 나오기까지 🛠️KEY WORD: 순열 순열: 던전 클리어 순서에 따라, 클리어한 던전의 수가 달라질 수 있으므로, 순서가 있게 경우의 수를 뽑아야한다.백트래킹: 매 순열 depth마다 체력이 다음 던전 입장 시 체력 기준에 맞는지 보는 식으로 풀어도 될 거 같다. 하지만 필자는 순열로 경우의 수를 구한 뒤에, base-..

1. 문제에 대하여 📦문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42842(1) 조건 분석 📊2차원 배열에서 테두리 원소의 개수(이하 brown) , 테두리 아닌 원소의 개수 (이하 yellow)가 주어진다.이때 주어진 brown과 yellow를 만족하는 2차원 배열의 행과 열의 길이를 배열 형태로 반환하라.2. 코드가 나오기까지 🛠️KEY WORD: 시뮬레이션, 사고력 테두리로 가로와 세로를 임의로 나누어서 2차원 배열을 형성한다.그렇게 나눈 2차원 배열의 테두리 안쪽의 원소 개수와 yellow의 개수가 일치하는 시점을 출력한다.이때, 2차원 배열을 실제로 만들지 않아도 된다. 왜냐하면 $(가로-2) \times (세로-2..

1. 문제에 대하여 📦문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42839(1) 조건 분석 📊numbers의 문자 하나 하나를 하나의 종이 조각이라 생각한다. (즉 일의 자릿수로 이루어진 종이가 존재함) 이 종이들을 조합하여 숫자를 만들 때, 그 숫자가 소수인 경우가 몇 개 있는지 그 개수를 세어라 2. 코드가 나오기까지 🛠️KEY WORD: 순열, 소수 판정 순열로 숫자 조합을 찾는다.각 depth 마다 소수 판정을 해서, 나올 수 있는 모든 자릿수의 수에 대하여 소수 확인을 거친다.소수인 수들의 개수를 세서 반환한다. (1) 시간복잡도 분석 ⏳N개의 숫자가 주어졌을 때, 모든 자릿수의 숫자 조합을 구하는 가짓수: $_N ..

1. 문제에 대하여 📦문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42840(1) 조건 분석 📊각 수포자의 찍는 방식은 고정됨. 모의고사 답지가 주어질 경우, 각 수포자별 점수를 계산, 가장 많이 맞춘 사람을 배열로 반환동점자가 있을 경우, 번호 별로 오름차순 하기2. 코드가 나오기까지 🛠️KEY WORD: 시뮬레이션, 나머지 활용 수포자는 3명으로 고정, 각 수포자의 패턴은 다음과 같다. int [] A = new int [] {1,2,3,4,5}; int [] B = new int [] {2,1,2,3,2,4,2,5}; int [] C = new int [] {3,3,1,1,2,2,4,..

1. 문제에 대하여 📦문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/86491(1) 조건 분석 📊명함들의 가로 세로가 주어질 때, 모든 명함을 넣을 수 있는 지갑의 최소 면적을 구하시오.이때, 명함을 90% 돌려서 가로와 세로를 서로 바꾸는 것도 가능하다.2. 코드가 나오기까지 🛠️KEY WORD: 시뮬레이션해당 문제는 사고력 문제로, 실제 명함을 지갑에 넣는 상황에서, 어떻게 하면 명함을 꾸기지 않고 넣을 수 있을지 생각해보면 문제가 쉽게 풀린다. (필자는 그것에 실패해서 문제를 푸는데 시간이 오래 걸렸다.)이번 문제는 가로와 세로에 의미를 부여하지 않아야 문제가 풀린다.명함의 종류에는 다음과 같이 가로형과 세로형이 있을 수 있..

1. 문제에 대하여 📦문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42578(1) 조건 분석 📊종류 별로 옷을 최대 한 가지씩 골라서 코니가 코디할 수 있는 옷의 가짓수를 구하는 문제2. 코드가 나오기까지 🛠️KEY WORD: HashMap 활용 해당 문제는 코디할 수 있는 옷의 가짓수를 요구하므로, 옷의 종류별로 옷이 총 몇 종류인지만 카운트하면 된다.따라서 HashMap을 만들어서 로 해서 정보를 수집한다.여기서 중요한 점은 옷을 하나도 안 고르고 다음 종류의 옷으로 넘어갈 수 있다는 것이다. 따라서 모든 가짓수에 기본적으로 +1을 한 상태로 시작한다.이후 각 옷의 가짓수를 곱한다. 이것의 뜻은 $$ _n C _1 \tim..

1. 문제에 대하여 📦문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42577(1) 조건 분석 📊전화번호 목록이 주어진다. 다음을 만족하는 반환값을 출력하라.A,B 두 명의 전화번호에 대하여A의 전화번호가 B의 전화번호에 완전히 포함되면? false 출력 모든 전화번호 통틀어서, 위의 경우가 없다면? true 출력2. 코드가 나오기까지 🛠️KEY WORD: HashMap활용, 트라이 Hashmap으로 푼 경우와, 트라이를 활용한 경우 총 두가지로 문제를 풀었다. (1) HashMap 활용 풀이해시맵에 모든 전화번호 목록 String으로 넣어두기 (KEY 전화번호, VALUE는 안씀)전화번호 목록을 순회하며 다음을 진행 해당 전..

1. 문제에 대하여 📦문제 링크: 폰켓몬 링크(1) 조건 분석 📊폰켓몬의 유형 수와 뽑아야 하는 폰켓몬의 수를 비교해야 한다. 유형 수 >= 뽑기 수 이면, 뽑기 수 모두 다른 유형으로 채울 수 있다는 뜻이므로, 뽑기 수를 그대로 출력 한다.유형 수 2. 코드가 나오기까지 🛠️KEY WORD: HashMap의 map.putIfAbsent() 활용가짓수를 체크하기 위해, putIfAbsent로 map에 없는 값일 경우만 넣는다. (1) 시간복잡도 분석 ⏳시간 복잡도 체크가 필요 없는 문제였다.3. 코드 🌐(1) SUDO CODE 💬// 의사 코드도 문제가 간단해서 생략한다.(2) JAVA CODE ☕import java.io.*;import java.util.*;class Solution { ..

1. 문제에 대하여 📦문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42576(1) 조건 분석 📊마라톤 참가자와 마라톤 완주자 목록이 주어졌을 때, 완주하지 못한 인원을 구하는 문제2. 코드가 나오기까지 🛠️KEY WORD: Hash Map의 compute 활용 마라톤 참가자들을 모두 HashMap 자료구조에 넣어서 정보를 저장한다. 이다.이는 동명이인을 상정하고 그렇게 만든 것이다.이후 완주자 리스트를 순회하며, 리스트의 이름을 참가자 리스트에서 지운다.지운다의 의미는 'HashMap에서 해당 이름의 value를 1 삭제한다.' 는 뜻이다. 만약 삭제했을 시, value가 0이 되면 그대로 삭제한다. (이를 쉽게 계산하기 위해..

Relevace Framing 🧩관련된 개념 : [[시뮬레이션]], [[정렬]]1. 문제에 대하여 📦문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42579(1) 조건 분석 📊곡마다 장르와, 재생 수가 나온다. 이제 모든 장르에서 2개의 곡씩 뽑아서 하나의 배열에 '수록' 할건데, 방법은 다음과 같다.속한 노래가 많이 재생된 장르를 먼저 수록한다.장르 내에서 많이 재생된 노래를 먼저 수록한다.장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록한다.2. 코드가 나오기까지 🛠️KEY WORD: 시뮬레이션, 정렬 Hash 문제인데, 정렬만 사용한 것 같다. 먼저 장르 라는 객체와 뮤직 이라는 객체를 각..

Relevace Framing 🧩관련된 개념 : [[시뮬레이션]], [[재귀]] 1. 문제에 대하여 📦문제 링크: https://www.acmicpc.net/problem/16719(1) 조건 분석 📊주어진 문장에서 아직 보여주지 않은 문자 중 하나를 추가했을 때, 사전 순으로 먼저 오는 단어들을 차례대로 출력한다.만약 STARTLINK라는 단어가 주어지면 AAIAIKAINKALINKARLINKARTLINKSARTLINKSTARTLINK이 순으로 와야 한다.보면서 주목해야할 점은 다음과 같다.A 뒤쪽을 먼저 다 확인한 뒤, A의 앞쪽을 보고 있음. T 두 개 중 뒤쪽의 T가 먼저 나옴그 이유는 다음과 같다. A가 알파벳 중 가장 사전 순이 빠른 문자인데, 이것의 앞에 어떤 문자가 나오는 것보다, 이..

1. 문제에 대하여 📦문제 링크: https://www.acmicpc.net/problem/16926(1) 조건 분석 📊배열을 원이라 쳤을 때, 동심원 별로 한 바퀴 돌리면 된다.2. 코드가 나오기까지 🛠️KEY WORD: 시뮬레이션(1) 배열을 회전시키는 방법문제 요구사항은 반 시계 방향으로의 회전이다. 이걸 실제로 구현하려면 나보다 뒷순서의 원소값을 나의 위치에 옮겨 담는 작업이 필수이므로, 실제 원소 재할당의 움직임은 시계 방향(문제 요구사항의 역방향)으로 이루어져야 한다.(2) 점점 안 쪽 동심원으로 들어가는 방법이것은 출발점을 정하면 쉽다. 한 번의 동심원 회전이 끝나면 (i,i) 였던 출발점을 (i+1, i+1)로 바꾸면 된다. 근데 여기서 주의해야할 지점이 있다.바로 얼마나 들어가야할..