[JAVA] 백준 | 3181 줄임말 만들기

📝 TIL

- [백준] 3181 줄임말 만들기

https://www.acmicpc.net/problem/3181

 

제한사항

시간 제한 1초

메모리 제한 128MB

 

입출력 예

입력#1

micro soft

 

출력#1

MS

 

입력#2

biti ali i ne biti

 

출력#2

BNB

---

🦔 설계 및 시도

처음에는 어제 풀었던 숫자 문자로 바꾸기 문제와 비슷하게,

제외 단어들을 배열에 넣고 아니면 첫 문자만 가져오게 하려고 했다.

 

 String[] check = {"i", "pa", "te", "ni", "a", "nego", "no", "ili"};
StringBuilder sb = new StringBuilder();

sb.append(parts[0].charAt(0));
   for(int i=1; i<parts.length; i++){
       for(int j=0; j<8; j++){
            if(!(parts[i]).equals(check[j])) {
                 sb.append(parts[i].charAt(0));
                 break;
            }
       }
}

 

이런 느낌으로 작성하려고 했는데..? 작성하다보니 이중 for문을 사용하는 것은 둘째치고

해당 방식으로 사용하면 모든 단어를 모든 check 단어에 비교하기에 틀렸다는 걸 깨달았다.

 

다시 생각해보니 중복 여부만 확인하면 된다!가 키워드여서

Set을 사용해서 풀이를 했다.

 

1. 문자열을 split을 이용하여 공백 기준으로 쪼개서 배열로 변환

2. StringBuilder를 만들어서 첫번째 단어의 경우 무조건 apend

3. 나머지 단어들은 set.contains로 판별을 해서 없으면 append

 

 

 

🔥 풀이에 사용된 개념

Set 인터페이스

- Java Collections Framework의 일부

- 중복 요소를 저장하지 않고, null 값을 저장할 수 있음

- 요소의 순서를 보장하지 않는다

 

Set 인터페이스의 종류

- HashSet : 가장 많이 사용되는 구현체, 순서 보장 안됨, 가장 빠른 성능

- TreeSet : 요소가 정렬된 상태로 유지됨

- LinkedHashSet : 삽입 순서가 유지됨

 

contains 메서드

- Set 인터페이스에 특정 요소가 존재하는지 확인하는 메서드

- set.contains("String")

 

Set.of(요소)

- 자바 9에서 도입된 불변 Set을 생성하는 정적 팩토리 메서드

- 불변이므로 Set.of()로 만든 Set에 add()나 remove()를 하면 예외

- null 허용 안됨!

 

💡 Set.of를 안 쓰고 Set을 만들려면?

- set.add(요소) : 요소의 수만큼 더하기

- Set<String> set = new HashSet<>(Arrays.asList("apple", "banana")); 

- Set<String> set = Stream.of("apple", "banana").collect(Collectors.toSet());

---

 

💡 풀이 소스 코드

 

시간복잡도 : O(n)

공간복잡도 : O(n)

 

import java.io.*;
import java.util.Set;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine(); 
        System.out.println(solution(str));      
    }

    // 풀이
    static String solution(String str){
        String[] parts = str.split(" ");
        Set<String> check = Set.of("i", "pa", "te", "ni", "niti", "a", "ali", "nego", "no", "ili");
        
        StringBuilder sb = new StringBuilder();
        sb.append(parts[0].charAt(0));

        for(int i=1; i<parts.length; i++){
            if(!check.contains(parts[i])){
                sb.append(parts[i].charAt(0));
            }
        }
        return sb.toString().toUpperCase();
    }
}

 

 

---

🚀 새로 배운 내용

- set.contains("string")을 쓸 때 순간 set과 string의 위치가 헷갈렸는데,

set 메서드를 사용하므로 당연히! set.contains("string")으로 써야 한다.

 

 

---

😺  느낀점

- 자료 구조를 공부하고 사용법을 익혀서, 최대한 시간복잡도를 줄이는 방향으로 풀이하자.

 

 

*소스 코드는 다음 깃허브에 올라옵니다 - https://github.com/s0ooo0k/Algorithm_Study

GitHub - s0ooo0k/Algorithm_Study: Algorithm Study 문제 및 풀이