Algorithm/문제 풀이62 [알고리즘] 보석쇼핑 투포인터 (2020 카카오 인턴십) 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 이것 또한 결국 못 풀었던 문제였다. 특정 조건을 만족하는 '구간'을 찾아야하는 문제이므로 투포인터기법을 활용해야한다. 만약 투포인터 기법을 활용하지 않고 찾게 된다면 O(N ^ 2)의 시간이 걸리게 된다. 투포인터 기법 활용 시 O(N) 시간 만에 찾을 수 있다. Solution 우선 HashMap을 만들어서 보석의 이름을 키값으로 count라는 객체를 만든다. 이 때 count의 사이즈는 총 보석 종류의 수가 된다. 반복문을 돌린다. 현재 구간에 포함된 보석 종류의 수를 나타내는 gem_count가 총 보석.. 2020. 8. 30. [알고리즘] 수식 최대화 (2020 카카오 인턴십) 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 � programmers.co.kr 상반기 카카오 인턴십 때 나온 문제이다. 해당 코딩 테스트에 참가했었기에 기억이 난다. (통과는 못했다.) 이 문제도 결국 못 풀었던 걸로 기억한다. 지금와서 다시 찬찬히 살펴보니 결국 문자열 처리 문제이다. 정확히 말하자면 '브루트 포스 + 문자열 처리' 문제라고 할 수 있겠다. 브루트 포스 문제인만큼 재귀 함수 사용은 필수적이다. 모듈은 크게 2개로 나누었는데 첫 번째는 '연산자 우선순위 결정' 메서드이고 나머지 하나는 '수식 계산' 메서드이다. 연산자.. 2020. 8. 29. [알고리즘] 찾기 KMP (백준 1786번) 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m번 문자가 차례로 � www.acmicpc.net 정확하게 KMP를 구현하는 문제다. 패턴 매칭 실패 시 패턴 인덱스 j 가 돌아갈 곳을 지정하는 failureFunction을 구하는 메서드와 그걸 이용해서 패턴 매칭을 하는 KMP 메서드로 이루어져있다. 주로 겹쳐져있는 패턴도 찾아낼 때에 사용한다. EX) 텍스트 : ababa, 패턴 : aba → 패턴 개수 : 2개 String.replace로는 찾아낼 수 없는 경우임 import java.io.BufferedReader; import java.io.. 2020. 8. 27. [알고리즘] 전화번호 목록 (백준 5052번) 5052번: 전화번호 목록 문제 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없� www.acmicpc.net 문자열 처리 문제인데 전화번호들의 일관성을 유지하려면 '한 번호가 다른 번호의 접두어인 경우가 없어야 한다' 라고 되어있다. 즉 911, 9112584 같은 경우엔 일관성이 없는 경우이다. 접두어 판별문제인만큼 Trie를 사용해야한다. Trie 자료구조에 관한 것은 알고리즘 설명 카테고리에 올라와 있을 것이다. Trie 클래스와 Node 클래스를 만들고 Trie 클래스에 String을 삽입하는 insertString() 메서드와 일관성 있는지 판별하는 isConsi.. 2020. 8. 26. 이전 1 ··· 11 12 13 14 15 16 다음
