[1053] 팰린드롬 공장(작성중)

문제

---

팰린드롬이란, 앞에서부터 읽었을 때와, 뒤에서부터 읽었을 때가 같은 문자열이다.

모든 문자열이 팰린드롬이 아니기 때문에 다음과 같은 4가지 연산으로 보통 문자열을 팰린드롬으로 만든다.

1. 문자열의 어떤 위치에 어떤 문자를 삽입 (시작과 끝도 가능)
2. 어떤 위치에 있는 문자를 삭제
3. 어떤 위치에 있는 문자를 교환
4. 서로 다른 문자를 교환

1, 2, 3번 연산은 마음껏 사용할 수 있지만, 마지막 연산은 많아야 한 번 사용할 수 있다.

문자열이 주어졌을 때, 팰린드롬으로 만들기 위해 필요한 연산의 최솟값을 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 문자열이 주어진다. 영어 소문자로만 이루어져 있고, 길이는 최대 50이다.

출력 

첫째 줄에 문제의 정답을 출력한다.

 

예시

babacvabba
//2
abba
//0

 

Key Point

---

• 삽입과 삭제는 동일한 처리이다. 두 번 반복할 필요 없음(babba,babbab)
•  

 

 

풀이

---

• 먼저 문자열을 팰린드롬으로 만들기 위한 연산을 정의한다.
  • 문자열에 문자 삽입(위치 무관)
  • 특정 인덱스에 있는 문자 삭제
  • 특정 위치에 있는 문자 교환
  • 서로 다른 문자 교환(1번만 사용 가능)
• 효율적인 연산을 위해 거를 수 있는 조건 정의
  • 문자열이 짝수일 경우 반으로 쪼개서 reverse 해서 팰린드롬인지 우선 확인
  • 홀수인 문자 있는지 탐색
• 문자열 상태에 따른 연산 처리를 위해 조건을 정의한다.
  •  
  •  

 

 

 

내 풀이

collection 안쓰고 해보려 했는데 실패

class Meeting{
    public int s,e;
    public Meeting(int s, int e){
        this.s = s;
        this.e = e;
    }
    public void compare(Meeting o){
        int cnt =0;
        if(this.e <=o.s){
            cnt++;
        }
        System.out.println(cnt);
    }
}
public class Main {
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int s,e;
        ArrayList<Meeting> arr = new ArrayList<>();
        for(int i =0; i<n; i++){
            s= in.nextInt();
            e = in.nextInt();
            arr.add(new Meeting(s,e));
        }
        //Meeting.compare 호출 어케해
    }
}

 

정답 풀이(Comparable implements)

class Meeting implements Comparable<Meeting>{
    int s,e;
    public  Meeting(int s,int e){
        this.s=s;
        this.e=e;
    }
    @Override
    public int compareTo(Meeting o) {
        //종료 시간이 같을 경우 시작 시간 오름차순 정렬
        if (this.e==o.e){
            return this.s-o.s;
        }
        //그 외 종료시간 오름차순 정렬
        else return this.e-o.e;
    }
}
public class Main {
    public int solution(ArrayList<Meeting> arr){
        int cnt=0;
        Collections.sort(arr);
        for(Meeting x : arr){
            System.out.print(x.s + " ");
            System.out.println();
        }
        int temp = 0;
        for(Meeting x : arr){
            //이전 회의의 종료시간보다 다음 회의 시작 시간이 크거나 같으면 cnt++, temp에 다음 회의 종료시간 저장
            if(x.s>=temp){
                cnt++;
                temp = x.e;
            }
        }
        return cnt;
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int s,e;
        ArrayList<Meeting> arr = new ArrayList<>();
        for(int i =0; i<n; i++){
            s= in.nextInt();
            e = in.nextInt();
            arr.add(new Meeting(s,e));
        }
        System.out.println(T.solution(arr));
    }
}

 

다른 풀이(Comparator)

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

        int arr[][] = new int[n][2];
        for(int i =0; i<n; i++){
            arr[i][0]=in.nextInt(); //시작 시간
            arr[i][1]=in.nextInt(); //종료 시간
        }
        Arrays.sort(arr, new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[1] == o2[1]){
                    return o1[0] -o2[0];
                }
                return  o1[1] -o2[1];
            }
        });
        int cnt =0;
        int et=0;
        for(int i = 0; i < n; i++) {
            // 직전 종료시간이 다음 회의 시작 시간보다 작거나 같다면 갱신
            if(et <= arr[i][0]) {
                et = arr[i][1];
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}