알고리즘 스터디-2

전재우·2021년 2월 6일
알고리즘
1
post-thumbnail
post-custom-banner

2021년 2월 4일

주제 : DP(Dynamic Programming)

문제 : 백준사이트 11656 , 1213, 1181, 1316
문자열 알고리즘

문자열 알고리즘

이번 문제는 문자열 알고리즘 이라고 하기보다 문자열 정렬에 가까운 문제였습니다. 익명 클래스를 사용하는 것과, collections 클래스를 이용하여 정렬하는 방법 등 API를 사용하는 방법을 위주로 사용했습니다.

사용한방법들

익명 클래스

  • 익명 클래스는 말 그대로의 익명의 성질을 가진 클래스라는 뜻이다. 즉 이름이 없는 클래스라고 불린다.

객체 정렬하기

객체 지향 언어의 특성상 객체들을 정렬해야하는 경우가 발생한다.예를 들어, 온라인 게임 서비스에서 게이머들을 높은 점수 순으로 보여주는 게이머 랭킹 페이지를 생각해보자.

  • 먼저 정렬이 필요한 대상 클래스를 생성한다.
public class Player {
    private String name;
    private int score;

    public Player(String name, int score) {
        this.name = name;
        this.score = score;
    }
}
  • 정렬할 객체를 생성한다. 
List<Player> players = new ArrayList<>();
players.add(new Player("재현", 1050));
players.add(new Player("재우", 2000));
players.add(new Player("형우", 500));
players.add(new Player("준우", 1920));
players.add(new Player("민규", 1300));

현재 재우의 스코어가 2000으로 가장 높다 -> 리스트의 맨 앞에 위치해야한다.

  • 객체 정렬 기준의 필요성
    단순히 숫자와 문자와 같은 기본형(primitive) 타입의 데이터는 대소 비교의 개념을 가지고 있습니다.Java에서는 정렬을 지원하는 메소드들있다. -> Arrays.sort() 메소드는 데이터 값을 오름차순으로 정렬 해준다.
int[] scores = {899, 982, 1090, 982, 1018};
Arrays.sort(scores);
System.out.println(Arrays.toString(scores)); // [899, 982, 982, 1018, 1090]

하지만 특정 타입의 객체는 기본형타입의 데이터와 달리 정렬 기준이 존재하지 않으면 정렬을 할 수가 없다. 따라서 정렬 기준을 정의하여 알려줘야 한다.

Collections.sort(players); // Compile error!

Comparable인터페이스

객체의 정렬 기준을 정의하는 첫번째 방법은 정렬 대상 클래스를 자바에서 기본적으로 제공하고 있는 Comparable 인터페이스를 구현하도록 변경하는 방법이 있습니다.
위에 생성된 Player의 클래스는 COmparable인터페이스를 상속 받습니다.

public class Player implements Comparable<Player> {
    // Fields, Getters, Setters 생략

    @Override
    public int compareTo(Player o) {
        return o.getScore() - getScore();
    }
}

Comparable 인터페이스의 compareTo() 메소드를 통해 인자로 넘어온 같은 타입의 다른 객체와 대소관계가 비교 가능하다. 메소드를 호출하는 객체가 인자로 넘어온 객체보다 작은 경우 음수를 리턴하고 크기가 같은 경우 0, 클 경우 양수를 리턴해야한다.
게이머 랭킹페이지의 경우 높은 점수 순으로 내림 차순 정렬을 원하기 때문에, 인자로 넘어온 게이머의 점수에서 메소드를 호출하는게 게이머의 점수를 빼면 된다.
=>예를 들면 게이머의 점수가 982이고 compareTo()메소드를 호출하는 객체의 점수가 1018이라면 compareTo()메소드는 음수(982-1018)을 리턴하게 되며,이는 곧 메소드를 호출하는 게이머가 인자로 넘어온 게이머보다 작다는것을 의미한다.
CompareTo를 오버라이딩해서 사용해야하는 이유! -> 객체에는 정렬 기준이 존재 X

Collections.sort(players);
System.out.println(players); // [Player(name=Chloe, score=1090), Player(name=Eric, score=1018), Player(name=Bob, score=982), Player(name=Dale, score=982), Player(name=Alice, score=899)]

더이상 에러 발생 x

ComParator 객체사용

만얄 정렬 대상 클래스의 코드를 직접 수정할 수 없는 경우에는 어떻게 객체의 정렬 기준을 정의할 수 있을까요? 또는 정렬하고자 하는 객체에 이미 존재하고 있는 정렬기준과 다른 정렬 기준으로 정렬을 하고 싶을때는 어떻게 해야할까요?

이 떄 필요한 것이 바로 Comparator 인터페이스 입니다.
Comparator 인터페이스의 구현체를 Arrays.Sort()나 Collections.sort()와 같은 정렬 메서드의 추가 인자로 넘기면 정렬 기준을 누락된 클래스의 객체나 기존 정렬 기준을 무시하고 새로운 정렬 기준으로 객체를 정렬 할 수 있습니다.

Comparator<Player> comparator = new Comparator<Player>() {
    @Override
    public int compare(Player a, Player b) {
        return b.getScore() - a.getScore();
    }
};

Collections.sort(players, comparator);
System.out.println(players); // [Player(name=Chloe, score=1090), Player(name=Eric, score=1018), Player(name=Bob, score=982), Player(name=Dale, score=982), Player(name=Alice, score=899)]

위의 코드는 Coparator 객체를 Collections.sort() 메소드의 두번째 인자로 넘겨서 이전 섹션과 동일한 정렬 결과를 만들어 내고 있습니다. 이렇게 Comparator객체를 인자로 넘기면, 정렬 대상 객체가 Comparable 인터페이스를 구현 여부와 상관없이 , 넘어온 Comparator 구현체의 Compare()메소드 기준으로 정렬을 수행합니다. Compar() 메소드는 비교 대상 2개의 객체를 인자로 받습니다. 첫번쨰 인자가 두번째 인자보다 작다면 음수 , 같다면 0, 크다면 양수를 리턴하게 됩니다.

람다 함수로 대체

Comparator 객체는 메소드가 하나 분인 함수형 인터페이스를 구현하기 떄문에 람다 함수로 대체가 가능하다.

Collections.sort(players, (a, b) -> b.getScore() - a.getScore());
System.out.println(players); // [Player(name=Chloe, score=1090), Player(name=Eric, score=1018), Player(name=Bob, score=982), Player(name=Dale, score=982), Player(name=Alice, score=899)]

Stream으로 정렬

Stream 클래스의 Sorted() 메소드도 Comparator 객체를 인자로 받아 정렬을 해줍니다. 스트림을 사용하면 위에서 갈펴본 배열과 리스트이 정렬이 달리 기존 객체의 순서를 변경하지 않고, 새롭게 정렬된 객체를 생성하고자 할 때 사용 됩니다.

List<Player> sortedPlayers = players.stream()
        .sorted((a, b) -> b.getScore() - a.getScore())
        .collect(Collectors.toList());
System.out.println(sortedPlayers); // [Player(name=Chloe, score=1090), Player(name=Eric, score=1018), Player(name=Bob, score=982), Player(name=Dale, score=982), Player(name=Alice, score=899)]

코드

백준 1181번 단어정렬

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		//ArrayList<String> arr = new ArrayList<>();
		
		int N = sc.nextInt();
		String[] arr =new String[N];
		for(int i =0;i<N;i++) {
			arr[i]=sc.next();
		
		}
		
		Arrays.sort(arr, new Comparator<String>() {

			@Override
			public int compare(String s1, String s2) {
				if(s1.length() == s2.length()) {//길이가 같은경우
					return s1.compareTo(s2);
				}
				else
					return s1.length()-s2.length(); //길이가 다른경우
				
			}
			
		});
			
			
		
		
		for (int i = 0; i < N-1; i++) {
			if(!arr[i].equals(arr[i+1]))
			System.out.println(arr[i]);
		}
		System.out.println(arr[N-1]);
		
	}
}

백준 11656번 접미사 배열

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

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String pattern = sc.next();
		List<String> subpattern = new ArrayList();
		 ArrayList<String> pitches = new ArrayList<String>();
		//int 
		for(int j = 'a';j<='z';j++) {
		for(int i = 0;i< pattern.length(); i++) {
			if(pattern.charAt(i)== j) {
				subpattern.add(pattern.substring(i));
			}}}
				System.out.println(subPattern);
				
		Collections.sort(subpattern);
		for(String z : subpattern) {
			if(z!=null)
			System.out.println(z);
		}
}
}

백준 1213번 팰린드롬 만들기

package com.study10;

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

public class Backjoon_1213 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String N = sc.next();
		List<Character> result = new ArrayList<>();
		int[] alphabet = new int[26];
		
		for(int i = 'A';i<='Z';i++) {
			for(int j=0;j<N.length();j++) {
				if(N.charAt(j)==i) {
					
				alphabet[i-'A']+=1;
				}
			}
		}
		int mid = 0;
		int cnt = 0;
		for(int i=0; i<alphabet.length; i++) {
			if(alphabet[i]%2!=0) {
				mid = i;
				cnt++;
			}
		}
		if(cnt>1&&(N.length()%2!=0||cnt>0&&N.length()%2==0)) {
			System.out.println("I'm Sorry Hansoo");
			
		}

		else {
//		for(int k: alphabet)
//		System.out.println(k);
		for(int i =0; i <26;i++) {
			for(int j=0; j<alphabet[i]/2; j++) {
				result.add((char) ('A'+i));
			}
			
		}

		if(cnt==1) {
			result.add((char) (mid+'A'));
		}
		boolean flag =true;
		if(N.length()>1) {
		for(int i=result.size();i>0;i--) {
			if(flag&&cnt==1) {
				i--;
				flag=false;
			}
			result.add(result.get(i-1));
		}
		}
		//if(cnt=0) {
		for(char A:result)
		System.out.print(A);
		
	//}
		}	
}
	}

항상 범위체크 잘할것 이번 문제도 다 풀어 놓고 엣지케이스에 걸려서 해결하지 못함 -> 범위가 0~10일때 0개나 10개 끝에 걸려있는 문제를 테스트케이스를 엣지 케이스라고 한다.
뒤부분을 넣어주는 부분에서 N.length()>1를 체크 하지 않아서 풀지 못했다 항상 엣지케이스를 신경 쓸것.
백준 1316번 그룹단어 체커

출처

느낀점
이번 스터디는 문제의 난이도는 평이했고 API를 이용하여 푸는 문제가 많아서 조금 더 쉽게 풀렸던것 같습니다. 저번주 보다는 문제를 보는눈이 조금 더 생긴것 같고 쉬운문제를 풀다보니 문제푸는 재미도 느껴가고 있습니다. 하지만 아직 구현을 거의 다 했음에도 불구하고 break를 사용하는 등의 디테일이 모자라서 모든 테스트 케이스를 통과하지 못하는 경우가 많이 있습니다. 조금더 꼼꼼하게 그리고 문제를 보고 바로 코드부터 작성해 나가는것이 아닌 문제 해결 방법을 글로 써보고 푸는 연습을 해야할것 같습니다. 이번주도 화이팅!

목표
스터디를 총 4번 진행 즉, 한달 후에 공부했던 코드들을 보고 백준에서 각각 유형에 해당하는 문제를 풀어보자!!
다른 팀원들에 비해 많이 늦었지만 따라잡자 그게 내 주특기니까!
수업시간에 풀지 못했거나 미흡했거나 아쉬웠던 문제들을 한번 더 풀어보자!!

profile
전재우
코린이
이전 포스트

CS스터디-1

다음 포스트

공부복습_3주차

post-custom-banner

0개의 댓글