코딩테스트
-
Q. 1215. 회문(D3)코딩테스트/SWEA_Java 2023. 5. 11. 16:25
Q. 1215. 회문(D3) 0. 문제 D3 난이도의 문제이고, 격자형 그래프를 활용한 구현 문제라고 생각된다. N이 주어지고 문자가 적혀있는 격자형 그래프가 주어진다. 격자형 그래프의 가로 / 세로 N개의 문자열을 뽑았을 때 똑바로/거꾸로 읽어도 똑같은 단어의 경우의 수를 구하는 문제이다. 1. 풀이 1) 격자형 그래프를 두 개 저장하는데, 하나는 그대로 나머지는 90도 돌린 방향으로 저장한다. (가로 / 세로 모두를 고려 해야 하므로) 2) 나올 수 있는 모든 문자열에 대해 회문 문자인지 판별한다. (만약 N이 홀수인 경우 ex.4 모든 문자를 비교해야 하지만, 5인 경우 1 2번째와 4 5번째 문자만 비교하면 된다.) import java.io.BufferedReader; import java.io..
-
Q. 1860. 진기의 최고급 붕어빵(D3)코딩테스트/SWEA_Java 2023. 5. 10. 23:01
Q. 1860. 진기의 최고급 붕어빵(D3) 0. 문제 D3 난이도의 문제이고, 구현 문제라고 생각된다. N, M, K가 주어진다. N은 붕어빵을 먹으려는 사람의 수 이고, M초에 K개의 붕어빵을 만들 수 있다. 한 손님은 한 개의 붕어빵을 가져 간다고 하면, 모든 손님들에게 기다리는 시간없이 붕어빵을 제공할 수 있는지 판별하는 프로그램을 작성하라. 1. 풀이 1) 손님들이 오는 순서가 차례대로 주어지지 않으므로 먼저 입력을 받은 뒤 정렬을 한다. 2) 그리고 손님들을 받으면서, 만약 현재 붕어빵이 없을 경우 손님의 시간 이하인 K 배수만큼 시간을 더하고, 붕어빵을 만들어서 손님에게 줄 수 있는지 판별한다. 3) 손님에게 줄 수 없을경우 즉시 루프를 종료한다. 시간을 줄이기 위해 손님이 온 시간에 만약 ..
-
Q. 1225. 암호생성기(D3)코딩테스트/SWEA_Java 2023. 5. 9. 21:07
Q. 1225. 암호생성기(D3) 0. 문제 D3 난이도의 문제이고, Queue를 사용한 구현 문제라고 생각된다. 숫자가 8개 주어지고 맨 앞의 숫자에 1을 빼고 맨 앞의 숫자를 맨 뒤로 보낸다. 이후 다음 숫자는 2를 빼고 맨 뒤로 보낸다. 빼는데 사용하는 숫자를 n이라고 했을 때 n이 5를 넘어서면 n은 1이 된다. 입력에 주어진 8개의 수 중 하나라도 0이 되면 루프를 종료하고, 결과를 출력하는 문제이다. 1. 풀이 1) 입력값을 받은 뒤에 큐에 저장한다. 2) 일일히 값을 빼가며 문제의 로직대로 수행한다. import java.util.Arrays; import java.util.Deque; import java.util.LinkedList; import java.util.StringTokeniz..
-
Q 1859. 백만 장자 프로젝트(D2)코딩테스트/SWEA_Java 2023. 5. 8. 23:35
Q 1859. 백만 장자 프로젝트(D2) 0. 문제 D2 난이도의 문제이고, 단순한 배열 순회 문제라고 생각된다. 매일 매일 물건의 가격이 주어진다. 하루에 물건은 하나만 살 수 있고, 파는 수량은 제한이 없다.이 때 최대 이익을 출력하는 문제이다. 1. 풀이 처음에 투 포인터나 정렬을 이용한 문제인가? 라는 생각을 했었는데, 단순하게 생각을 뒤집어서 맨 뒤에서 앞으로 배열을 조회하면 해결할 수 있었다. 1) 배열의 맨 뒤에서 앞으로 순회한다. 1-1) 이 때 만약 기존 최대 가격보다 큰 가격을 만날 경우 그 값을 저장한다. 1-2) 그렇지 않은 경우 기존 최대 가격 - 현재 가격을 결과값에 저장한다. import java.util.Scanner; import java.util.StringTokenize..
-
Q. 1206. View (D3)코딩테스트/SWEA_Java 2023. 5. 7. 22:03
Q. 1206. View(D3) 0. 문제 D3 난이도의 문제이고, 구현 문제라고 생각된다. 빌딩들의 높이가 주어지고, 오른쪽/왼쪽 두 칸이 비어있으면 그 집은 조망권이 확보된다고 말할 때, 조망권이 확보되는 세대의 수를 구하는 문제이다. 1. 풀이 1) 모든 땅에 대해 왼쪽 2칸의 높이의 최대값 & 오른쪽 2칸 높이의 최대값을 저장한다. 2) 그리고 두 값을 현재 땅의 높이와 비교해서, 현재 땅이 양 옆 높이의 최대값보다 높은 경우 그 차이를 결과에 저장하는 방식으로 풀었다. import java.util.Scanner; import java.util.StringTokenizer; import java.io.BufferedReader; import java.io.FileInputStream; impor..
-
Q. 15657 자바 : N과 M(8)코딩테스트/백준_Java 2023. 4. 25. 23:29
Q. 15657 자바 : N과 M(8) 문제 : boj.kr/15657 실버 3 난이도의 문제이다. N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. - N개의 자연수 중에서 M개를 고른 수열 - 같은 수를 여러 번 골라도 된다. - 고른 수열은 비내림차순이어야 한다. - 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 수열에서 원소를 선택할 때는 중복을 허용하지만, 수열은 중복하면 안된다.주의해야 할 점은 수열은 사전 순으로 증가하는 순서로 출력한다 라는 내용 때문에 수열을 입력 받은 뒤 정렬이 한번 필요하다. 이 문제는 백트래킹과 재귀함수를..
-
Q. 15654 자바 : N과M(5)코딩테스트/백준_Java 2023. 4. 24. 22:59
Q. 15654 자바 : N과M(5) 문제 : boj.kr/15654 실버 3 난이도의 문제이다. N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. - N개의 자연수 중에서 M개를 고른 수열을 출력하는 문제이다. 주의해야 할 점은 수열은 사전 순으로 증가하는 순서로 출력한다 라는 내용 때문에 수열을 입력 받은 뒤 정렬이 한번 필요하다. 이 문제는 백트래킹과 재귀함수를 이용해 풀었고, 이전 계산한 결과를 배열에 저장하고, 깊이가 최대일 때 까지 탐색을 완료하면 저장한 결과를 출력하는 방식으로 풀었다. 시간 복잡도를 계산하면, M과 N이 최대 8이므로 1. 계산 - O(N^M) 2. 출력 - O(NM) ..
-
Q. 14940 자바 : 쉬운 최단거리코딩테스트/백준_Java 2023. 4. 22. 23:20
Q. 14940 자바 : 쉬운 최단거리 문제 : boj.kr/14940 실버 1 난이도의 문제이다. 그래프가 주어지고, 시작 정점이 주어질 때 모든 정점의 최단거리를 출력하는 문제이다 주의해야 할 점은 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다는 점 이다 아래와 같은 방법으로 풀었다. 1. 입력은 bool 타입의 2차원 배열로 받았으며, 방문 가느한 위치를 true로 표시했다. (이 때 시작 정점의 위치는 따로 저장해 주었다.) 2. 이후 BFS 순회를 통해 모든 정점을 탐색하며 결과값은 ResArr이라는 2차원 int형 배열에 저장했다. (벽이 아닌 경우 - !Graph[y][x], 방문한 경우 visit[y][x] 에는 방문하지 않았다) 3. 탐색이 끝난 뒤 출력을 위..