프로그래머스

[PGM] 점프와 순간이동

문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/12980 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 Greedy 1. 문제 이해 점프는 K칸을 이동하는 것이고 순간이동은 지금까지 온 거리의 2배만큼 이동하는 것 입니다. 이 때 주의해야할 점은 점프는 배터리가 소모되고, 순간이동은 소모되지 않는다는 점입니다. 저는 이 문제를 처음에 대충 읽고 풀다가.. 뒤로도 점프하는 경우까지 고민했네요.(뒤로 점프가 가능하다면 예를들어 15로 가야할 경우에는 16에..

[PGM_77885] 2개 이하로 다른 비트 (Java)

문제링크 https://programmers.co.kr/learn/courses/30/lessons/77885?language=java 코딩테스트 연습 - 2개 이하로 다른 비트 programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 비트연산자 1. 문제 이해 $f(x)$ = $x$ 보다는 크지만 비트 2개만 변경된 값 중 최소값으로 정의되는 함수 $f$가 있을 때, $f(x)$의 값을 구해주는 문제이다. 2. 접근방법 bit연산자인 &연산자를 사용하여 문제를 해결할 수 있다. &연산자는 and연산으로 a & b에서 불 대수 a,b가 모두 1인 경우만 1이다. 비트 두개만 변경하여 최소가 되기 위해서는 가장 작은 위치의 0값을 찾아 1로 바꾸어주고 가장 작은 위치 바로 아래의 1을 0으로 ..

[PGM_42883] 큰 수 만들기 (Java)

문제링크 https://programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 탐욕 알고리즘 1. 문제 이해 숫자 number와 지워지는 문자의 개수 k가 주어질 때 가장 큰 값으로 지워지게 만들어주는 경우를 구해주는 문제이다. number k return "1924" 2 "94" "1231234" 3 "3234" "4177252841" 4 "775841" 위 예시를 보면 알 수 있듯이 1924에서 2개의 수를 지웠을 때 가장 큰 값은 94이고, 1231234에서 3개의 수를 지웠을 때 가장 큰 수는 3234임을 알 수 있다. 2. 접근방법 문제는 굉장히 이해하기 쉽지만..

[PGM_42583] 다리를 지나가는 트럭

문제링크 https://programmers.co.kr/learn/courses/30/lessons/42583 코딩테스트 연습 - 다리를 지나는 트럭 트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 큐 1. 문제 이해 모든 트럭이 다리를 지나가는데 걸리는 시간을 구하는 문제이다. 이 때 트럭이 지나가는 다리의 길이와 가능한 무게가 주어진다. 트럭 한대가 지나가는데 걸리는 시간은 다리의 길이이다. 그리고 트럭이 올라갈 수 있는 한계는 다리의 길이만큼과 다리가 버틸 수 있는 무게의 이하일..

[PGM_17679] 프렌즈 4블록

문제링크 https://programmers.co.kr/learn/courses/30/lessons/17679 코딩테스트 연습 - [1차] 프렌즈4블록 프렌즈4블록 블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록". 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙 programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 구현 1. 문제 이해 프렌즈 4블록 게임은 2x2로 이루어진 블록이 제거되는 게임이다. 위 그림을 보면 라이언과 콘이 2x2로 겹쳐있는 것을 볼 수 있다. 이 경우 해당하는 블록을 제거해주며 된다. 이 때 라이언처럼 겹치게 2x2를 만족하면 겹치는 부분을 포함하여 제거해줄 수 있다는 것을 주의..

[PGM_12978] 배달 (java)

문제링크 https://programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 구현 1. 문제 이해 주어지는 파라미터로 정수인 N과 K 그리고 int형 이차원 배열 road가 주어진다. N은 마을의 개수 K는 특정 임계값 그리고 road는 마을과 마을 사이의 길에 대한 정보가 들어있는 배열이다. road의 첫번째 값은 첫번째 마을, 두번째 값은 두번째 마을 마지막으로 ..

[PGM_76502] 괄호 회전하기 (java)

문제링크 https://programmers.co.kr/learn/courses/30/lessons/76502 코딩테스트 연습 - 괄호 회전하기 programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 구현 1. 문제 이해 괄호로 이루어진 String이 주어졌을 때 해당 괄호를 회전해서 올바른 괄호가 될 수 있는 경우의 수를 구하는 문제이다. 이 때 회전할 수 있는 크기는 주어진 String의 길이만큼만 가능하다. 2. 접근방법 A와 B가 올바른 괄호 문자열이라면 AB도 올바른 괄호 문자열이다. 따라서 우리는 올바른 최소한의 단위의 괄호 문자열들을 구해주면 된다. String의 길이만큼 회전할 수 있다는 뜻은 한바퀴만 돌 수 있다는 의미와 같다. 따라서 최소단위의 올바른 괄호 문자열들로 이루..

[PGM_42890] 후보키 (java)

문제링크 https://programmers.co.kr/learn/courses/30/lessons/42890 코딩테스트 연습 - 후보키 [["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]] 2 programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 완전탐색 1. 문제 이해 DB에 대한 릴레이션이 주어지면 그에 해당하는 후보키가 총 몇개가 존재하는지 찾아내는 문제이다. 2. 접근방법 1) 재귀를 활용하여 키가 될 수 있는 조합을 구해준다. ..

[PGM_72412] 순위 검색 (java)

문제링크 https://programmers.co.kr/learn/courses/30/lessons/72412 = left){ mid = (right + left)/2; if(scores.get(mid) >= score) break; left = mid + 1; } for(;mid != -1 && scores.get(mid) >= score; mid--); return scores.size() - mid-1; 이분탐색을 수행해주는 코드이다. 쿼리로 주어지는 스코어의 값 이상을 찾아주는 것이기 때문에 조건에 맞는 큰 값을 먼저 찾아주고 그 조건을 만족하는 가장 작은 값이 있는 위치까지 옮겨주어야한다. 그 뒤 들어있는 데이터의 개수 전체에서 for문을 돌아 조건을 만족하는 가장 작은 값이 있는 위치의 값을 ..

[PGM_12985] 예상 대진표 (java)

문제링크 https://programmers.co.kr/learn/courses/30/lessons/12985 코딩테스트 연습 - 예상 대진표 △△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 수학 1. 문제 이해 토너먼트로 경기를 진행하게 된다. 이 때 토너먼트 게임은 1 vs 2, 3 vs 4, 5 vs 6 ... 로 진행되며 1 vs 2의 승자와 3 vs 4의 승자가 다음 토너먼트에서 경기를 진행하는 방식이다. 토너먼트를 진행하는 사람의 수 n과 두 명의 선수의 번호 a, b..

[PGM_42577] 전화번호 목록 (java)

문제링크 https://programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 정렬 1. 문제 이해 서로 다른 전화번호에 대한 배열이 주어진다. 전화번호의 접두어에 대한 개념을 이해하기 위해 예를 들어보겠다. 111, 1113, 1424 와 같이 번호가 주어졌다고 하자. 이 때 2번째 전화번호인 1113이 111을 앞에서 포함하고 있다. 그렇다면 111은 1113에 접두어라고 할 수 있다...

[PGM_87946] 피로도 (java)

문제링크 https://programmers.co.kr/learn/courses/30/lessons/87946 코딩테스트 연습 - 피로도 XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던 programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 완전탐색(순열) 1. 문제 이해 - 던전을 도는 xx게임은 피로도를 소모하게된다. 던전에 대한 피로도는 최소피로도와 소모피로도가 있다. 최소 피로도는 던전을 돌기위한 최소의 피로도이며 소모피로도는 던전을 돌았을 때 소모되는 피로도이다. 던전들의 최소피로도 그리고 소모피로도에 대한 값의 정보와 피로도가 주어졌을..

[PGM_1844] 게임 맵 최단거리 (java)

문제링크 https://programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 BFS 1. 문제 이해 (0,0)을 시작점으로 하여 정 반대편에 위치한 (n,m)으로 이동하는 최단거리를 구하는 문제이다. 입력으로 이동할 수 있는지 없는지의 여부의 map이 주어진다. 만약 (n,m)으로 이동할 수 없는 경우에는 -1을 return하여주면 된다...

[PGM_42860] 조이스틱 (java)

문제링크 https://programmers.co.kr/learn/courses/30/lessons/42860 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 브루트포스 1. 문제 이해 입력으로 알파벳으로 이루어진 문자가 주어지면, 조이스틱을 움직여 그 문자를 만들 때 최소한으로 조이스틱을 움직이는 경우를 구하는 문제이다. 조이스틱은 위,아래 그리고 좌,우로 움직일 수 있으며 위와 아래로 움직이는 경우 알파벳이 변경되고 좌우로 움직이면 해당 문자의 위치..

[PGM_42746] 가장 큰 수 (java)

문제링크 https://programmers.co.kr/learn/courses/30/lessons/42746 코딩테스트 연습 - 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 정렬 0과 양의정수의 배열이 주어졌을 때 그 값들을 이어붙여서 가장 크게 만들 수 있는 수를 찾아주는 문제이다. 이 문제를 해결하기 위해 배열에 있는 값들을 정렬하여 이어붙이는 방법을 사용하였다. 단순히 오름차순 혹은 내림차순의 정렬이 아니라 문자열의 ..

[PGM_42587] 프린터 (java)

문제링크 https://programmers.co.kr/learn/courses/30/lessons/42587 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린 programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 Queue 우선순위가 가장 큰 문서부터 먼저 프린터를 하는 문제이다. 만약 우선순위가 대기열에 있던 프린터중에서 제일 높지 않다면 가장 뒤로 넘겨서 처리해주어야한다. 나는 이 문제를 해결하기 위해 Queue를 사용하였다. 문서를 프린터하기 위해 대기열에서 빼는 방법은 순서대로 빼주어야하며, 만약 우선순위가 가장 높지 않..

[pgm_64065] 튜플 (java)

문제링크 https://programmers.co.kr/learn/courses/30/lessons/64065 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 Set 튜플로 만들어지는 집합이 input으로 들어오고 값들을 확인하여 튜플을 찾아내는 문제이다. 이 때 튜플의 수가 (a1,a2,a3,a4)라고 하면 이 것으로 만들수 있는 값들의 집합을 {{a1},{a1,a2},{a1,a2,a3},{a1,a2,a3,a4}}로 구성될 수 있으며, 집합의 순서는 서로 바뀔수 있다. 이 때 튜플로 만들어진 집합을 보고 튜플을 만들어주면 해결할 수 있다. 문제를 해결하기 위해서는 구성된 집합의 크기가 가장 작은 것부터 확인해야한다. 왜냐하면 가장 작은 값 중 포함되지 않은 값을 빼면 순서를 구할 수 있기 때문이다. 예시에서 보여..

[pgm_67257] 수식 최대화 (java)

문제링크 https://programmers.co.kr/learn/courses/30/lessons/67257 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 Deque + 와 - 그리고 * 세개의 연산자의 우선순위를 서로 다르게 하여 계산한 결과의 절대값이 최대가 되는 값을 찾는 문제이다. 연산자 3개에 대한 서로 다른 우선순위가 있는 경우의 수는 6가지 밖에 없으므로 모든 경우를 계산해주고 최대값을 구해주었다. 이때 자료구조는 Deque를 사용해주었다.Deque는 Q..