코딩테스트

[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_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_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_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_42586] 기능개발 (java)

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

[카카오] 단체사진찍기 (java)

문제링크 https://programmers.co.kr/learn/courses/30/lessons/1835 코딩테스트 연습 - 단체사진 찍기 단체사진 찍기 가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 브루트포스 순열 카카오 프렌즈 캐릭터 8명이 원하는 순서대로 사진을 찍을 수 있는 횟수를 구하는 문제이다. 캐릭터가 순서대로 서는 경우의수는 8!이며 최대로 들어올 수 있는 조건이 100개이다. 따라서 최악의 경우 $O(8!*100)$의 시간이 걸리게 된다. 따라서, 브루트포스로 문제를 해결할 수 있다. 순열로 문..

[카카오] 오픈채팅방 (java)

문제링크 코딩테스트 연습 - 오픈채팅방 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오 programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 Map, 구현 카카오 오픈채팅방의 입장과 퇴장의 로그를 리턴해주는 문제이다. 닉네임을 변경하는 경우에는 과거의 입장 및 퇴장의 닉네임도 변경해주어야 한다. 닉네임을 변경하는 방법은 다시 입장시 혹은 방 안에서 변경이 가능하다. 닉네임은 Map을 활용하여 id와 닉네임을 매핑시켜주었다. 모든 record를 확인하여 출력해주어야할 log는 가변배열인 ArrayList를 사용해서 넣어주었고, 닉네임이 변경될 수 있는 경우..

[카카오] 신고 결과 받기 (java)

문제링크 코딩테스트 연습 - 신고 결과 받기 문제 설명 신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다. 각 유저는 한 번에 한 명의 programmers.co.kr 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 Set(집합) 신고 결과 받기 문제는 유저들이 신고를 하는 정보를 확인하고 신고를 당한 횟수가 k 이상일 경우 정지를 주게 되는데, 그 때 정지를 받은 유저를 신고한 유저에게 알람을 준다면 알람을 받을 횟수를 확인하는 문제이다. 이 때 한 유저가 동일한 사람을 중복으로 신고하면 한번으로 처리를 해야한다. 이 조건을 만족시키기 위하여 나는 집합을 사용하여 구현하였다. 집합은 데이터를 중복없이 한개씩만 가지고 있..

[BOJ_16197] 두 동전 (java)

문제링크 https://www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 브루트포스, 재귀 문제는 두 동전을 보드판에 올려놓고 상하좌우 중 한 곳으로 이동시켜 주어 하나의 동전만 떨어뜨리는 방법을 구하는 문제이다. 단, 동전이 움직일 때 벽을 만나게 되면 움직이지 못하며, 그 외의 경우에는 모두 움직여 줄 수 있다. 떨어지는 경우는 동전이 보드의 배열 밖으로 나가는(범위를 벗어나는) 경우가 된다. 이 문제를 브루트포스로 ..

BOJ_14888 연산자 끼워넣기 (Java)

문제링크 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 브루트포스 연산자를 끼워 넣는 문제는 브루트포스로 해결하였다. 연산자의 개수는 숫자 배열의 크기 -1 이므로 최대 10개이다. 10개를 순서를 고려하여 나열하는 방법은 최대 10!이므로 시간초과 없이 해결할 수 있다. 따라서, 만들수 있는 모든 연산자의 경우의수를 만들어준 뒤 계산해 주면 쉽게 해..

[backjoon_2225] 합분해 (Java)

문제링크 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제설명 더보기 더보기 문제 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 입력 첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다. 출력 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. 제한사항 제한시간 메모리제한 2초 128MB * 출처 : https://www.acmicpc.ne..

[Backjoon_4375] 1 (Java)

문제 링크 https://www.acmicpc.net/problem/4375 4375번: 1 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. www.acmicpc.net 문제 요약 더보기 더보기 더보기 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성한다. 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다. 1로 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력한다. 시간 제한 1초 메모리 제한 128MB 문제 풀이 n을 입력받아 n의 배수중 1로만 이루어진 가장 작은..

최대, 최소공배수 그리고 소수

최대공약수(GCD) 두 수 a,b의 공통된 약수중 가장 큰 수 - 구하는 방법 1. 2부터 시작해서 a,b로 공통되게 나누어 떨어지는 것중 최대값을 구한다. O(n) -> n은 a,b중 최소값 2. 유클리드 호제법을 사용하기 // 나는 주로 재귀를 사용하는 편 public int gcd(int a, int b){ if(a%b == 0) return b; return gcd(a,a%b); } //반복문을 사용하여 구할수도 있음 public int gcd(int a, int b){ int temp; while(true){ if(a%b == 0) return b; temp = a % b; a = b; b = temp; } } 위 코드는 유클리드 호재법을 사용해서 구현해본 코드이다. 최소공배수(LCM) - 최소..

약수

약수를 구하는 방법 1. 1부터 n까지 %연산을 활용하여 구하기 2. 1부터 루트n까지 %연산을 활용하여 구하기 루트n까지만 비교해도 되는 이유는 약수는 짝을 지어 있기 때문이다. 약수의 개수가 홀수일 경우 root를 씌어준 값이 약수가 된다.(루트n까지 확인해야한다.) 시간복잡도 1번 방법 : O(n) 2번 방법 : O(√n) // 1번 방법 O(n) int n = 121; for(int i = 1; i