지니로그

백준 xxxx. 

https://www.acmicpc.net/problem/3273

Key Point

투 포인터
정렬

Git

https://github.com/dev-jinius/Algorithm-Practice

처음 풀이 시도

( 40 min / 성공 )

• 문제를 보고 초등학생 때 배웠던 가우스 덧셈 방식이 떠올랐다. 1 ~ 100까지 덧셈을 가장 빨리 구했다는..
  • 어떻게? 이미 1~100은 정렬되어 있어 (1+100), (2+99), (3+98) .. (49+52) (50+51) 이런식으로 짝지어서 50쌍이 만들어지니까 101 * 50 = 5050
  • 이 문제도 1 ~ 100 덧셈처럼 무조건 등차수열은 아니기 때문에 딱 떨어지지 않을 수 있다. 그래도 앞뒤로 짝지어서 시간복잡도 O(n)으로 구할 수 있다.
• 먼저 주어진 숫자들을 자료구조 리스트에 넣고 정렬을 했다.
• 리스트 맨앞에서부터 탐색하는 포인터 p1과 맨뒤에서부터 탐색하는 포인터 p2를 두고, 포인터를 움직이면서 짝을 지어 합한다. => 투 포인터 사용

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(scanner.nextInt());
        }

        int target = scanner.nextInt();
        scanner.close();

        Collections.sort(list);

        int p1 = 0;
        int p2 = n-1;
        int count = 0;
        while (p1 < p2) {
            int n1 = list.get(p1);
            int n2 = list.get(p2);
            if (n1+n2 > target) {
                p2--;
                continue;
            }
            if (n1+n2 < target) {
                p1++;
                continue;
            }

            p1++;
            p2--;
            count++;
        }

        System.out.println(count);
    }
}

백준 1931. 회의실 배정

https://www.acmicpc.net/problem/1931

Key Point

정렬, 그리디 알고리즘
- 최적의 해 구하기
- 종료 시간이 빠른 순서대로 회의를 선택하면 더 많은 회의를 배정할 수 있어서 그리디 알고리즘의 핵심!

Git

https://github.com/dev-jinius/Algorithm-Practice

처음 풀이 시도

(1hour over / 시간 초과로 실패)

• 주어진 회의 시간에서 시작시간이 같다면, 종료시간이 더 작은 미팅을 Map에 넣었다.
• TreeMap을 사용한 이유는 정렬을 사용하기 위해서이다.
  • TreeMap은 내부적으로 SortedMap을 상속받은 NavigableMap 인터페이스를 implement 하기 때문에 정렬이 되어 있는 자료구조이다.
  • 정렬을 사용한 이유는 회의 시작시간과 종료시간을 비교해 가능한 빠른 종료시간을 찾아서 최대한 많은 회의를 배정하기 위함이다.
• 아래 코드는 시간 초과로 실패했다.
  
  • Map에 있는 모든 회의를 순서대로 한개씩 꺼내서 최적의 해를 찾는 알고리즘이다.
  • 가능한 모든 조합을 탐색하기 때문에 시간복잡도는 O(n!) 이 된다. 

import java.util.*;

public class Main {
    private static int n;
    private static int count;
    public static void counting(Map<Integer, Integer> map, int endTime, int cnt) {
        for (Integer key : map.keySet()) {
            if (key < endTime) continue;
            counting(map, map.get(key), cnt+1);
        }

        if (count < cnt) count = cnt;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        count = 0;
        n = Integer.parseInt(scanner.nextLine());
        Map<Integer, Integer> map = new TreeMap<>();
        int start = 0;
        int end = 0;
        for (int i = 0; i < n; i++) {
            String line = scanner.nextLine();
            start = Integer.parseInt(line.split(" ")[0]);
            end = Integer.parseInt(line.split(" ")[1]);

            if (!map.containsKey(start)) {
                map.put(start, end);
            }
            if (map.get(start) > end) {
                map.put(start, end);
            }
        }
        n = map.size();

        for (Integer key : map.keySet()) {
            counting(map, map.get(key), 1);
        }

        System.out.println(count);
    }
}

그리디 알고리즘 풀이

• 종료 시간이 빠른 순서대로 정렬을 한다.
  • 더 많은 회의를 배정할 수 있다.
  • " 이전 회의의 종료 시간 이후에 시작하는 회의만 선택 " 함으로써 중복 배정을 방지할 수 있다.
  • Java의 Comparable<T> 제네릭 인터페이스는 특정 객체를 비교할 수 있는 기능을 제공하며, 타입 안정성이 있다.
  • Collections.sort()는 리스트 정렬을 한다. 리스트 요소들이 Comparable<T>를 상속받아 compareTo() 메서드를 통해 비교 기준에 따라 정렬을 할 수 있다.
• 시간복잡도는 O(nlogn)이다.
  • Collections.sort()는 Timsort 알고리즘을 사용해 대부분의 정렬 알고리즘은 O(nlogn) 시간복잡도를 가진다.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    static class Time implements Comparable<Time> {
        int start;
        int end;

        public Time(int start, int end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public int compareTo(Time o) {
            if (this.end == o.end) {
                return this.start - o.start;
            }
            return this.end - o.end;
        }
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        List<Time> timeList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int start = scan.nextInt();
            int end = scan.nextInt();
            timeList.add(new Time(start, end));
        }

        Collections.sort(timeList);

        int count = 0;
        int endTime = 0;

        for (Time time : timeList) {
            if (time.start >= endTime) {
                endTime = time.end;
                count++;
            }
        }
        System.out.println(count);
    }
}

오늘의 학습 키워드

그리디 알고리즘

알고리즘 문제

LeetCode Medium - 1338. Reduce Array Size to The Half

공부한 내용

그리디 알고리즘

• 최적해를 구하는 알고리즘
• 전체 최적해를 구하기 위해 각 단계에서 최선의 선택을 한다.
• 문제를 해결하는 과정에서 현재 상황에서의 최적의 해법을 찾는 과정을 반복하며 최종 해답을 도출한다.

오늘의 회고

처음 시도

• 완전 탐색을 해야해서 DFS를 사용해야 하나 생각했다. 
  • 문제1. 배열 최대 크기가 10^5인데, 모두 탐색하면 2^10^5 = 1,125,899,906,842,624 번을 탐색해야 한다.
  • 문제2. DFS로 최적의 해를 찾더라도, 다시 돌아와서 다른 경로를 탐색하면 최적의 해를 놓칠 수 있다.

해결

• 그리디 알고리즘으로 가장 빈도수가 많은 숫자부터 주어진 배열의 전체 길이의 반이 될때까지 빈도수를 더해서 답을 구할 수 있다.

문제 풀이

import java.util.*;

class Solution {
    public int minSetSize(int[] arr) {
        int len = arr.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int n : arr) {
            map.put(n, map.getOrDefault(n, 0)+1);
        }
        List<Integer> values = new ArrayList<>(map.values());
        Collections.sort(values);

        int res = 0, sum = 0;
        for (int i = values.size()-1; i >= 0; i--) {
            sum += values.get(i);
            res++;

            if (sum >= Math.round(len/2)) break;
        }

        return res;
    }

오늘의 학습 키워드

힙
우선순위 큐

알고리즘 문제

• LeetCode Medium. 1845. Seat Reservation Manager

공부한 내용

PriorityQueue

오늘의 회고

처음 시도

• 처음엔 "데이터를 추가하고 꺼내야 한다." 는 생각으로 stack, queue를 생각하다가 "숫자가 작은 순서대로 꺼내야 한다." 조건에서 priorityQueue로 풀어야겠다고 생각했다. 

해결

• 자료구조를 바로 생각해내고, 15분 이내로 풀어서 성공적인 느낌!
• 입력 값인 n만큼 큐에 좌석(숫자)를 넣어놓고, 예약하면 큐에서 꺼내고 예약 취소 시 매개변수인 좌석 번호를 다시 큐에 넣는다.

문제 풀이

import java.util.*;

class SeatManager {
    private PriorityQueue<Integer> queue;
    public SeatManager(int n) {
        this.queue = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            queue.offer(i+1);
        }
    }
    
    public int reserve() {
        return queue.poll();
    }
    
    public void unreserve(int seatNumber) {
        queue.offer(seatNumber);
    }

오늘의 학습 키워드

Stack
Queue

알고리즘 문제

LeetCode Medium. 341. Flatten Nested List Iterator

공부한 내용

Queue, 재귀 함수를 활용

오늘의 회고

• 갈수록 문제 해결 시간이 빨라지고, 스스로 해결할 수 있는 문제도 많아져서 좋다.
• 처음에 재귀 함수를 만들어서 푸는 문제가 이해가 되지도 않고 어려웠는데, 이제는 어떤 느낌인지 조금은 감이 오는 것 같다. => 어떤느낌? 배열/리스트, 큐/스택 자료구조를 사용하면서 같은 Format의 형태를 탐색해야 한다거나 등등.

처음 시도

• 주어진 nestedList를 보면 숫자와 숫자로 된 리스트가 섞여있는데, 차례대로 숫자 배열로 반환하는 게 목표였다.
• nestedList 형태를 봤을 때, NestedInteger 타입으로 되어 있고, NestedInteger는 숫자 또는 리스트 형태로 된 걸 확인했을 때, 아! 반복해서 nestedList를 순서대로 꺼내서 Integer로 된 큐에 담아야 겠다고 생각했다.
• 같은 형태의 반복, Integer를 담을 큐, 순서대로 반복 => DFS 방식으로 풀면 좋겠다!

해결

• 주어진 nestedList를 순서대로 꺼내서 Integer 타입이면 바로 Queue에 넣고, List 타입이면 다시 순서대로 꺼내서 Queue에 넣는 것을 반복하는 재귀 함수를 사용한 DFS 방식으로 풀었다.

문제 풀이

내가 푼 풀이 (Queue + DFS 방식)

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return empty list if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
import java.util.*;

public class NestedIterator implements Iterator<Integer> {
    private Queue<Integer> queue;
    public NestedIterator(List<NestedInteger> nestedList) {
        this.queue = new LinkedList<>();
        reculsive(nestedList);
    }

    public void reculsive(List<NestedInteger> list) {
        for (int i = 0; i < list.size(); i++) {
            if (!list.get(i).isInteger()) {
                reculsive(list.get(i).getList()); 
            } else {
                queue.offer(list.get(i).getInteger());
            }
        }
    }

    @Override
    public Integer next() {
        return queue.poll();
    }

    @Override
    public boolean hasNext() {
        return !queue.isEmpty();
    }
}

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i = new NestedIterator(nestedList);
 * while (i.hasNext()) v[f()] = i.next();
 */

다른 풀이 (Stack + DFS 방식)

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return empty list if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
public class NestedIterator implements Iterator<Integer> {
    private LinkedList<NestedInteger> stack; // Stack to keep track of NestedInteger objects

    public NestedIterator(List<NestedInteger> nestedList) {
        stack = new LinkedList<>();
        // Push nestedList elements in reverse order onto the stack
        for (int i = nestedList.size() - 1; i >= 0; i--) {
            stack.push(nestedList.get(i));
        }
    }

    @Override
    public Integer next() {
        return stack.pop().getInteger(); // Return the integer from the top of the stack
    }

    @Override
    public boolean hasNext() {
        while (!stack.isEmpty()) {
            NestedInteger curr = stack.peek();
            if (curr.isInteger()) {
                return true; // Found an integer
            }

            // Flatten nested list
            stack.pop(); // Remove the list
            for (int i = curr.getList().size() - 1; i >= 0; i--) {
                stack.push(curr.getList().get(i)); // Push its elements in reverse order
            }
        }
        return false; // No more integers
    }
}

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i = new NestedIterator(nestedList);
 * while (i.hasNext()) v[f()] = i.next();
 */

오늘의 학습 키워드

문자열

알고리즘 문제

LeetCode Medium 451. Sort Characters By Frequency

공부한 내용

문자열, 정렬

오늘의 회고

처음 시도

• 처음에 문제를 잘못 이해해서, 연속된 문자열을 순서를 바꿔서 출력하는 것으로 생각했다...

해결

• frequency라는 키워드를 확인하고 빈도수와 관련있다는 것을 나중에 알았고, 다시 자료구조를 HashMap으로 생각하고 짰다.
• 어찌어찌 풀긴 풀었는데 너무 느린 코드였다

문제 풀이

잘못 이해해서 만든 코드

import java.util.*;

class Solution {
    Queue<String> queue;
    String s;
    int len;
    int count;
    char current;

    public void dfs(String str, char c, int index) {
        if (index == 0) {
            queue.offer(str);
            return;
        }
        if (s.charAt(index-1) != current) {
            queue.offer(str);
            str = s.substring(index-1, index);
            current = s.charAt(index-1);
        } else {
            str += s.substring(index-1, index);
        }       
        
        dfs (str, current, index-1);
    }

    public String frequencySort(String s) {
        this.queue = new LinkedList<>();
        this.s = s;
        this.len = s.length();
        this.current = s.charAt(len-1);
        dfs(s.substring(len-1), current, len-1);

        String result = "";
        while (!queue.isEmpty()) {
            result += queue.poll();
        }

        return result;
    }
}

풀긴 풀었는데 성능이 안좋은 코드

import java.util.*;

class Solution {
    Map<Character, Integer> map;
    List<Map.Entry<Character, Integer>> entryList;
    String s;
    int len;

    public void counting() {
        char c;
        int index = 0;
        int count = 0;
        for (int i = 0; i < len; i++) {
            c = s.charAt(i);
            index = 0;
            count = map.containsKey(c) ? map.get(c)+1 : 1;
            map.put(c, count);
        }
    }
    
    public void ranking() {
        this.entryList = new LinkedList<>(map.entrySet());
        entryList.sort(new Comparator<Map.Entry<Character, Integer>>() {
            @Override
            public int compare(Map.Entry<Character, Integer> o1, Map.Entry<Character, Integer> o2) {
                return o2.getValue() - o1.getValue();
            }
        });
    }

    public String makeString() {
        String str = "";
        for (Map.Entry<Character, Integer> entry : entryList) {
            for (int i = 0; i < entry.getValue(); i++) {
                str += entry.getKey();
            }
        }
        return str;
    }

    public String frequencySort(String s) {
        this.map = new HashMap<>();
        this.s = s;
        this.len = s.length();

        counting();
        ranking();
        return makeString();
    }
}

다른 사람 풀이 1

class Solution {
    public String frequencySort(String s) {
        int[] arr = new int[128];
        char[] sh = s.toCharArray();

        for (char ch : sh) { arr[ch] += 1; }

        int index = 0;
        while(index < sh.length) {
            char ch = ',';
            for (int j = 0; j < 128; j++) {
                if (arr[j] > arr[ch]) {
                    ch = (char) j;
                }
            }
            while (arr[ch] != 0) {
                sh[index++] = ch;;
                arr[ch]--;
            }
        }

        return new String(sh);
    }
}

다른 사람 풀이2

class Solution {
    public String frequencySort(String s) {
        StringBuilder sb = new StringBuilder();
        HashMap<Character,Integer> map1 = new HashMap<>();
        for(int i=0;i<s.length();i++){
            char ch = s.charAt(i);
            map1.put(ch,map1.getOrDefault(ch,0)+1);
        }
        Integer arr[] = new Integer[map1.size()];
        int k = 0;
        for(char ch : map1.keySet()){
            arr[k] = map1.get(ch);
            k++;
        }
        Arrays.sort(arr, Collections.reverseOrder());
        Queue<Character> q = new LinkedList<>();
        for(char ch : map1.keySet()){
            q.add(ch);
        }
        // HashMap<Integer,Character> map2 = new HashMap<>();
        // for(char ch : map1.keySet()){
        //     map2.put(map1.get(ch),ch);
        // }
        // for(char ch : map1.keySet()){
        //     sb.append(ch);
        // }


        for(int i=0;i<arr.length;i++){
            while(arr[i] != map1.get(q.peek())){
                char ch = q.remove();
                q.add(ch);
            }
            char ch1 = q.peek();
            for(int j=0;j<arr[i];j++){
                sb.append(ch1);
            }
            char ch = q.remove();
            q.add(ch);
            // if(map2.containsKey(arr[i])){
            //     for(int j=0;j<arr[i];j++){
            //         sb.append(map2.get(arr[i]));
            //     }
            // }
        }
        // while(!q.isEmpty()){
        //     sb.append(q.remove());
        // }
        return sb.toString();
    }
}

오늘의 학습 키워드

DFS
Combination

알고리즘 문제

LeetCode Medium 1286. Iterator for Combination

공부한 내용

오늘은 스스로 생각한 DFS를 활용해서 처음부터 끝까지 혼자힘으로 풀었다. 너무 기분이 좋다!

오늘의 회고

처음 시도

• 주어진 문자열의 한 문자씩 모두 탐색해서 원하는 길이의 문자열을 만드는(조합하는) 문제였기 때문에 DFS로 문자열의 0번 인덱스부터 마지막 인덱스까지 순서대로 조합을 찾는 방법을 생각했다.
  • 문제에서 이미 오름차순으로 정렬된 문자열이 주어지기 때문에 앞에서부터 순서대로 자신의 이후 인덱스부터 차례로 조합하면서 모든 조합을 찾을 수 있다.
• DFS로 생각했고, 큐(Queue) 자료구조를 사용해 조합한 문자열을 큐에 넣고, 오름차순으로 정렬되서 이미 큐에 들어가기 때문에 그대로 앞에서부터 꺼내면 된다.
• 그 다음으로 재귀 종료 조건을 생각해야 하는데 반복하면서 문자열에 1씩 증가하는 인덱스의 값을 더할때마다 카운팅을 하면서 원하는 문자열 길이만큼 조합을 만들고, 원하는 문자열 길이만큼 카운팅이 되었을 때 return하도록 생각했다.

해결

• DFS 알고리즘과 Queue 자료구조로 해결했다!

문제 풀이

import java.util.*;

class CombinationIterator {
    private String characters;
    private int len;
    private Queue<String> queue;

    public CombinationIterator(String characters, int combinationLength) {
        this.characters = characters; 
        this.len = combinationLength;
        this.queue = new LinkedList<>();
        for (int i = 0; i < characters.length(); i++) {
            dfs(characters.substring(i,i+1), i, 1);
        }
    }
    
    public void dfs(String str, int index, int count) {
        if (count == len) {
            queue.offer(str);
            return;
        }

        for (int i = index+1; i < characters.length(); i++) {
            dfs(str+characters.substring(i,i+1), i, count+1);
        }
    }

    public String next() {
        return queue.poll();
    }
    
    public boolean hasNext() {
        return !queue.isEmpty();
    }
}

/**
 * Your CombinationIterator object will be instantiated and called as such:
 * CombinationIterator obj = new CombinationIterator(characters, combinationLength);
 * String param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */

오늘의 학습 키워드

배열

알고리즘 문제

• LeetCode Medium 1282. Group the People Given the Group Size They Belong To
• https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/description/?source=submission-ac

공부한 내용

다른 풀이를 보고 분석

오늘의 회고

처음 시도

• 처음 내가 시도했던 방식은 List만을 사용해서 풀었다.
  1. groupSizes 배열 전체 요소를 하나씩 읽어서 size만큼 새로운 List에 담아서 그룹핑을 한다.
  2. 그룹 배열을 만들 때, 그룹에 담은 groupSizes 해당 요소는 0으로 만든다.
  3. 카운트 변수를 두어 size만큼 카운트가 되면 다음 요소로 넘어가도록 했다.
• 그런데 내가 어렵게 꼬아서 생각한 것 같았다. 여기까지는 좋았는데.. 왜 처음에 괜히 어렵게 재귀로 풀려고 했었는지 런타임 에러나고, 케이스마다 안되는 게 생기고 로직이 복잡해졌다.
• 그래서 다시 처음으로 돌아가 Map에 size별로 리스트를 담아서 subList로 나누기로 생각했다.

해결

• groupSizes 배열 전체를 loop 돌면서 size로 key를 size가 같은 것끼리 value에 리스트로 HashMap에 저장했다.
• HashMap에 모두 저장했으면, HashMap의 key를 꺼내서 해당 size만큼 다시 List로 분리해서 result 리스트에 추가했다.

문제 풀이

HashMap으로 푼 나의 풀이

import java.util.*;
class Solution {
    Map<Integer, List<Integer>> map;

    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        List<List<Integer>> result = new ArrayList<>();
        Map<Integer, List<Integer>> map = new HashMap<>();

        // grouping (key: groupSize / val: index list) 
        for (int i = 0; i < groupSizes.length; i++) {
            List<Integer> values;
            if (map.containsKey(groupSizes[i])) {
                values = map.get(groupSizes[i]);
            } else {
                values = new ArrayList<>();
            }
            values.add(i);
            map.put(groupSizes[i], values);
        }
        
        // partitioning
        for (int key : map.keySet()) {
            List<Integer> list = map.get(key);
            for (int i = 0; i < list.size(); i+= key) {
                result.add(list.subList(i, Math.min(i+key, list.size())));
            }
        }

        return result;
    }
}

처음에 List로만 풀려고 했던 내 생각과 유사한 풀이

class Solution {
    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        List<List<Integer>> result = new ArrayList<>();
        for(int i = 0; i<groupSizes.length; i++){
            if(groupSizes[i] == 0){
                continue;
            }
            int k = i;
            int z = groupSizes[i];
            int j = z;
            List<Integer> temp = new ArrayList<>();
            while(j>0){
                if(groupSizes[k]==z){
                    temp.add(k);
                    groupSizes[k]=0;
                    j--;
                }
                k++;
            }
            result.add(temp);
        }
        return result;
    }

}

이렇게도 풀 수 있구나

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

class Solution extends java.util.AbstractList<List<Integer>> {
  int[] gs;
  List<List<Integer>> ans;

  public List<List<Integer>> groupThePeople(int[] groupSizes) {
    this.gs = groupSizes;
    return this;
  }

  @Override
  public List<Integer> get(int index) {
    if (ans == null)
      this.size();
    return ans.get(index);
  }

  @Override
  public int size() {
    if (ans == null) {
      ans = new ArrayList<>();
      var map = new java.util.HashMap<Integer, List<Integer>>();
      for (int i = 0; i < gs.length; i++) {
        List<Integer> g = map.computeIfAbsent(gs[i], z -> new ArrayList<>());
        g.add(i);
        if (g.size() == gs[i])
          ans.add(map.remove(gs[i]));
      }
    }
    return this.ans.size();
  }
}