본문 바로가기

알고리즘

[PS] TwoSum Two Sum 문제 설명 문제는 간단 정수 배열과 target 이 들어오고 배열 중 2개의 요소 합이 target 을 만족하면 두 값의 인덱스를 출력하는 것 조건은 배열안에 무조건 만족하는 솔루션이 하나는 있고 똑같은 요소를 두번 사용하는 경우는 없다는 것 해결 1. 부르트 포스 public int[] twoSumEasy(int[] nums, int target) { for(int i = 0; i < nums.length; i++) { for(int j = i; j < nums.length; j++) { if(i==j) continue; if(nums[i] + nums[j] == target) { return new int[]{i,j}; } } } return new int[]{-1,-1}; } 티스토리..
[PS] Meeting Rooms(Medium) solution in JAVA Meeting Rooms2 문제 회의시간이 주어지면 총 사용해야하는 회의실이 최소 몇개인가를 구하는 문제이다. Easy 만큼 쉬운줄알고 정렬하고 그냥 막 풀었다가 아차 싶었다. 처음에 접근한 방법은 Map 에 모든 시간 데이터를 넣고 겹치는 시간을 넣은 List 의 사이즈를 비교하는방법이었는데 아니 무슨 미팅룸 시간이라면서 10만자리 대의 숫자를 input 으로 주길래 시간초과로 실패했다. 리트코드의 단점이 아닐까 input 의 사이즈가 명시되지 않는 문제들이 있는것 PQ 를 쓰면 시간내에 들어올 수 있다. 코드를 보여주고 그림으로 설명하겠다. public Interval[] convert(int[][] arr) { return Arrays.stream(arr) .map(it -> new Interval..
[PS] Meeting Rooms(Easy) Solution in Java Meeting Room 이지 버전 풀이이다. MergeIntervals 풀이를 보고오면 매우 쉽다. public class MeetingRooms { public boolean canAttendMeetings(int[][] intervals) { Arrays.sort(intervals, (o1, o2) -> { return o1[0] == o2[0] ? Integer.compare(o1[1], o2[1]) : Integer.compare(o1[0], o2[0]); }); new ArrayList(); for(int i = 0; i intervals[i + 1][0]) { return false; } } retu..
[PS] MergeIntervals Solution in Java Leetcode MergeIntervals Solution 문제설명 불규칙하게 들어오는 배열의 범위를 Merge 한 배열을 찾는 것 Input [[1,3],[2,6],[8,10],[15,18]] Output [[1,6],[8,10],[15,18]] Input Output 설명 1,3과 2,6 은 겹치는 구간이 있으므로 merge 된것 코드 public class MergeIntervals { //javaxf Pair doesn't work at leetcode TT class Pair { Integer key; Integer value; public Pair(Integer key, Integer value) { this.key = key; this.value = value; } public Integer..
[Algorithm] 슬라이딩 윈도우(Sliding Window) 알고리즘 슬라이딩 윈도우 알고리즘 슬라이딩 윈도우 알고리즘은 윈도우 즉 일정한 범위를 가지고 있는 것을 유지하면서 이것을 이동(sliding) 하는 것이다. 예를들어 2가지 긴 문자열이 주어지고 알파벳 2개만을 포함하는 가장 긴 문자열을 찾아보는 문제가 있다, 이 문제를 슬라이딩 알고리즘을 이용하여 풀면 다음과 같이 파란색으로 칠해진 영역이 윈도우가 되고 이를 하나씩 밀게 되는 것이다. 그림의 Right 를 하나씩 움직이면 되는데 Right 가 C 를 가리키면 다음 포함하는 문자열이 3개가 되므로 윈도우가 더이상 확장 되지 않고 다음 윈도우로 움직인다. 이런식으로 움직이게 되는 것이다. 마찬가지로 D로 움직이면 CD 만 포함하게 되는것이다. Max lenght 를 값으로 가지면서 윈도우를 옮길 수 있는데 윈도우의..

티스토리툴바