[BOJ] 2866. 문자열 잘라내기

Hyodong Lee·2022년 2월 10일
0

알고리즘

목록 보기
5/32

[작성일]

  • 2022-02-10

[분류]

  • Set


[문제링크]

[요구사항]

  • 맨 윗줄을 지우고 열 문자열끼리 비교해서 같은 값이 없으면 count+1 해주고 있으면 count를 출력하고 종료해라.


[풀이]

한 줄씩 지워가면서 비교를 일일이 처음에는 다 해줄려고 했는데 hashset에 넣어서 비교 시간을 크게 단축할 수 있는 방법이 떠올랐다. 이를 이용해서 한 문자열에 대한 중복검사 로직은 O(1)로 단축할 수 있었다.

1) string을 열로 나누어서 배열로 담는다.

2) 맨 윗줄을 지운다 = 각 문자열마다 맨 앞 글자를 지운다.

3) 지울 때마다 hashSet에 동일한 문자열이 있는지 확인하고 없으면 hashSet에 해당 문자열을 추가해주어서 뒤에 올 문자열들이 비교할 수 있도록 해준다.

4) 동일한 문자열이 있을 경우 loop문을 빠져나와 count를 출력하고 아닐 경우 count+1을 해주고 2)번 과정부터 다시 반복한다.



[코드]

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


public class Main {
    static int R, C;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        Set<String> set = new HashSet<>();
        int count = 0;
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        // C개의 stringbuilder 생성
        StringBuilder[] sb = new StringBuilder[C];
        for (int i = 0; i < sb.length; i++) {
            sb[i] = new StringBuilder();
        }

        for (int i = 0; i < R; i++) {
            String s = br.readLine();
            for (int j = 0; j < C; j++) {
                sb[j].append(s.charAt(j));
            }
        }

        String[] str = new String[C];
        for (int i = 0; i < C; i++) {
            str[i] = sb[i].toString();
        }

        loop:
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                // 1. 맨 위에 문자열을 지운다
                str[j] = str[j].substring(1);

                // 2-1. 동일한 문자열 발견 시 break
                if (set.contains(str[j])) break loop;
                else {
                    // 2-2. 동일한 문자열 검사를 위해 set에 넣어주기
                    set.add(str[j]);
                }
            }

            // 검사 통과 시 count++
            count++;
            // 메모리가 쌓이는 것을 막기위해 set 초기화
            set.clear();
        }
        System.out.println(count);
    }
}

[통과여부]



[느낀점]

중복검사를 해야한다면 항상 set 자료구조를 사용하는 것을 염두해야겠다!

profile
사용자가 신뢰할 수 있는 튼튼한 서비스 개발을 지향하는 예비 개발자입니다.

0개의 댓글