algorithm
-
[프로그래머스] 불량 사용자 (08.04)algorithm/프로그래머스 2020. 8. 4. 18:05
문제 https://programmers.co.kr/learn/courses/30/lessons/64064 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 무지는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 �� programmers.co.kr 접근법 응모자 아이디를 돌면서 불량 사용자의 아이디와 일치하는 경우를 찾았다. dfs를 사용했다. 문자열을 비교하는 것은 정규표현식을 사용하였다. 중요한 포인트는 중복되는 경우들을 어떻게 처리하느냐였다. 시간이 좀 걸릴 것을 알았지만 데이터가 적었기 때문에 가능한 조합을 오름차순으로 나열해서 set에 넣었다 그러면 crodo frodo 가 되던 frodo..
-
[프로그래머스] 방문길이 (08.02)algorithm/프로그래머스 2020. 8. 2. 16:58
문제 https://programmers.co.kr/learn/courses/30/lessons/49994 코딩테스트 연습 - 방문 길이 programmers.co.kr 접근법 고려했던 것은 두 가지다. 1. 방문한 경로를 어떤 방식으로 체크할 것인가? 2. 지나친 경로의 중복 체크를 어떻게 할 것인가? 1번은 List를 사용했다. 출발하는 x,y 좌표 + 도착하는 x,y 좌표를 String 값으로 해서 List에 저장하고 경로를 체크했다. 2번은 경우에는 list의 contains 함수를 사용하였다. 만약 (0,0) -> (1,0) 의 경로에서 다시 (1,0) -> (0,0)로 갈 경우 두 번 이동했지만 처음 이동한 경로는 하나가 된다. 결국 내가 사용한 방법은 출발하는 x,y 좌표 + 도착하는 x,y..
-
[프로그래머스] 멀리 뛰기 (08.01)algorithm/프로그래머스 2020. 8. 1. 16:32
문제 https://programmers.co.kr/learn/courses/30/lessons/12914 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2�� programmers.co.kr 접근법 처음에 규칙을 찾으려고 했다. 총 1칸인 경우에는 1칸을 건너뛰는 방법 1가지 뿐이고 2칸일 경우 1칸을 두 번 뛰는 경우와 2칸을 한번에 뛰는 경우 2가지이다. 3칸일 때는 2칸을 뛰었을 때 1칸을 뛰는 경우의 수와 1칸을 뛰었을 때 2칸을 뛰는 경우의 수가 있다. 점화식을 도출해보면 d..
-
[프로그래머스] 가장 긴 팰린드롬 (07.31)algorithm/프로그래머스 2020. 7. 31. 15:13
문제 https://programmers.co.kr/learn/courses/30/lessons/12904 코딩테스트 연습 - 가장 긴 팰린드롬 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들 programmers.co.kr 접근법 팰린드롬이 되기 위해선 두 가지 경우의 수가 있다. aba 처럼 홀수개인 경우 abba 처럼 짝수개인 경우 checkOdd 메서드를 통해서 홀수개인 경우를 체크하고 checkEven 메서드를 통해서 짝수새인 경우를 체크한다. 그 경우 중의 큰 값이 asnwer에 저장되게 된다. 코드 class S..
-
[프로그래머스] 저울 (07.30)algorithm/프로그래머스 2020. 7. 30. 17:34
문제 https://programmers.co.kr/learn/courses/30/lessons/42886 코딩테스트 연습 - 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 합니다. 이 저울의 양팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같습니다. 또한, 저울의 한쪽에는 저울추들 programmers.co.kr 접근법 무게 1짜리 추로는 무게 1밖에 표현할 수 없다. 무게 1짜리 두 개의 추로는 1과 2를 표현할 수 있다. 무게 1짜리 두 개와 2짜리 한 개로는 1, 2, 3, 4 를 표현할 수 있다. 그러나 5는 표현할 수가 없다. 이미 사용할 수 있는 추들을 모두 사용하여 만든 최대의 무게에 +1을 하게 된다면 그 무게는 구할 수 없게 되는 것이다. 결국은 추들..
-
[프로그래머스] 입국심사 (07.29)algorithm/프로그래머스 2020. 7. 29. 19:01
문제 https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 � programmers.co.kr 접근법 정답이 될 수 있는 범위는 0 부터 times 배열의 최대값 * n 이 된다. 입출력 예시로 보면 심사하는데 걸리는 시간은 7과 10이 있다. 이때 6명의 사람을 심사하는데 최악의 경우는 모든 사람이 10이 걸리는 심사대에서 심사를 받는 것이다. 그렇게 되면 6 * 10, 즉 최대 60의 시간이 걸린다는 것을 알 수 있다. 그럼 정답은 0~60 사..
-
[프로그래머스] 이중우선순위큐 (07.28)algorithm/프로그래머스 2020. 7. 28. 16:53
문제 https://programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 접근법 단순하게 직관적으로 생각했다. 큐에 숫자가 삽입이 될때는 항상 정렬된 상태를 유지해야한다. 처음에는 우선순위큐를 사용했는데 힙에 삽입이 되듯이 정렬이 되어서 그냥 offer만 한 상태에서는 오름차순으로 정렬이 되지 않았다. 아직 우선순위 큐에 사용이 좀 미숙하다. 그래서 그냥 List를 정렬해가면서 풀었다. 삽입하고 삭제하는 연산이 많아서 LinkedList를 사용했다. for문 안에 또 정렬을 하면 시간복잡도가 높게 나오지 않을까 걱정했는데 생각보다 짧게 걸렸다. 코드 import java.util.*; class Solut..
-
[프로그래머스] 디스크 컨트롤러 (07.27)algorithm/프로그래머스 2020. 7. 28. 00:56
문제 https://programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를�� programmers.co.kr 접근법 우선 요청이 들어온 순서대로 정렬을 해준다. ( 그냥 단순히 작업이 짧은 순으로 정렬하면 아직 요청이 들어오지 않았는데도 실행할 수도 있기 때문에 ) 요청 시간 순으로 정렬이 된 상태에서 작업 시간이 짧은 순으로 우선순위 큐에 넣는다. 우선순위 큐에는 힙에 삽입이 되는 것처럼 데이터가 들어간다. index를 이용하여 작업을 꺼내고 time을..