개발자 던킨

문제는 틈틈히 푸는데 TIL를 쓰기엔 정성이 부족해서 잘안하게 되네요.. ㅎㅎ

오늘은 백준 문제 12605번 : 단어순서 뒤집기 에 대해서 이야기 해볼까 합니다.

문제

스페이스로 띄어쓰기 된 단어들의 리스트가 주어질때, 단어들을 반대 순서로 뒤집어라. 각 라인은 w개의 영단어로 이루어져 있으며, 총 L개의 알파벳을 가진다. 각 행은 알파벳과 스페이스로만 이루어져 있다. 단어 사이에는 하나의 스페이스만 들어간다.

입력

첫 행은 N이며, 전체 케이스의 개수이다.
N개의 케이스들이 이어지는데, 각 케이스는 스페이스로 띄어진 단어들이다. 스페이스는 라인의 처음과 끝에는 나타나지 않는다. N과 L은 다음 범위를 가진다.
N = 51 ≤ L ≤ 25

앞서 그냥 받은 문자열을 뒤집는것이 아닌 항해99에서 내준 문제는 스택/큐 를 사용해서 문제를 풀라고 하여서 Stack을 사용했습니다.

public class backjoon12605 {
    public static void main(String[] args) throws IOException {
    	//BufferedReader로 입력받기
    	//BufferedReader를 사용해 입력을 받아 n에 저장합니다. n은 테스트 케이스의 수입니다.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        //for문이 각 테스트 케이스마다 실행됩니다.
        //Stack<String> q = new Stack<>();가 for문 안에 있어, 각 테스트 케이스마다 새로운 Stack이 생성됩니다.
        for(int i =1; i<=n; i++){
            Stack<String> q = new Stack<>();
            //입력된 문장을 split(" ")으로 단어별로 나누어 String 배열 que에 저장합니다.
            String[] que = br.readLine().split(" ");
            //for-each 루프를 사용해 각 단어를 Stack에 push()로 추가합니다.
            for(String a : que){
                q.push(a);
            }
            //System.out.print("Case #" + i + ":");를 출력해 현재 테스트 케이스 번호를 출력합니다.
            //while (!q.isEmpty()) 루프에서 Stack이 비어있지 않을 때까지 pop()을 사용해 단어를 출력합니다. Stack은 LIFO(Last In, First Out) 구조이므로 마지막에 push()된 단어부터 출력되어 단어 순서가 역순이 됩니다.
            //System.out.println();로 각 테스트 케이스 출력을 마치고 줄바꿈을 합니다.
            System.out.print("Case #"+i+": ");
            while(!q.isEmpty()){
                System.out.print(" "+ q.pop());
            }
            System.out.println();
        }

    }
}

TIP : 

각 테스트 케이스마다 Stack을 새로 생성하므로, 이전 테스트 케이스의 데이터가 현재 테스트 케이스에 영향을 주지 않습니다.
Stack의 내용을 pop()하면서 단어를 출력할 때, 단어가 역순으로 출력됩니다.

stack이 for문 밖에 선언이 되어있어도 잘 작동되고 답변 똑같이 나옵니다. 그러나 그럴 경우,
모든 테스트 케이스가 동일한 Stack 인스턴스를 공유하기 때문에 예상치 못한 결과를 초래할 수 있습니다.
다만, 현재 코드 구조에서는 매 반복문 안에서 Stack 이 비워질 때까지 pop() 을 호출하므로 동작할 수 있습니다.

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

오늘은 백준 에서 31562 전주 듣고 노래 맞히기 에 대해서 진행해보도록하겠습니다.

문제 :

윤수와 정환은 「전주 듣고 노래 맞히기」라는 게임을 할 예정이다. 「전주 듣고 노래 맞히기」는 주어진 노래의 전주를 듣고 먼저 제목을 맞히는 사람이 점수를 얻어 최종적으로 점수가 더 많은 사람이 이기는 게임이다. 절대 음감을 가진 윤수는 노래의 첫 네 음만 듣고도 어떤 노래든 바로 맞힐 수 있다. 따라서, 정환은 윤수를 이기기 위해 첫 세 음만으로 노래를 맞히게 해주는 프로그램을 만들려고 한다. 우선 정환이 알고 있는 노래 제목, 음이름 등을 데이터로 만든 뒤 프로그램을 구현하기 시작했다. 예를 들어, 다음은 TwinkleStar(반짝반짝 작은 별)의 악보 중 일부이다.

위 악보를 박자와 관계없이 음이름으로 표현하면 CCGGAAG가 된다.

윤수를 이기기 위해서는 이 프로그램이 첫 세 음인 CCG만으로 노래 제목인 TwinkleStar를 출력할 수 있어야 한다. 또한, 세상의 모든 노래를 아는 윤수와 다르게 정환은 음을 아는 노래가 N개뿐이다. 그래서 프로그램에 N$N$개의 노래의 정보를 저장해 놓을 것이다. 만약 저장된 노래 중 입력한 첫 세 음으로 시작하는 노래가 여러 개 있어 무슨 노래인지 정확히 알 수 없는 경우 ?를 출력하고, 입력한 첫 세 음에 맞는 저장된 노래가 없을 경우 !를 출력한다.

정환을 도와서 첫 세 음만으로 본인이 음을 아는 노래를 맞히는 프로그램을 완성하자. 이 프로그램은 대문자와 소문자를 구분한다.

입력 :

첫 번째 줄에 정환이 음을 아는 노래의 개수 N$N$, 정환이 맞히기를 시도할 노래의 개수 M$M$이 공백으로 구분되어 주어진다.

두 번째 줄부터 N$N$개의 줄에 걸쳐 노래 제목의 길이 T$T$, 영어 대소문자로 이루어진 문자열 노래 제목 S$S$, 해당 노래에서 처음 등장하는 일곱 개의 음이름 a1,a2,a3,a4,a5,a6,a7$a_1, a_2, a_3, a_4, a_5, a_6, a_7$이 공백으로 구분되어 주어진다.

 N+2$N+2$번째 줄부터 M$M$개의 줄에 걸쳐 정환이 맞히기를 시도할 노래의 첫 세 음의 음이름 b1,b2,b3$b_1, b_2, b_3$가 공백으로 구분되어 주어진다.

주어지는 음이름은 각각 C, D, E, F, G, A, B 중 하나이다. 같은 제목이 두 번 이상 주어지지 않는다.

예제 :

4 4
11 TwinkleStar C C G G A A G
8 Marigold E D E F E E D
23 DoYouWannaBuildASnowMan C C C G C E D
12 Cprogramming C C C C C C C
E D E
C G G
C C C
C C G

JAVA  

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

        String[] NM = br.readLine().split(" ");

        int N = Integer.parseInt(NM[0]); // 음을 아는 노래의 개수 N
        int M = Integer.parseInt(NM[1]); // 맞출 노래의 개수 M

        String[][] musicInfo = new String[N][]; // [제목 길이, 제목, 음이름]이 담긴 이차원 배열 선언

        for(int i = 0; i < N; i++) {
            musicInfo[i] = br.readLine().split(" "); // 음악 정보 초기화
        }

        for(int j = 0; j < M; j++) {
            int cnt = 0;
            String code = br.readLine().replaceAll(" ", ""); 
            ArrayList<String> list = new ArrayList<>(); 
            for(int i = 0; i < N; i++) {
                // code와 가장 맨앞부터 3개의 음이름 같으면 list에 저장
                if((musicInfo[i][2] + musicInfo[i][3] + musicInfo[i][4]).equals(code)) {
                    list.add(musicInfo[i][1]);
                }
            }

            int listSize = list.size();

            if(listSize == 1) { // size 1이면 제목 출력
                System.out.println(list.get(0));
            }
            else if(listSize > 1) { // size 1보다 크면 ? 출력
                System.out.println("?");
            }
            else { // size 0이면 ! 출력
                System.out.println("!");
            }
        }
    }

JAVA 2

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken());

        Map<String, String> map = new HashMap<>();
        while (n-- > 0) {
            String[] arr = br.readLine().split(" ", 3);
            String key = arr[2].substring(0, 5);

            map.put(key, map.containsKey(key) ? "?\n" : arr[1] + "\n");
        }

        while (m-- > 0) sb.append(map.getOrDefault(br.readLine(), "!\n"));

        bw.write(sb.toString());
        bw.flush();
    }

둘의 장단점 : 

첫 번째 코드 (JAVA)

장점:
명확한 흐름: 입력을 받고 처리하는 과정이 명확하게 나누어져 있어 이해하기 쉽습니다.
직관적인 비교: 코드가 음악 정보를 직접 비교하여 일치 여부를 판단하므로, 쿼리의 결과를 이해하기 쉽게 출력합니다.

단점:
비효율성: 모든 쿼리에 대해 음악 정보를 매번 순회하여 비교하므로, 시간이 오래 걸릴 수 있습니다. 쿼리 수가 많아지면 성능이 저하될 수 있습니다.
중복 출력 처리: 중복된 제목이 있을 때, 명시적으로 "?"를 출력하는 로직이 필요하여 코드가 다소 복잡해질 수 있습니다.


두 번째 코드 (JAVA2)

장점:
해시맵 사용: 음악 코드와 제목을 해시맵에 저장하여 O(1) 시간 복잡도로 쿼리를 처리할 수 있습니다. 이로 인해 성능이 크게 향상됩니다.
중복 처리 간편화: 해시맵에 키가 이미 존재할 경우 "?"로 처리하므로, 코드가 간결해지고 중복 제목 처리가 쉽게 이루어집니다.
효율적인 입출력: BufferedWriter와 StringBuilder를 사용하여 입출력을 효율적으로 처리합니다.

단점:
코드 이해의 어려움: 해시맵 사용과 관련된 부분이 초보자에게는 직관적이지 않을 수 있습니다. 코드의 흐름이 첫 번째 코드에 비해 다소 복잡하게 느껴질 수 있습니다.
고정된 키 길이: 코드의 처음 5글자만 사용하므로, 만약 코드가 5글자 이하로는 구분할 수 없는 경우가 생길 수 있습니다.


결론
성능을 중시한다면 두 번째 코드(Main)가 더 좋습니다. 해시맵을 사용하여 쿼리 처리 속도가 빠르고, 중복 처리가 간편하여 전체적인 효율성이 높습니다.
코드의 직관성과 간단함을 중시한다면 첫 번째 코드(bak_31562)가 더 나을 수 있습니다. 읽기 쉬운 구조로 인해 이해하기 쉽습니다.
따라서 사용자의 요구에 따라 선택할 수 있습니다. 성능이 더 중요한 경우에는 두 번째 코드를 추천합니다.

오늘은 화요일 향해99에서 2번째 맞이하는 날입니다. 

월요일은 회사일이 너무 바뻐서 참여를 못했지만 처음으로 화요일날 참여하게되었습니다. 

TIL - Todya I Learn

오늘은 비기너 두번째날 문제를 풀어봤습니다. 

문제 설명

숫자로 이루어진 문자열 t와 p가 주어질 때, t에서 p와 길이가 같은 부분문자열 중에서, 이 부분문자열이 나타내는 수가 p가 나타내는 수보다 작거나 같은 것이 나오는 횟수를 return하는 함수 solution을 완성하세요.

예를 들어, t="3141592"이고 p="271" 인 경우, t의 길이가 3인 부분 문자열은 314, 141, 415, 159, 592입니다. 이 문자열이 나타내는 수 중 271보다 작거나 같은 수는 141, 159 2개 입니다.

제한사항

1 ≤ p의 길이 ≤ 18
p의 길이 ≤ t의 길이 ≤ 10,000
t와 p는 숫자로만 이루어진 문자열이며, 0으로 시작하지 않습니다.

입출력 예

입출력 예 설명

입출력 예 #1
본문과 같습니다.

입출력 예 #2
p의 길이가 1이므로 t의 부분문자열은 "5", "0", 0", "2", "2", "0", "8", "3", "9", "8", "7", "8"이며 이중 7보다 작거나 같은 숫자는 "5", "0", "0", "2", "2", "0", "3", "7" 이렇게 8개가 있습니다.

입출력 예 #3
p의 길이가 2이므로 t의 부분문자열은 "10", "02", "20", "03"이며, 이중 15보다 작거나 같은 숫자는 "10", "02", "03" 이렇게 3개입니다. "02"와 "03"은 각각 2, 3에 해당한다는 점에 주의하세요

글쓴이의 풀이

class Solution {
    public int solution(String t, String p) {
        int pLength = p.length();
        long pValue = Long.parseLong(p);
        System.out.println(pValue);
        int answer = 0;
        for(int i=0; i<=t.length()-pLength; i++){
            String sub = t.substring(i,i+p.length());
            System.out.println(sub);
            long subValue = Long.parseLong(sub);
            if(subValue <= pValue){
                answer ++;
            }

        }
        return answer;
    }
}

일단 부분 문자열 추출을 해야됩니다. 

t의 각 가능한 부분의 문자열을 검사해야하기 때문에, t의 길이 만큼 반복하고 부분 문자열 t 에서 시작 인덱스 i 를 기준으로 i 부터 i+p.length() 까지의 문자를 추출하여서 생성합니다. 

그 후에 숫자비교 

문자열로 표현된 숫자를 비교하려면 문자열 => 숫자형으로 변환 해야됩니다. 

[Long.parseLong()] 메서드를 사용합니다.

변환 후 두 숫자(subValue 와 pValue)를 비교해서 위와 같은 조건인지 검사합니다.

시간 복잡도는 

- 0(n*m) 입니다. n은 t의 길이이고, m은p 의 길이입니다.

- 각 부분 문자열을 만드는데 0(m)의 시간이 소요되고, 이를 t의 길이 n에 대해 반복하므로 전체적으로 0(n*m) 이 됩니다.