Java/알고리즘 (51) 썸네일형 리스트형 [자바 알고리즘 인터뷰] 7장 배열 (2) 빗물 트래핑 https://leetcode.com/problems/trapping-rain-water/description/ - 높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지를 계산하라 풀이 1) 투 포인터를 최대로 이동 - 최대 높이의 막대까지 각각 좌우 막대 최대 높이 leftMax, rightMax가 현재 높이와의 차이만큼 물 높이 volume을 더해나간다. - 이 경우 적어도 낮은 쪽은 그만큼 항상 채워질것이기 때문에, 좌우 어느쪽이든 낮은 쪽은 높은 쪽을 향해서 포인터가 가운데로 점점 이동한다. - 오른쪽이 높다면 left+=1로 왼쪽 포인터가 이동하고, 왼쪽이 높다면 right-=1로 오른쪽 포인터가 이동한다. - 이렇게 하면 가장 높이가 높은 막대, 즉 '최대' 지점에서 좌우 포인터가 서로.. [자바 알고리즘 인터뷰] 7장 배열 (1) 두 수의 합 https://leetcode.com/problems/two-sum/description/ - 덧셈하여 타깃을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라 풀이 1) 브루트 포스로 계산 - 배열을 두 번 반복하면서 모든 조합을 더해서 일일이 확인해보는 무차별 대입 방식인 브루트 포스(Brute-Force)로 풀이 class Solution { public int[] twoSum(int[] nums, int target) { //입력값 배열을 처음부터 순회 for(int i=0; i [자바 알고리즘 인터뷰] 6장 문자열 처리(6) 가장 긴 팰린드롬 부분 문자열 https://leetcode.com/problems/longest-palindromic-substring/description/ - 가장 긴 팰린드롬 부분 문자열을 출력하라 풀이 1) 팰린드롬을 발견하면 확장하는 풀이 최장 공통 부분 문자열(Longest Common Substring) - 여러 개의 입력 문자열이 있을 때 서로 공통된 가장 긴 부분 문자열을 찾는 문제로, 다이나믹 프로그래밍으로 풀 수 있는 전형적인 문제 - 이 문제 또한 동일한 유형의 문제로서, 동일하게 다이나믹 프로그래밍으로 풀 수있다. - 그러나 이 문제의 경우 다이나믹 프로그래밍을 이용한 풀이는 직관적으로 이해가 어렵고, 실행속도가 느리다. - 그러므로 투 포인터(Tow Pointers)가 팰린드롬을 발견하면 확장하는 형태로 풀.. [자바 알고리즘 인터뷰] 6장 문자열 처리(5) 그룹 애너그램 https://leetcode.com/problems/group-anagrams/description/ - 문자열 배열을 받아 애너그램 단위로 그룹핑하라 풀이 1) 정렬하여 비교 - 애너그램을 이루는 단어들을 정렬하면 모두 같은 값을 갖게 된다. - 우선, 정렬한 값을 보관하기 위한 맵을 선언한다. - 하나의 키에 애너그램인 여러 개의 값이 추가될 수 있기 때문에 값은 리스트 형태가 되며, 따라서 맵은 리스트를 값으로 둔 형태로 선언한다. //애너그램 결과를 보관하기 위한 맵 선언 Mapresults = new HashMap(); - 입력값을 하나씩 순회하며 정렬한다. //입력값인 문자열 배열을 순회 for(String s : strs) { //문자열을 문자 배열로 변환 char[] chars = s.t.. [자바 알고리즘 인터뷰] 6장 문자열 처리(4) 가장 흔한 단어 https://leetcode.com/problems/most-common-word/description/ - 금지된 단어를 제외하고 가장 흔하게 등장하는 단어를 출력하라, 대소문자를 구분하지 않으며, 구두점(마침표, 쉼표 등)또한 무시한다. 풀이 1) 전처리 작업 후 개수 처리 및 추출 - 입력값에는 대소문자가 섞여 있으며 쉼표 등 구두점이 존재한다. - 따라서 데이터 클렌징(Data Cleansing)이라 부르는 입력값에 대한 전처리(Processing) 작업이 필요하다. - 정규식에서 \W는 단어 문자(Word Character)가 아닌 것을 뜻한다. - 단어 문자를 뜻할 때는 \w를 사용 - 문자 뒤에 +를 붙이면 연속적인 값을 의미한다. - \W+는 연속적으로 단어 문자가 아닌 값을 의미 rep.. [자바 알고리즘 인터뷰] 6장 문자열 처리(3) 로그 파일 재정렬 https://leetcode.com/problems/reorder-data-in-log-files/description/ - 로그 파일을 재정렬하라. 기준은 다음과 같다. 1) 로그의 가장 앞부분은 식별자로서, 순서에 영향을 끼치지 않는다. 2) 문자로 구성된 로그가 숫자 로그보다 앞에 오며, 문자 로그는 사전순으로 한다. 3) 문자가 동일할 경우에는 식별자순으로 한다. 4) 숫자 로그는 입력 순서대로 한다. 풀이 1) 문자 로그와 숫자 로그를 구분해 각각 처리 - 먼저 문자로 구성된 로그가 숫자 로그보다 이전에 오며, 숫자 로그는 입력 순서대로 둔다. - 문자 로그와 숫자 로그는 서로 정렬 방식이 다르므로, 둘을 분리해 정렬하고 나중에 결과를 서로 이어붙이는 방식으로 풀이 - 먼저 로그에서 각각의 종.. [자바 알고리즘 인터뷰] 6장 문자열 처리(2) 문자열 뒤집기 https://leetcode.com/problems/reverse-string/description/ - 문자열을 뒤집는 함수를 작성하라, 입력값은 문자 배열이며, 리턴없이 입력 배열 내부를 직접 조작하라 풀이 1) 문자 배열로 스왑 - 서로 중앙으로 나아가다 겹치는 지점에 도달하면 종료하는 형태 - 스왑을 통해 배열 내부의 값을 변경 class Solution { public void reverseString(char[] s) { int start = 0; int end = s.length-1; //서로 중앙으로 이동해 나가다 겹치는 지점에 도달하면 종료 while(start [자바 알고리즘 인터뷰] 6장 문자열 처리(1) 유효한 팰린드롬 https://leetcode.com/problems/valid-palindrome/description/ - 주어진 문자열이 팰린드롬인지 확인하라. 대소문자를 구분하지 않으며, 영숫자(영문자와 숫자)만을 대상으로 한다. 풀이 1) 문자 단위로 추출해서 처리 - Character 클래스에는 원시 자료형 char를 입력값으로 하여 모두 소문자로 변경해주는 toLowerCase() 메소드와 영숫자인지 판별해주는 isLetterOrDigit() 메소드가 모두 존재한다. ex) Character.toLowerCase('G'); //'g' Character.isLetterOrDigit('G'); //true - 문자열에서 맨앞의 문자와 맨 뒤의 문자를 추출한 다음 유효한 문자(영숫자)인지를 확인하고 모두 소문자로.. 이전 1 ··· 3 4 5 6 7 다음
