문제풀이
-
[프로그래머스]가장 긴 팰린드롬 - JAVA문제풀이/프로그래머스 2021. 3. 12. 13:57
[프로그래머스]가장 긴 팰린드롬 programmers.co.kr/learn/courses/30/lessons/12904 코딩테스트 연습 - 가장 긴 팰린드롬 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들 programmers.co.kr 풀이 중첩 반복문을 사용하여 가장 긴 팰린드롬을 찾아내도록 하였다. 가장 긴 팰린드롬을 발견하면 그대로 그 값을 반환하였다. 우선 팰린드롬의 길이를 문자열 s의 길이로 지정한 후 팰린드롬이 아니라면 길이를 1씩 줄여나가면서 찾았다. 그 다음 시작점 부터 팰린드롬의 길이 만큼 s의 문자들을 비..
-
[백준]2458:키 순서 - JAVA문제풀이/백준 2021. 3. 10. 18:34
[백준]2458: 키 순서[백준]2458: 키 순서 www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 풀이 키를 비교한 결과의 일부를 입력받고, 이를 통해서 유추할 수 있는 비교 순서를 모두 유추한 다음 확실하게 자신의 키가 몇 번째 인지 알 수 있는 학생의 수를 출력하는 문제이다. 모든 학생들의 비교 순서를 비교하면서 유추할 수 있는 비교 순서가 발견되면 값을 변경해 주기 위해 플로이드-와샬 알고리즘을 사용하였다. 풀이 순서는 다음과 같당. MAX값으로 초기화..
-
[백준]1038: 감소하는 수 - JAVA문제풀이/백준 2021. 3. 9. 21:00
문제 www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 풀이 처음에는 정직한 완전탐색 방법으로, 이전에 뽑은 수에 1씩 더해가며 감소하는 수 인지 판별하며 수를 찾았다. 이렇게 풀면 시간초과가 발생한다. 제일 첫 번째 뽑는 수를 기준으로 감소하는 수를 만들어서 list에 저장하고, list를 정렬하여 n번째 수를 반환하도록 하였다. 예를들어서 아래와 같당. 처음에 뽑는 수 다음에 올 수 있는 수 만들어 지는 수 1 0 10 2 1, 0 21, 2..
-
[백준]2023: 신기한 소수 - JAVA문제풀이/백준 2021. 3. 8. 18:51
[백준]2023: 신기한 소수 www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 풀이 N자리 수중에 소수를 모두 출력하는 DFS문제이다. 숫자를 자리수 별로 하나씩 뽑으면서 뽑았을 때 소수가 되는 경우만 수를 이어서 뽑는다. 뽑다가 N자리가 되는 순간 출력을 하도록 하였다. 소수를 판별하는 방법은 에라토스테네스의 접근 방식을 사용했다. 소수 판별식 코드는 아래와 같다. public static boolean isPrime(int num) { if(n..
-
[백준]9019: DSLR - JAVA문제풀이/백준 2021. 3. 7. 19:53
문제 www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 풀이 A를 B로 표현할 수 있는 최소한의 방법을 출력하는 것이므로 BFS를 사용하였다. 모든 경우에서 4가지 명령어를 실행하고 각각의 실행한 경우에서 또 명령어를 실행하도록 반복해 주었다. 이러다가 B가 되었을때 그때까지의 명령어를 반환하도록 하였다. 현재까지 사용된 명령어를 저장하기 위해서 Node 클래스를 사용해 주었다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15..
-
[프로그래머스]입국심사 - JAVA문제풀이/프로그래머스 2021. 3. 5. 14:30
[프로그래머스]입국심사 programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 풀이 심사를 받는데 최소로 소요되는 시간을 반환하는 문제로 소요되는 시간을 기준으로 이분탐색을 하였다. 우선 제일 오래 걸리는 심사위원을 알아내기 위해 times를 정렬해 주었다. 그리고 제일 오래걸리는 심사위원의 시간을 알아내어 최대 시간을 계산해 주었다. 이때 최대 소요 시간이란, 제일 오래걸리는 심사위원이 n명 모두를 심사할때 소요되는 시간이 되므로..
-
[백준]13023: ABCDE - JAVA문제풀이/백준 2021. 3. 4. 14:19
[백준]13023: ABCDE www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 풀이 모든 경우를 탐색하는 DFS탐색 문제로, A -> B -> C -> D -> E인 관계가 있다면 1을 출력, 아니면 0을 출력하는 문제이다. 위와 같은 연결 관계가 있다면 DFS탐색 깊이가 4가 되는 것을 이용하여 문제를 풀었다. 반복문을 사용하여 시작 순서를 돌아가면서 DFS탐색을 하였고, 탐색 깊이가 4가 되는 순간 1을 출력하고 프로그램을 종료했다. 1이 출력되면 그 이후에는 더 이상 탐색하지 않아도 되기 때문이다. 모든 DFS탐색 동안 1이 출력이 되지 않는다면 위와 같은 ..
-
[프로그래머스]야근 지수 - JAVA문제풀이/프로그래머스 2021. 3. 4. 13:53
문제 programmers.co.kr/learn/courses/30/lessons/12927 코딩테스트 연습 - 야근 지수 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도 programmers.co.kr 풀이 works 배열의 원소에서 n만큼 뺀 값중 나머지에 대해 제곱의 합이 최소인 값을 찾는 문제이다. 제곱의 합이 최소가 되기 위해서는 works의 각 숫자들이 전체적으로 균형이 맞아야 한다. 예를 들어 첫 번째 예제 입력의 경우, works = {4, 3, 3}이고 n이 4이다. 이때 n시간을 모두 첫 번째 일을 처리하는데 사용하면 남는 시간은 0, 3..