Yong's Tech Story

https://school.programmers.co.kr/learn/courses/30/lessons/60057

문제 풀이 (JAVA)

import java.util.*;
class Solution {
    public int solution(String s) {
        int answer = Integer.MAX_VALUE; // 최대 숫자 길이 임의로 설정
        List<String> slist = new ArrayList<>(); // substring 문자열 저장 리스트
        String str=""; // 글자 개수별로 나눈 문자를 저장할 변수
        String nstr=""; // 새로 조립될 문자를 저장할 변수
        int cnt = 1; // 문자의 개수를 세는 카운트 변수
        if(s.length() == 1){ // 테스트케이스 5번 예외처리
            return 1; // 글자가 1개일때에는 조건문을 돌지 않는다.
        }
        for(int i=1; i<s.length(); i++){ // 자를 글자 수 = i
            for(int j=0; j<s.length(); j+=i){  // j는 글자수 +i 만큼 증가
                if(j+i < s.length()){ // 글자열이 최대 문자길이를 안넘긴다면
                    str = s.substring(j,j+i); // 글자수 i 만큼 잘라서 저장
                }else{ // 자를 글자열이 최대 문자길이를 넘어간다면
                    str = s.substring(j,s.length()); // 남은 마지막 문자까지 저장
                }
                slist.add(str); // 리스트에 자른 글자열 저장
            }
            for(int k=0; k<slist.size()-1; k++){ // k+1과 비교하므로 size()-1 까지 비교
                // 리스트에 저장한 단어 문자열 i번째와 i+1번째가 같다면
                if(slist.get(k).equals(slist.get(k+1))){ 
                    cnt++; // 카운트 증가 (초기 카운트=1, 따라서 2이상)
                }else{ // 다음 문자열 리스트와 같지 않다면
                    if(cnt > 1){ // 같은 문자열 카운트가 2 이상이라면
                        nstr += cnt + slist.get(k); // 숫자 + 문자열 저장
                    }else{ // 같은 문자열 카운트가 1, 즉 없다면
                        nstr += slist.get(k); // k-1에서 초기화한 글자 출력
                    }            
                    cnt=1; // 다음 문자열 k+1의 카운트 초기화
                }
                // 마지막 size-2 인덱스 처리(마지막 문자열 출력)
                if((k+1) == slist.size()-1){
                    if(cnt > 1){
                        nstr += cnt + slist.get(k+1);
                    }else{
                        nstr += slist.get(k+1);
                    }                     
                }
            }
            // 기존에 저장한 문자열의 길이보다 작다면 결과값 변경
            if(answer > nstr.length()){
                answer = nstr.length();
            }
            slist.clear(); // 리스트 초기화
            nstr=""; // 문자열 초기화
            cnt=1; // 카운트 변수 초기화
        }
        return answer;
    }
}

주요 핵심 포인트

1. for문의 i는 자를 문자열의 길이를 차례로 증가시키기 위하여 사용하였다.

2. for문의 j+=i 를 선언함으로써 다음 문자열의 길이를 반복하여 자른다. j+i가 문자열의 길이를 초과하는지 여부를 판단하여 문자열을 잘랐다.

3. 자른 문자열을 리스트에 저장하여, k번째와 k+1 번째가 같다면 cnt는 1씩 증가하였고, 초기 cnt는 1로 설정하였다. 따라서 k번째와 k+1번째가 달라질 경우 cnt의 크기에 따라 2이상이면 숫자와 함께 출력, 1이면 단일 문자열로 그대로 출력하였다. 마지막에 cnt=1 로 설정 한것은 다음 문자열의 개수를 미리 설정한 것이다. 비교문은 버블 정렬과 비슷한 알고리즘이다.

4. 마지막 인덱스에 도달했을때 경우를 출력하기 위하여  마지막에 조건절을 추가하였다.

5. 새로운 nstr 문자열 길이가 기존 answer보다 작다면 answer을 변경하였다.

6. 다음 문자열을 저장하기 위하여 clear()를 사용하여 리스트를 초기화하였고, nstr , cnt 또한 초기화하였다.

개선해야할 사항

: 해당 문제를 깔끔하게 풀었다고는 할 수 없을 것 같다. 문자열의 길이가 1~1000이하였기에 중첩되는 for문에서 시간초과 오류가 나지 않았다. 문자열의 길이가 매우 크다면, 해당 로직은 분명히 시간 초과 오류를 겪을 것이다. for문을 최소화 할수 있는 방법이 있는지 탐색해보아야겠다.

https://school.programmers.co.kr/learn/courses/30/lessons/12981

문제 풀이 (JAVA)

import java.util.*;
class Solution {
    public int[] solution(int n, String[] words) {
        int[] answer = new int[2]; // 결과 : 걸린사람, 회차

        List<String> wordlist = new ArrayList<>(); // words를 저장할 리스트
        Queue<Integer> queue = new LinkedList<>(); // 순서를 반복하기 위한 큐 선언
        int [] cnt = new int[n+1]; // 각 순서마다의 회차 기록
        for(int i=1; i<=n; i++){
            queue.offer(i); // 초기 순서 세팅
        }
        int idx=0; // words의 0번째 인덱스 선언
        char as=' '; // 이전 단어의 마지막 단어 변수
        char to=' '; // 현재 단어의 첫 번째 단어 변수
        while(idx < words.length){ // words의 배열을 다 돌떄까지 반복
            if(idx>0){ // 2번째 인덱스부터 이전 단어와 비교
                as = words[idx-1].charAt(words[idx-1].length()-1);// 이전 단어 마지막 글자
                to = words[idx].charAt(0); // 현재 단어 첫번째 글자
            }
            // 리스트에 반복되는 단어가 없고, 끝자리와 첫자리가 같은 경우만 다음 순서 반복
            if(wordlist.contains(words[idx]) != true && as==to){
                int person = queue.peek(); // 해당 순서의 사람 번호
                wordlist.add(words[idx]); // 워드 추가
                queue.offer(queue.poll()); // 순서를 가장 뒤로
                cnt[person]++; // 해당 번째 순서의 회차 기록
            }
            // 단어가 리스트에 존재하거나, 끝자리와 첫자리 단어가 다른 경우 끝말잇기 종료
            else if(wordlist.contains(words[idx]) == true || as != to){
                int person = queue.poll(); 
                cnt[person]++; // 해당 순서 회차 기록
                answer[0] = person; // 걸린 사람 번호
                answer[1] = cnt[person]; // 순서 회차
                break; // 종료
            }           
            idx++;
        }
        // 정상적으로 다 돌았다면 끌맛잇기는 정상적으로 종료된것으로 0,0 리턴
        return answer;
    }
}

주요 핵심 포인트

1. 해당 문제는 순서가 반복되는 문제로 큐를 선언해야 한다.

2. 이미 한번 반복되는 문자를 처리하기 위해 List를 선언하여 contains() 함수를 사용하였다.

3. cnt 배열을 선언하여 각 사람 번호의 회차를 기록하였다.

4. 끝자리와 첫자리가 다른 경우를 단어를 가져와 비교하였다. 단어가 다른 경우 또한 종료 대상이다.

개선해야할 사항

1. 테스트 결과가 통과 하지 않는 것을 보고 문제를 다시 읽어보니, 이전단어 끝자리와 현재 단어 첫자리가 다르면 리턴하도록 설계하는 것이었다. 문제를 제대로 읽지 않아 조금의 시간이 더 들었다. 그러하여 끝말잇기에 걸리는 사람의 조건은 반복되는 단어를 말하였거나 or 이전 단어와 다른 첫번째 단어를 말하였을때를 말한다.

https://school.programmers.co.kr/learn/courses/30/lessons/12973

문제 풀이 (JAVA)

import java.util.*;
class Solution
{
    public int solution(String s)
    {
        int answer = 0; // 기본 리턴 0 세팅
        Stack<Character> stack = new Stack<>();
        char [] ch = s.toCharArray();
        for(int i=0; i<ch.length; i++){
            if(i == 0){ // 첫번째 스택은 무조건 추가
                stack.push(ch[i]);
                continue; // 아래 조건 돌지 않고 i++
            }
            // 스택에 데이터가 들어 있고, 스택의 최상단값이 비교할 값과 같다면
            if(stack.size() > 0 && ch[i] == stack.peek()){
                    stack.pop(); // 스택의 최상단 값 제거
            }else{ // 스택의 최상단값이 같지 않다면 스택에 추가
                stack.push(ch[i]);
            }                
        }
        // 스택이 비어 있을시 모두 짝지은 문자이므로 제거 되어 1 리턴
        if(stack.size() == 0){
            answer = 1;
        }     

        return answer;
    }
}

주요 핵심 포인트

1. 짝지은 문자가 들어 왔을 때를 처리하는 것은 스택의 대표적인 문제인 '괄호'  문제와 같은 개념으로 스택으로 풀게 되었다.

2.  스택의 사이즈를 체크하지 않고 pop()시 사이즈를 체크하지 않으면 오류가 난다.

3. 첫번째 스택은 무조건 추가하도록 하였다.

4. for문이 모두 돌고 스택이 비어있다면 모두 짝인 문자이다.

개선해야할 사항

1.  i == 0 대신 stack.size() == 0 일때 조건을 거는것으로 바꾸는 풀이 방법 또한 있다.

https://school.programmers.co.kr/learn/courses/30/lessons/42586

문제 풀이 (JAVA)

import java.util.*;
class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        int[] answer = {}; // 결과값 배열 선언
        Queue<Integer> queue = new LinkedList<>(); // 큐 선언
        int cnt=0; // 각 프로그레스가 스피드로 몇 회 돌았는지 카운트할 변수
        for(int i=0; i<progresses.length; i++){
            cnt = 0; // 횟수 초기화
            while(progresses[i] < 100){ // 프로그레스가 100보다 작다면 반복
                progresses[i] += speeds[i]; // 스피드를 반복해서 증가
                cnt++; // 횟수 카운트 증가
            }
            queue.offer(cnt); // 각 프로그레스 100이 되기위한 횟수 카운트 저장
        }
        List<Integer> list = new ArrayList<>();
        int max = queue.peek(); // 비교를 위한 첫 숫자는 큐의 첫번째 값
        cnt = 0; // 카운트 초기화
        while(queue.isEmpty() != true){
            if(max < queue.peek()){ // 큐의 횟수 카운트가 더 큰 숫자가 있다면
                max = queue.poll(); // 최대 값은 해당 값
                list.add(cnt); // 최대값을 만나면 카운트 한 이전 값을 저장한다.
                cnt = 0; // 다음 최대값 이후로 카운트 초기화
            }else{
                queue.poll(); // 최대값보다 작은 횟수라면 그대로 꺼낸다.
            }
            cnt++; // 모든 경우 카운트 증가
            if(queue.size()==0){ // 마지막 큐 처리문
                list.add(cnt); // 앞에서 계산된 카운트를 넣는다.
            }
        }
        answer = new int[list.size()];
        
        for(int i=0; i<list.size(); i++){
            answer[i]=list.get(i);
        }
        return answer;
    }
}

주요 핵심 포인트

1.  문제의 접근 방식을 progress를 큐에 적재하는것이 아닌 반복되는 speed의 횟수를 배열로 저장하여 구현하였다.

2. 각 pregress의 speed 카운트와 result의 규칙을 찾은 결과, 앞쪽부터 가장 큰 값보다 더 큰값이 나온다면 그 이전의 값을 배열로 저장하였다. 따라서 앞쪽부터 max값을 차례대로 비교하여 새로운 max값을 찾은 경우 그 이전에 세었던 count를 리스트로 저장하였다.

3. 마지막 큐 사이즈가 0인 경우를 고려하여 끝 처리를 하였다.

개선해야할 사항

1.  cnt 카운트를 이용해서 정답을 구하긴 하였으나 최선의 수로 구했는지는 알 수 없다.  다른 사람이 작성한 소스 코드를 참고해봐야겠다.