CodingTest/Programmers

야간전술보행 (Python)

문제설명 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/133501 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 중요 포인트 화랑이가 이동하면 경비병들이 모두 근무를 선다.(1초에서 함께 시작) 화랑이는 1초에 1m/s로 움직이며 경비병들은 근무와 휴식을 번갈아가며 수행한다. 경비병들의 감시 구간은 겹치지 않는다. 화랑이는 멈추지 않는다. 화랑이가 경비병의 감시 구간을 지나갈 때 근무중이라면 붙잡힌다. 입력되는 경비구간은 [시작, 끝]이 아니다. (끝 부분이 앞으로 올 수도 있다.) 출..

[PGM] 점프와 순간이동

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

[PGM] 구명보트 (java)

문제링크 https://programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 Greedy 1. 문제 이해 구명보트를 활용하여 무인도에 갖힌 사람들을 구출할 때 구명보트를 최소한으로 사용한다면 몇개의 구명보트면 구할 수 있을지를 구하는 문제이다. 이 때 구명보트에는 최대 2명의 사람과 제한무게 이하로 탑승할 수 있다. 2. 접근방법 Greedy한 접근을 하면 문제를 ..

[PGM] 주식 가격 (Java)

문제링크 https://programmers.co.kr/learn/courses/30/lessons/42584 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00 programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 우선순위 큐 1. 문제 이해 초 단위로 기록되어있는 주식의 가격에 대한 정보가 들어있는 int형 배열이 input으로 들어올 때 그 가격이 떨어지지 않은 기간이 몇 초인지 return 하는 문제이다. 2. 접근방법 우선순위 큐를 활용하여 문제를 해결할 수 있다. 우선 순위 큐..

[PGM_12981] 영어 끝말잇기 (Java)

문제링크 https://programmers.co.kr/learn/courses/30/lessons/12981 코딩테스트 연습 - 영어 끝말잇기 3 ["tank", "kick", "know", "wheel", "land", "dream", "mother", "robot", "tank"] [3,3] 5 ["hello", "observe", "effect", "take", "either", "recognize", "encourage", "ensure", "establish", "hang", "gather", "refer", "reference", "estimate", "executive"] [0,0] programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 Set 1. 문제 이해 n명의 사람이 ..

[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. 문제 이해 입력으로 알파벳으로 이루어진 문자가 주어지면, 조이스틱을 움직여 그 문자를 만들 때 최소한으로 조이스틱을 움직이는 경우를 구하는 문제이다. 조이스틱은 위,아래 그리고 좌,우로 움직일 수 있으며 위와 아래로 움직이는 경우 알파벳이 변경되고 좌우로 움직이면 해당 문자의 위치..