[인터뷰] 자주 사용되는 코딩 패턴

안녕하세요, 인터뷰에서 자주 나오거나 사용되는 20가지 코딩 패턴에 대해 자세히 설명하겠습니다.

1. Two Pointers - 투 포인터 

투 포인터 알고리즘(기법)은 말 그대로 두 개의 포인터를 이용해 문제를 해결하는 알고리즘을 뜻합니다.

보통 특정 조건을 만족하는 배열 내의 쌍이나 배열을 찾아야 할 때 또는 정렬된 배열에서 특정 요소를 찾을 때 사용됩니다.

DSA: Array, String, LinkedList

문제를 해결하는 예시

1. 정렬된 배열이나 정렬되지 않은 배열에서 목표 합계를 이루는 숫자 쌍을 찾기

입력: [3,5,2,8,11], 목표 합계 = 10
출력: [2, 8]

자바 코드

import java.util.Arrays;

public class TwoPointerSum {
    public static int[] findPairWithTargetSum(int[] nums, int target) {
        Arrays.sort(nums); // 배열을 정렬합니다. (정렬되지 않은 배열의 경우에만 필요)

        int left = 0; // 왼쪽 포인터 초기화
        int right = nums.length - 1; // 오른쪽 포인터 초기화

        while (left < right) {
            int currentSum = nums[left] + nums[right];
            
            if (currentSum == target) {
                // 목표 합계를 이루는 쌍을 찾았습니다.
                return new int[]{nums[left], nums[right]};
            } else if (currentSum < target) {
                // 현재 합계가 목표 합계보다 작으면 왼쪽 포인터를 오른쪽으로 이동합니다.
                left++;
            } else {
                // 현재 합계가 목표 합계보다 크면 오른쪽 포인터를 왼쪽으로 이동합니다.
                right--;
            }
        }
        
        // 쌍을 찾지 못한 경우 실패를 나타내기 위해 빈 배열 또는 null을 반환합니다.
        return new int[0]; // 또는 return null;
    }

    public static void main(String[] args) {
        int[] input = {3, 5, 2, 8, 11};
        int targetSum = 10;
        int[] result = findPairWithTargetSum(input, targetSum);

        if (result.length == 2) {
            System.out.println("목표 합계를 이루는 쌍을 찾았습니다: [" + result[0] + ", " + result[1] + "]");
        } else {
            System.out.println("목표 합계를 이루는 쌍을 찾지 못했습니다.");
        }
    }
}

 

2. 주어진 문자열에서 가장 긴 Palindrome 부분 문자열을 찾기

입력: "babad"
출력: "bab"

 

자바 코드

public class LongestPalindromeSubstring {
    public static String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
        
        int start = 0;
        int end = 0;
        
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i); // 홀수 길이의 팰린드롬 검사
            int len2 = expandAroundCenter(s, i, i + 1); // 짝수 길이의 팰린드롬 검사
            int len = Math.max(len1, len2);
            
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        
        return s.substring(start, end + 1);
    }
    
    private static int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
    
    public static void main(String[] args) {
        String input = "babad";
        String result = longestPalindrome(input);
        System.out.println("입력: \"" + input + "\"");
        System.out.println("출력: \"" + result + "\"");
    }
}

 

3. 주어진 배열의 최대 합 부분 배열을 찾기

입력: [-2,1,-3,4,-1,2,1,-5,4]

출력: [4,-1,2,1]

public class MaximumSubarray {
    public static int[] findMaximumSubarray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }

        int maxSum = nums[0];
        int currentSum = nums[0];
        int start = 0;
        int end = 0;
        int tempStart = 0;

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > currentSum + nums[i]) {
                currentSum = nums[i];
                tempStart = i;
            } else {
                currentSum += nums[i];
            }

            if (currentSum > maxSum) {
                maxSum = currentSum;
                start = tempStart;
                end = i;
            }
        }

        int[] result = new int[end - start + 1];
        for (int i = start; i <= end; i++) {
            result[i - start] = nums[i];
        }

        return result;
    }

    public static void main(String[] args) {
        int[] input = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int[] result = findMaximumSubarray(input);

        System.out.print("[");
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i]);
            if (i < result.length - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("]");
    }
}

4. 두 정렬된 배열의 교집합을 찾기

입력: [1,3,4,5,7], [2,3,5,6]

출력: [3,5]

import java.util.ArrayList;
import java.util.List;

public class IntersectionOfSortedArrays {
    public static List<Integer> findIntersection(int[] arr1, int[] arr2) {
        List<Integer> result = new ArrayList<>();
        
        int pointer1 = 0;
        int pointer2 = 0;
        
        while (pointer1 < arr1.length && pointer2 < arr2.length) {
            if (arr1[pointer1] == arr2[pointer2]) {
                result.add(arr1[pointer1]);
                pointer1++;
                pointer2++;
            } else if (arr1[pointer1] < arr2[pointer2]) {
                pointer1++;
            } else {
                pointer2++;
            }
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        int[] arr1 = {1, 3, 4, 5, 7};
        int[] arr2 = {2, 3, 5, 6};
        
        List<Integer> intersection = findIntersection(arr1, arr2);
        
        System.out.println("Intersection: " + intersection);
    }
}

 

2.  Fast & Slow Pointers

DSA에서는 연결 리스트, 배열 또는 다른 데이터 구조를 다루는 문제를 해결하는 데 사용됩니다. 여기서는 데이터를 특정한 방법으로 반복해야 할 때 사용됩니다. 빠른 포인터와 느린 포인터 기술을 두 개의 포인터를 사용하는데, "느린" 포인터와 "빠른" 포인터가 있습니다. 느린 포인터는 한 번에 한 걸음씩 움직이고, 빠른 포인터는 한 번에 두 걸음씩 움직입니다.

 

DSA: Array, String, LinkedList

문제를 해결하는 예시

1. 연결 리스트에서 사이클 감지 

입력: 1 -> 2 -> 3 -> 4 -> 5 -> 2

출력: True

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    
    ListNode slow = head;
    ListNode fast = head;
    
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        
        if (slow == fast) {
            return true; // 사이클 감지
        }
    }
    
    return false; // 사이클 없음
}

2. 연결 리스트의 중간 요소 찾기:

입력: 1 -> 2 -> 3 -> 4 -> 5

출력: 3

public ListNode findMiddle(ListNode head) {
    if (head == null) {
        return null;
    }
    
    ListNode slow = head;
    ListNode fast = head;
    
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    return slow;
}

3. 두 연결 리스트의 교차점 찾기

입력: 1 -> 2 -> 3 -> 4 -> 5, 8 -> 4 -> 5

출력: 4

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode a = headA;
    ListNode b = headB;
    
    while (a != b) {
        a = (a == null) ? headB : a.next;
        b = (b == null) ? headA : b.next;
    }
    
    return a; // 교차점 노드 또는 교차점이 없으면 null 반환
}

4. 연결 리스트에서 k번째 뒤에서부터 요소 찾기

입력: 1 -> 2 -> 3 -> 4 -> 5, k = 2

출력: 4

public ListNode findKthToLast(ListNode head, int k) {
    if (head == null || k <= 0) {
        return null;
    }
    
    ListNode slow = head;
    ListNode fast = head;
    
    // 빠른 포인터를 k 노드만큼 이동
    for (int i = 0; i < k; i++) {
        if (fast == null) {
            return null; // 리스트 길이가 k보다 짧음
        }
        fast = fast.next;
    }
    
    // 빠른 포인터가 끝에 도달할 때까지 두 포인터를 이동
    while (fast != null) {
        slow = slow.next;
        fast = fast.next;
    }
    
    return slow; // 뒤에서 k번째 요소
}

 

3.  Sliding Window

이것은 특정한 합이나 곱을 가지거나 특정한 패턴이나 문자를 포함하는 하위 배열 또는 부분 문자열을 찾아야 하는 상황에서 사용됩니다. 또한 입력 데이터는 특정한 창 크기 내에 있어야 합니다.

 

DSA: Array, String, LinkedList

문제를 해결하는 예시

1. 주어진 크기의 배열에서 최대 또는 최소 합 부분 배열 찾기

입력: [1, 4, 2, 10, 2, 3, 1, 0], k=3

출력: 15

public int findMaxSumSubarray(int[] nums, int k) {
    int maxSum = 0;
    int currentSum = 0;

    for (int i = 0; i < k; i++) {
        currentSum += nums[i];
    }

    maxSum = currentSum;

    for (int i = k; i < nums.length; i++) {
        currentSum += nums[i] - nums[i - k];
        maxSum = Math.max(maxSum, currentSum);
    }

    return maxSum;
}

2. 중복 문자가 없는 가장 긴 부분 문자열 찾기.

입력: "abcabcbb"

출력: "abc"

public String findLongestSubstring(String s) {
    int[] charIndex = new int[256];
    Arrays.fill(charIndex, -1);
    int maxLength = 0;
    int start = 0;

    for (int end = 0; end < s.length(); end++) {
        if (charIndex[s.charAt(end)] >= start) {
            start = charIndex[s.charAt(end)] + 1;
        }
        charIndex[s.charAt(end)] = end;
        maxLength = Math.max(maxLength, end - start + 1);
    }

    return s.substring(start, start + maxLength);
}

3. 문자열에서 패턴 또는 부분 문자열의 첫 번째 발생 찾기.

입력: s= "hello world" , pat= "world"

출력: 6

public int findFirstOccurrence(String s, String pat) {
    int[] patCount = new int[256];
    int[] sCount = new int[256];

    for (char c : pat.toCharArray()) {
        patCount[c]++;
    }

    int left = 0;
    for (int right = 0; right < s.length(); right++) {
        char rightChar = s.charAt(right);
        sCount[rightChar]++;

        while (sCount[rightChar] > patCount[rightChar]) {
            char leftChar = s.charAt(left);
            sCount[leftChar]--;
            left++;
        }

        if (right - left + 1 == pat.length()) {
            return left;
        }
    }

    return -1;
}

4. 다른 문자열의 모든 문자를 포함하는 문자열에서 가장 작은 창 찾기.

입력: s1= "this is a test string" , s2= "tist"

출력: "tist"

public String findSmallestWindow(String s1, String s2) {
    int[] s1Count = new int[256];
    int[] s2Count = new int[256];

    for (char c : s2.toCharArray()) {
        s2Count[c]++;
    }

    int left = 0;
    int minLen = Integer.MAX_VALUE;
    int startIndex = -1;
    int count = 0;

    for (int right = 0; right < s1.length(); right++) {
        char rightChar = s1.charAt(right);
        s1Count[rightChar]++;

        if (s1Count[rightChar] <= s2Count[rightChar]) {
            count++;
        }

        if (count == s2.length()) {
            while (s1Count[s1.charAt(left)] > s2Count[s1.charAt(left)] || s2Count[s1.charAt(left)] == 0) {
                if (s1Count[s1.charAt(left)] > s2Count[s1.charAt(left)]) {
                    s1Count[s1.charAt(left)]--;
                }
                left++;
            }

            int windowLen = right - left + 1;
            if (windowLen < minLen) {
                minLen = windowLen;
                startIndex = left;
            }
        }
    }

    if (startIndex == -1) {
        return "";
    }

    return s1.substring(startIndex, startIndex + minLen);
}