CodingTest

[PGM_42839] 소수 찾기

문제링크 https://programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 완전탐색, 순열 1. 문제 이해 String으로 숫자에 대한 문자열이 입력으로 주어지고, 그 문자열에 있는 숫자들을 한 글자씩 취급하여 새로운 조합의 숫자를 만들었을 때 소수인 경우를 구하는 문제이다. 2. 접근방법 문제를 해결하기 위해 주어지는 숫자를 순열로 나타낼 수 있는 경우의 수를 모두 만들어주..

[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..

[PGM_81302] 거리두기 확인하기 (java)

문제링크 https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 브루트포스 이 문제는 5개의 방에 5x5로 ..

[PGM_17677] 뉴스 클러스터링 (java)

문제링크 https://programmers.co.kr/learn/courses/30/lessons/17677 코딩테스트 연습 - [1차] 뉴스 클러스터링 뉴스 클러스터링 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브 programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 자료구조 Map을 사용 이 문제는 2개의 문자열에 대하여 2문자씩 연속하는 값으로 문자열 집합을 구성한다. 2개의 집합에 대하여 교집합을 합집합으로 나눈 값을 65536을 곱하고 소수점을 버려서 뽑아내는 문제이다. 집합과 다른점은 중복을 허용한다는 점이다. 따라서 Map으로 집합을 표현해주었다...

[PGM_60058] 괄호 변환 (java)

문제링크 https://programmers.co.kr/learn/courses/30/lessons/60058 코딩테스트 연습 - 괄호 변환 카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 구현, 시뮬레이션 괄호변환 문제는 괄호를 올바르게 만드는 과정을 구현하는 문제이다. 문제에서는 괄호를 올바르게 변경하는 방법에 대하여 알려주고 있으므로 알려주는 알고리즘을 구현해주기만 하면 된다. 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니..

[PGM_72411] 메뉴 리뉴얼 (java)

문제링크 https://programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 브루트포스 사람들의 주문내역이 입력으로 들어온다. 그 주문내역에서 함께 시킨 단품 메뉴들을 확인하여, 가장 많이 함께 시킨 메뉴들을 묶어 세트메뉴를 만들어주는 문제이다. 세트메뉴에 단품메뉴의 개수도 입력으로 주어지게 된다. 문제를 해결하기 위하여, 각 사람들이 메뉴를 n가지씩 뽑는 경우의 수를 모두 구하는 메소드를 구..

[PGM_77485] 행렬 테두리 회전하기 (java)

문제링크 https://programmers.co.kr/learn/courses/30/lessons/77485 코딩테스트 연습 - 행렬 테두리 회전하기 6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]] [8, 10, 25] 3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] [1, 1, 5, 3] programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 구현 쿼리가 주어지면 그 쿼리에 맞추어 행렬의 테두리 부분을 시계방향으로 돌려주게 된다. 그리고 그 값들중에 최소값을 찾는 문제이다. 쿼리는 x1,x2,y1,y2로 주어지게 된다. 행렬은 1행 1열부터 1부터 채워지는 값이다. 문제에 있는 예시를 보면 행렬은 6x6 행렬이며 (2,2,5,4)의 쿼리..

[PGM_12973] 짝지어 제거하기 (java)

문제링크 https://programmers.co.kr/learn/courses/30/lessons/12973 코딩테스트 연습 - 짝지어 제거하기 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙 programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 Stack 연속되는 문자열을 짝지어서 제거해주는 문제이다. 처음에 문제를 해결할 때 subString을 사용해서 붙이고 모든 문자열을 돌아도 괜찮다고 생각이 되어 그렇게 문제를 해결하였다. 그러나 효율성에서 점수를 받지 못하여, 새로운 방법을 고안하다가 스택을 사용해서 문제를 해결하게 되었다. (스택을 ..

[PGM_43165] 타겟 넘버 (java)

문제링크 https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 브루트포스 - 재귀 2021.11.02 - [CordingTest/Algolithm] - 브루트포스(2) 재귀 배열과 타겟넘버 두개의 인풋이 들어온다. 이 때 배열의 값을 적당히 + 혹은 -로 넣어주어 더해서 타겟 넘버를 만족시키는 경우의수를 모두 구하는 문제이다. 배열의 개수가 최대 20개 ..

[PGM_42626] 더 맵게 (Java)

문제링크 https://programmers.co.kr/learn/courses/30/lessons/42626# 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 Heap 처음에는 그냥 단순하게 초기 정렬 후 삽입정렬로 값을 계속 넣어주었는데 효율성에서 0점을 받았다. 곰곰히 생각해보니 적절한 자료구조로 Heap을 사용하면 되겠다고 생각되어 Heap을 사용해 문제를 해결해 주었다. 더 맵게 문제는 매운맛에 대한 배열과 매운 강도 K값이 input으로 주어진다. ..

[PGM_42626] 더 맵게 (Java)

문제링크 https://programmers.co.kr/learn/courses/30/lessons/42626# 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 Heap 처음에는 그냥 단순하게 초기 정렬 후 삽입정렬로 값을 계속 넣어주었는데 효율성에서 0점을 받았다. 곰곰히 생각해보니 적절한 자료구조로 Heap을 사용하면 되겠다고 생각되어 Heap을 사용해 문제를 해결해 주었다. 더 맵게 문제는 매운맛에 대한 배열과 매운 강도 K값이 input으로 주어진다. ..

자바에서 Heap 사용하는 방법

Java에서 Heap 사용하기 Java에서는 Collection으로 Heap이 없다. 하지만 Max-Heap과 Min-Heap을 Primary Queue를 활용하여 구현할 수 있다. 이번 시간에는 Primary Queue를 활용해 Heap을 구현하는 방법을 알아보고자 한다. Heap이라는 자료구조는 값들이 모여있는 자료구조를 트리로 구현하였다고 할 때, 루트에 위치하는 값이 최대 혹은 최소값이 되는 자료구조를 의미한다. 최소 힙 사용하기 최소힙을 사용하는 것은 Primary Queue를 그대로 사용해주면 된다. PriorityQueue minHeap = new PriorityQueue(); 이렇게 사용하여 컬렉션에 데이터를 넣으면 remove되는 peek의 값이 minHeap의 최소값이 된다. Prim..

[PGM_42586] 기능개발 (java)

문제링크 https://programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 구현 기능을 구현을 하고 기능이 구현이 완료되면 업데이트를 수행한다. 이 때, 기능은 순서가 있으며 앞의 기능이 구현이 되지 않았다면 뒤에 기능이 구현이 되어도 배포가될 수 없다. 입력으로 기능의 순서와 진행도 그리고 각 기능별 구현하는 속도가 주어진다. 기능이 배포가 될 때 몇개의 기능이 한번에 배포가 되는..

[PGM_12899] 124 나라의 숫자 (Java)

문제링크 https://programmers.co.kr/learn/courses/30/lessons/12899 코딩테스트 연습 - 124 나라의 숫자 programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 3진수 이 문제는 1과 2 그리고 4로 숫자를 표현하는 진법으로 변환해주는 것이다. 문제를 계속 들여다보면 3진법으로 구성되는 것을 알 수 있다. 10진법의 수가 1일 경우 1, 2일 경우 2, 3일 경우에는 4, 4일 경우에는 11 이 되는 것을 알 수 있다. 원래 3진수의 경우 3이 될 때는 carry가 발생하여 자리수를 변경해주어야하는데, 딱 3일 경우에는 4로 변경이 되는 특이점이 있다. 따라서 주어진 값을 진수로 변경하여주고 이러한 특이점을 해결해주면 문제를 풀 수 있다. n진수..

[PGM_62048] 멀쩡한 삼각형 (java)

문제링크 https://programmers.co.kr/learn/courses/30/lessons/62048 코딩테스트 연습 - 멀쩡한 사각형 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 최대공약수 최대공약수를 활용하여 문제를 해결할 수 있다. 가로와 세로의 최대공약수를 구해주게 되면 가로와 세로의 비율을 알 수 있게된다. 즉, 대각선으로 그었을 때, 가로와 세로의 비율 만큼의 값이 동일한 패턴으로 잘려지게 될 것이다. 예를들어 예시의 내용을 참고하면, 세로의 길이 12 가..