1181번: 단어 정렬
첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.
www.acmicpc.net
구상 :
- scanner.nextInt()로 몇 개의 단어가 입력될지를 변수에 저장해서 이걸로 for 반복문 돌림
- for 반복문 안에서 입력받은 단어들을 저장 ( 저장할 타입은? String . 어디다 저장할까? ArrayList
- 조건 1. 각 요소들의 크기를 비교해서 길이가 짧은 것 부터 다시 새로운 공간에 저장
조건 2 : 길이가 같으면 charAt ? 정도 사용해서 문자열을 문자로 바꾸고 사전순대로 점검한 뒤 다시 저장
*중복 단어는 무시해야함 :
ex) import java.util.ArrayList
for(int check : arrayList){
if( !arrayList.contains(check)) //리스트에 객체(check)가 존재하면 true리턴
//리스트의 contains메소드 활용해 리스트 내부의 데이터 체크
arrayList.add(check);//중복데이터 없을 경우 add를 통해 그 값을 넣어줌.
}
*내가 해맨 거 : 단어 정렬이 되다 안 되다 했는데 단어들의 길이를 저장한 wordLength 배열도 순서를 맞춰 바꿔줘야했음 !
또 for문을 중첩을 썼어야 했음 이미 정렬된 앞에 것도 또 비교하도록. for 하나만 쓴 건 버블 정렬 ? 방식이니까
음 위에 두 개 다 아님 선택정렬로 해서 전체 레코드에서 최솟값 뽑아 맨 앞, 나머지에서 최솟값 뽑아 맨 앞 이런방식으로 해야함.
음 근데 이렇게 안 함 결국 문제는 데이터 저장할 때 중복된 값 일 때 cnt 값을 ++ 안 해서 그런 거였고 암튼 완성은 했는데
예제는 돌아가는데 자꾸 틀렸다고 함
import java.util.Scanner;
import java.util.ArrayList;
class MainApp {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int num = scanner.nextInt();
String str;
String tempstr;
int tempint;
int cnt = 0;
ArrayList<String> array = new ArrayList<>();
int wordLength[] = new int[num];//저장된 단어들의 길이를 싹다 세서 배열에 넣음
for(int i =0;i<num;i++)
{
str = scanner.next();
if(!array.contains(str)){//중복제거하고 저장
array.add(str);
cnt++;//이게 ArrayList와 단어 하나씩의 길이 저장된 배열의 크기임.(중복 제거된 단어들의 수
}
}
for(int j=0;j<cnt;j++) {
str = array.get(j); //저장된 단어 하나씩을 str에 저장
wordLength[j] = str.length(); //단어들의 길이를 순서대로 wordLength 배열에 저장.
}
for(int i=0;i<cnt-1;i++) {
for(int j=i+1 ; j<cnt;j++) {
//길이가 짧은 것부터 정렬
if(wordLength[i]>wordLength[j]) {
tempstr = array.get(i);
array.set(i,array.get(j));
array.set(j, tempstr);
tempint = wordLength[i];
wordLength[i] = wordLength[j];
wordLength[j] = tempint;
}
//길이가 같으면 사전 순 정렬
else if(wordLength[i]==wordLength[j]) {
if(array.get(i).charAt(0) > array.get(j).charAt(0)) {//부등호가 큰 쪽이 사전순으로 뒤에 있는 알파벳
tempstr = array.get(i);
array.set(i,array.get(j));
array.set(j, tempstr);
tempint = wordLength[i];
wordLength[i] = wordLength[j];
wordLength[j] = tempint;
}
else if(array.get(i).charAt(0) == array.get(j).charAt(0)) {
if(array.get(i).charAt(1) > array.get(j).charAt(1)) {//부등호가 큰 쪽이 사전순으로 뒤에 있는 알파벳
tempstr = array.get(i);
array.set(i,array.get(j));
array.set(j, tempstr);
tempint = wordLength[i];
wordLength[i] = wordLength[j];
wordLength[j] = tempint;
}
else if(array.get(i).charAt(1) == array.get(j).charAt(1)) {//부등호가 큰 쪽이 사전순으로 뒤에 있는 알파벳
if(array.get(i).charAt(2) > array.get(j).charAt(2)) {
tempstr = array.get(i);
array.set(i,array.get(j));
array.set(j, tempstr);
tempint = wordLength[i];
wordLength[i] = wordLength[j];
wordLength[j] = tempint;
}
else if(array.get(i).charAt(2) == array.get(j).charAt(2)) {//부등호가 큰 쪽이 사전순으로 뒤에 있는 알파벳
if(array.get(i).charAt(3) > array.get(j).charAt(3)) {
tempstr = array.get(i);
array.set(i,array.get(j));
array.set(j, tempstr);
tempint = wordLength[i];
wordLength[i] = wordLength[j];
wordLength[j] = tempint;
}
}
}
}
}
}
}
for(int i =0;i<cnt;i++)
{
System.out.print(array.get(i));
if(i !=cnt-1)
System.out.println();
}
scanner.close();
}
}문제가 뭔가 봤더니
나는 앞 첫 글자만 똑같을 때 사전 순 정렬까지만 작성한 거고
단어 길이가 50을 안 넘으면 중첩에 중첩에 중첩 if문을 작성해야함 한마디로 개똥덩어리 코드임 ㅡㅡ
[백준] 1181번 : 단어 정렬 - JAVA [자바] (tistory.com)
[백준] 1181번 : 단어 정렬 - JAVA [자바]
www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1≤N≤20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문
st-lab.tistory.com
여기보고 공부해서 낼 다시 풀어보장,,,,,,,,,,,,,
지민아 보고있니 ? 나 종일 이것만 했어 ㅠ 너무 힘들다 -떡볶이 수혈 시급-
3/6 다시 공부해서 도전
Comparable , Comparator 개념
- 객체를 비교하기 위해서 쓴다.
Comparable 인터페이스에는 compareTo(T o) 메소드 하나. => compareTo는 정수를 반환. 자기 자신을 기준으로 상대방과의 차이값을 비교하여 반환함.
Comparator인터페이스에 많은 메소드 중 compare(T o1,T o2) 구현해서 씀
<Comparable은 "자기 자신과 매개변수 객체를 비교"하는 것이고, Comparator는 "두 매개변수 객체를 비교">
<Comparable은 lang패키지에 있기 때문에 import 를 해줄 필요가 없지만, Comparator는 util패키지에 있다.>
[Comparable의 특징]
1. 자기 자신과 매개변수를 비교한다.
2. compareTo 메소드를 반드시 구현해야한다.
compare메소드를 사용할 때는 필요없는 객체가 하나 만들어지게 됨. comparator 기능만 따로 두고싶을 땐
익명 객체(클래스)활용
보통의 경우 다음과 같이 생성할 것이다.
Rectangle a = new Rectangle();
하지만, 익명객체의 경우는 다음과 같이 생성된다.
Rectangle a = new Rectangle() { //...구현부...// };
즉, 쉽게 생각하여 'Rectangle을 상속받은 하나의 새로운 class라는 것이다.'
분명 새로운 class인데 이름이 정의되지 않고 있다.
=> 이름이 정의되지 않기 때문에 특정 타입이 존재하는 것이 아니기 때문에 반드시 익명 객체의 경우는 상속할 대상이 있어야 한다.
객체를 비교하기 위해 Comparable / Comparator을 쓴다는 것은 사용자가 정의한 기준 토대로 비교하여 양수, 0,음수 중 하나가 반환된다는 것 Java의 정렬은 기본이 '오름차순'. Arrays.sort(), Collections.sort() 모두 오름차순
[두 수의 비교 결과에 따른 작동 방식]
음수일 경우 : 두 원소의 위치를 교환 안함
양수일 경우 : 두 원소의 위치를 교환 함
제네릭 : 제네릭(Generic)은 클래스 내부에서 지정하는 것이 아닌 외부에서 사용자에 의해 지정되는 것을 의미
타입 파라미터로 명시할 수 있는 것은 참조타입 (Integer, Double...같은 Wrapper Type)
배열을 특정한 규칙에 의해 정렬하고 싶은 경우 Arrays.sort 메소드에 Comparator을 구현하면 된다.
// 제네릭 클래스
class ClassName<E> {
private E element; // 제네릭 타입 변수
void set(E element) { // 제네릭 파라미터 메소드
this.element = element;
}
E get() { // 제네릭 타입 반환 메소드
return element;
}
}
class Main {
public static void main(String[] args) {
ClassName<String> a = new ClassName<String>();
ClassName<Integer> b = new ClassName<Integer>();
a.set("10");
b.set(10);
System.out.println("a data : " + a.get());
// 반환된 변수의 타입 출력
System.out.println("a E Type : " + a.get().getClass().getName());
System.out.println();
System.out.println("b data : " + b.get());
// 반환된 변수의 타입 출력
System.out.println("b E Type : " + b.get().getClass().getName());
}
}보면 ClassName이란 객체를 생성할 때 <> 안에 타입 파라미터(Type parameter)를 지정한다.
그러면 a객체의 ClassName의 E 제네릭 타입은 String으로 모두 변환된다.
반대로 b객체의 ClassName의 E 제네릭 타입은 Integer으로 모두 변환된다.
- 제한된 Generic(제네릭)과 와일드 카드
특정 범위내로 좁혀서 제한하고 싶다면 extends, super, ? 사용. ?는 와일드카드 == 알 수 없는 타입
<K extends T> // T와 T의 자손 타입만 가능 (K는 들어오는 타입으로 지정 됨)
<K super T> // T와 T의 부모(조상) 타입만 가능 (K는 들어오는 타입으로 지정 됨)
<? extends T> // T와 T의 자손 타입만 가능
<? super T> // T와 T의 부모(조상) 타입만 가능
<?> // 모든 타입 가능. <? extends Object>랑 같은 의미
extends T : 상한 경계
? super T : 하한 경계
<?> : 와일드 카드(Wild card)
* 주의 K extends T와 ? extends T는 비슷한 구조지만 차이점있음.
경계가 지정되고 K는 특정 타입으로 지정되지만 ?는 타입이 지정되지 않는다는 의미
<T extends B> // B와 C타입만 올 수 있음
<T extends E> // E타입만 올 수 있음
<T extends A> // A, B, C, D, E 타입이 올 수 있음
<? extends B> // B와 C타입만 올 수 있음
<? extends E> // E타입만 올 수 있음
<? extends A> // A, B, C, D, E 타입이 올 수 있음대표적인 예로는 제네릭 클래스에서 수를 표현하는 클래스만 받고 싶은 경우가 있다. 대표적인 Integer, Long, Byte, Double, Float, Short 같은 래퍼 클래스들은 Number 클래스를 상속 받는다.
존나어렵네
Arrays.sort() 자체는 2차원 배열의 정렬을 할 수 없음. 람다식을 사용해 확장할 수 있어야함.
(매개변수1,...) -> {함수;}// 람다식 X
public int sum(int a, int b) {
return a + b;
}
// 람다식 O
(int a, int b) -> {return a + b;}람다식으로 구현한 함수를 익명함수라고도 함.
sort메소드는 두 가지 인자를 받을 수 있다.
첫 번째는 제너릭타입 객체배열(T[]).(클래스, 오브젝트, 자료형 등 어떤 타입이든 상관없이 배열의 형태로 받을 수 있음)
두 번째는 Comparator<? super T> c.
<? super T>는 상속관계에 있는 타입만 자료형으로 받겠다는 의미. T타입이 자식클래스가 되고 T의 상속관계에 있는 타입까지만 허용하겠다는 의미. 이 문제에서는 상속관계의 데이터는 정렬 안 해서 <T> 로 봐도 된대.
Comparator를 람다식으로 표현 가능. -> compart 메소드를 오버라이딩하여 compare 메소드 안에 자신만의 비교방법(우선순위 판단)을 구현
arr[N][2] 배열이 있고, 두 좌표를 모두 입력받았다고 가정해보자. 그리고 arr[i][0] 와 arr[i+1][0] 을 정렬할 것이고 만약 두 값이 같다면 arr[i][1] 과 arr[i+1][1] 을 비교할 것이다.
위 말대로라면 T 는 int[] 가 될 것이고, arr[] 의 [1] (arr[i][1])을 비교하기 위해 사용자화
Arrays.sort(arr, new Comparator<int[]>() {
@Override
public int compare(int[] e1, int[] e2) {
if(e1[0] == e2[0]) { // 첫번째 원소가 같다면 두 번째 원소끼리 비교
return e1[1] - e2[1];
}
else {
return e1[0] - e2[0];
}
}
});위의 코드를 람다식으로 변경하면
..
.
Arrays.sort에 Comparator을 써서 Compare메소드를 구현하는 방법
import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;
class MainApp{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int num = scanner.nextInt();
String[] word = new String[num];
scanner.nextLine();
for(int i=0;i<num;i++) {
word[i] = scanner.next();
}
Arrays.sort(word, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
if(o1.length() == o2.length()) {
//단어 길이가 같으면 사전 순
return o1.compareTo(o2);
}
else return o1.length() - o2.length();
}
});
System.out.println(word[0]);
for(int i=1; i< num; i++) {
if(!word[i].equals(word[i-1])) {
System.out.println(word[i]);
}
}
scanner.close();
}
}결론은 이렇게 간단한 코드로 할 수 있었따.
여기서 Comparator을 넣어준 건 내가 지정한 정렬로 만들기 위함 !.. 이라고 이해함
여기서 알게된 것
Arrays.sort()
Comparable 인터페이스에 compareTo메소드
Comparator 인터페이스에 compare 메소드
등 배열의 정렬을 효과적으로 할 수 있는 법 !!
[자바(java)] 배열 객체(2) 데이터 다.. : 네이버블로그 (naver.com)
[자바(java)] 배열 객체(2) 데이터 다루기(Arrays클래스, sort)
배열 데이터 정렬 (sorting) 요즘 프로그래밍 언어는 다행히도 기본적으로 sorting 내장되어 있지만, 기초...
blog.naver.com
Arrays클래스
java.util.Arrays에 있음
배열을 다룰 때 자주 쓰이는 유용한 메소드들(분류나 검색)등을 모아놓은 class.
- sort() : 배열 오름차순 정렬
- binarySearch() : 오름차순 정렬된 배열에서 원하는 데이터 값이 저장된 index를 리턴.
- copyOf() : 원본 배열을 원하는 길이만큼 복사한 새로운 배열 객체를 반환
- fill() : 배열 데이터 값 일괄 채우기/변환
- toString() : 배열 데이터를 문자열로 표현([배열 데이터, 배열 데이터, 배열 데이터 ..])로 반환
------------------------
Comparable 비교하는 인터페이스 -> compareTo 구현해서 사용 !
Comparator 인터페이스 -> compare 구현해서 사용
================
중요한 또 알게된 것 !
성능차이 관련
1) Scanner + System.out.println 내가 쓰는 가장 쉽지만 제일 오래걸리는 방법
2) Scanner + StringBuilder
3) BufferReader + StringBuilder
1) Scanner + System.out.println
scanner 쓸 때 nextInt()로 정수 입력 받은 뒤 nextLine()을 쓰면 입력한 첫 번째 문자가 arr[0]에 입력되는 것이 아니고
개행("\n")이 arr[0]에 저장된다. 따라서 nextLine()하기전에 nextLine을 한 번 해줘서 개행을 버려야 정상적으로 입력한 문자열을 배열에 저장할 수 있다.
=> 이는 next 계열 입력을 받은 뒤, nextLine() 을 쓰면 두 메소드의 메커니즘이 달라 발생하는 대표적인 에러
입력 받는 문자열을 next()로 받으면 개행 안 버려도 됨
* next()는 첫 공백 전 까지만 받고 나머지는 다 버퍼로 들어가있음.
* nextLine()은 한 줄 입력을 받음 \n전까지만
2) Scanner + StringBuilder
출력방법을 바꾸어 StringBuilder 을 사용하여 하나의 문자열로 묶어준 뒤 마지막에 묶어준 문자열을 출력해주는 방법
별로 안 어렵 !
3) BufferedReader + StringBuilder
scanner vs BufferedReaderReader
scanner는 입력받을 때 정수, 소수, 문자도 구분지어 읽어들임. 장 : 직관적이고 사용하기 편리 단 : 속도 느림
BufferedReader 입력받은값을 기본적으로 8192char(16384 byte)크기 버퍼에 담아뒀다가 한 번에 프로그램에 전송
버퍼리더 특 :
- 개행문자(엔터)만 경계로 인식BufferedReader와 StringTokenizer를 사용하기 위해 import하고 입력된 데이터의 형식이 String으로 고정. 데이터 따로 후처리해줘야함
- BufferedReader를 사용하기 위해선 예외처리가 필수적이기 때문에 try, catch문을 이용하던가
메인문 중괄호 시작 전 throws IOException
- 입력을 받기 위해선 readLine() 메소드를 사용하고, 데이터가 문자 값으로 들어오기 때문에 숫자 값을 받아올 땐 꼭 형변환이 필요하다.
버퍼리더와 스트링빌더를 사용해서 코딩하도록 신경써보자 !
'알고리즘 > 백준' 카테고리의 다른 글
| 2231번 문제 : 분해합 (0) | 2023.03.07 |
|---|---|
| 11651번 문제 : 좌표정렬 2 (0) | 2023.03.06 |
| 11650번 문제 : 좌표 정렬하기 (0) | 2023.03.06 |
| 백준 깃허브에 commit 돼있는 거 local로 받아오기 (0) | 2023.02.28 |
| 12월에 백준하면서 쓴 코딩일지 (0) | 2023.02.23 |