[240223] 알고리즘 리부트 14일차 - 백준 1181, 1427 자바

[Part1-Chapter05-Clip02]

- 백준 1181 단어정렬

 

 

 

 

1년 전과 비교해서 나는 어떤 일이 있었던 걸까... 아무리 생각해도 set밖에 생각이 나질 않아 이를 활용해서 아래와 같이 풀었다. 그리고  compareTo가 단기 기억으로만 남고 정작 활용할 때는 잘 떠오르지 않아서 주석처럼 정리했다. 앞에 위치시킨다 이런 표현 대신 순서를 변경한다/안한다로 구분해서 정리하니 헷갈리지 않는다. 

 

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        StringBuilder sb = new StringBuilder();
        int n = sc.nextInt();

        HashSet<String> exist = new HashSet<>();

        String[] words = new String[n];

        for (int i = 0; i < n; i++) {
            String thisString = sc.next();
            if (exist.contains(thisString)) {
                words[i] = "*";
            } else {
                words[i] = thisString;
                exist.add(thisString);
            }
        }

        Arrays.sort(words, (o1, o2) -> {
            if (o1.length() == o2.length()) {
                // 길이가 같다면 o1과 o2를 비교해서
                // 음수가 나오면 순서 변경 하지마
                // 양수가 나오면 순서 변경해!
                // o2.compareTo(o1)로 작성하면
                // 두 개의 위치를 바꿔서 비교하기 때문에
                // 음수일 게 양수로 판별되고
                // 양수일 것이 음수로 판별되기 때문에
                // 역순으로 정렬되는 것
                return o1.compareTo(o2);
            } else {
                return Integer.compare(o1.length(), o2.length());
            }
        });

        for (int i = 0; i < n; i++) {
            if(words[i]=="*") continue;
            sb.append(words[i] + "\n");
        }

        System.out.println(sb.toString());
    }
}

 

그리고 아래는 1년 전에 내가 푼 코드이다. 오히려 자료구조를 많이 알지 못할 때 어떻게든 풀어보려고 생각하면서 메모리도 적게 사용하면서 문제를 풀 수 있었던 것 같다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {
	// 단어의 개수가 최대 20,000개 이기 때문에 2중 반복문 사용하면 4억개로 4초가 소요됨 -> 시간 초과
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int wNum = Integer.parseInt(br.readLine());
		String[] words = new String[wNum];
		for (int i = 0; i < wNum; i++) {
			words[i] = br.readLine();
		}

		Arrays.sort(words, 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();
				}
			}
		});

		System.out.println(words[0]);
		for (int i = 1; i < words.length; i++) {
			// 중복되지 않는 단어만 출력
			if (!words[i].equals(words[i - 1])) {
				System.out.println(words[i]);
			}
		}
	}
}

 

 

- 백준 1427 소트인사이드

 

 

Object 객체 배열을 정렬할 때, Comparator를 구현해서 정렬 로직을 짜는 것은 이제 익숙해진 것 같다. 람다식으로 변경하는 것은 아직 어설프긴 하다. 처음에 Character 배열이 아닌 char 배열로 primitive 타입을 사용했더니 Comparator 구현이 안되어서 Character 배열로 선언해서 처리했다. 숫자로 변경하지 않아도 문자로 처리할 수 있어서 간편했다.

 

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

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

        String numStr = sc.next();
        Character[] num = new Character[numStr.length()];

        for(int i =0; i<numStr.length(); i++){
            num[i] = numStr.charAt(i);
        }

        Arrays.sort(num, (o1, o2) -> o2-o1);
        
        // 람다식 변경 전
        // Arrays.sort(num, new Comparator<Character>() {
            // @Override
            // public int compare(Character o1, Character o2) {
                // return o2-o1;
            // }
        // });

        StringBuilder sb = new StringBuilder();

        for(int i =0; i<num.length; i++){
            sb.append(num[i]);
        }

        System.out.println(sb.toString());

    }
}