[알고리즘] 정렬 문제 풀이(백준 1181번, 1920번, 1427번)

◎ 다른 문제 풀이

• [알고리즘] 정렬 문제 풀이(백준 10817번, 11399번) (tistory.com)

[알고리즘] 정렬 문제 풀이(백준 10817번, 11399번)

• [알고리즘] 정렬 문제 풀이(백준 2750번, 2751번, 10989번) (tistory.com)

[알고리즘] 정렬 문제 풀이(백준 2750번, 2751번, 10989번)

 

 

 

1. 단어 정렬(백준 1181번 문제)

 

1181번: 단어 정렬 (acmicpc.net)

1181번: 단어 정렬

 

▷ 풀이 코드(퀵 정렬)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class WordSort4 {    
   public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();           	
    	
		int n = Integer.parseInt(br.readLine());
    	
    	String word[] = new String[n];
    	
        List<String> list = new ArrayList<>();
    	
    	
    	for(int i=0; i<word.length; i++) {
    		word[i] = br.readLine();
    	}   	
    	
        // 1. 람다식을 추가로 적용한 sort 메소드
    	// Arrays.sort(word, (String s1, String s2) -> s1.length() - s2.length());
    	
        // 사전 순으로 단어 정렬
    	Arrays.sort(word);
        
        // 2. 길이 순으로 정렬하기 위한 메소드 Override
    	Arrays.sort(word, new Comparator<String>() {
    		@Override
    		public int compare(String s1, String s2) {
    			return s1.length() - s2.length();
    		}
    	});
    	
    	for(int i=0; i<word.length; i++) {
    		if(!list.contains(word[i]))
    			list.add(word[i]);
    	}
    	
    	for(String arr : list) {
        	sb.append(arr).append("\n");
    	}
    	
    	System.out.println(sb.toString());
    	br.close();
    	
   }
}

 

 

2. 수 찾기(백준 1920번 문제)

 

1920번: 수 찾기 (acmicpc.net)

1920번: 수 찾기

 

▷ 풀이 코드(HashSet의 contains 메소드 사용)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;

public class findNum {         
	public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());

        String[] arr1Word1 = br.readLine().split(" ");
        int[] arr1 = new int[n];
        HashSet<Integer> set = new HashSet<>();

        for (int i = 0; i < arr1.length; i++) {
            arr1[i] = Integer.parseInt(arr1Word1[i]);
            set.add(arr1[i]);
        }

        n = Integer.parseInt(br.readLine());

        String[] arr2Word2 = br.readLine().split(" ");
        int[] arr2 = new int[n];

        for (int i = 0; i < arr2.length; i++) {
            arr2[i] = Integer.parseInt(arr2Word2[i]);
        }

        for (int i = 0; i < arr2.length; i++) {
            if (set.contains(arr2[i])) {
                sb.append("1").append("\n");
            } else {
                sb.append("0").append("\n");
            }
        }

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

가장 빠르게 출력하기 위해서는 HashSet을 사용해야합니다!

List, 배열은 시간이 HashSet에 비해 오래 걸립니다.

HashSet은 중복된 값을 저장하지 않기 위해 사용하고 List는 순서가 가장 중요합니다.

 

 

 

3. 소트인사이드(백준 1427번 문제)

 

1427번: 소트인사이드 (acmicpc.net)

1427번: 소트인사이드

 

▷ 풀이 코드(버블 정렬)

import java.util.Scanner;

public class sortInside {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String a = sc.nextLine();
		char arr[] = new char[a.length()];
		
		for(int i=0; i<a.length(); i++) {
			arr[i] = a.charAt(i);
		}
		
		for(int i=0; i<a.length(); i++) {
			char temp = 0;
			
			for(int j=i + 1; j<arr.length; j++) {
				if(arr[i] >= arr[j]) {
					temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
				}
			}
		}
		
		for(int i=0; i<a.length(); i++) {
			System.out.print(arr[a.length()-i-1]);
		}
	}
}

 

이번에도 정렬에 관한 문제 물이를 해보았습니다!

 

다음 시간에는 퀵 정렬에 대해서 한 번 정리해볼게요!!

 

많은 분들의 피드백은 언제나 환영합니다!  많은 댓글 부탁드려요~~