SDeung01 commented 12 months ago

문제1 : 스킬트리

문제

문제 링크
선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.
예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.
위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다.
선행 스킬 순서 skill과 유저들이 만든 스킬트리를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요.
제한 조건

스킬은 알파벳 대문자로 표기하며, 모든 문자열은 알파벳 대문자로만 이루어져 있습니다.

스킬 순서와 스킬트리는 문자열로 표기합니다.

예를 들어, C → B → D 라면 "CBD"로 표기합니다

선행 스킬 순서 skill의 길이는 1 이상 26 이하이며, 스킬은 중복해 주어지지 않습니다.

skill_trees는 길이 1 이상 20 이하인 배열입니다.

skill_trees의 원소는 스킬을 나타내는 문자열입니다.

skill_trees의 원소는 길이가 2 이상 26 이하인 문자열이며, 스킬이 중복해 주어지지 않습니다.

입출력 예

skill | skill_trees | return -- | -- | -- "CBD" | ["BACDE", "CBADF", "AECB", "BDA"] | 2

문제 풀이

처음에는 조건식과 반복문, charAt() 메소드를 사용하여 접근하였으나 적합한 조건식을 세우지 못하며 많이 헤매었다.
한참 고민하다 아예 스킬트리에서 선행스킬을 제외한 스킬들을 모두 제거 한 후 선행스킬과 비교하는 방향으로 코드를 새로짰다.
선행스킬(문자열 skill)을 스킬트리에서 제거하는 방법으로 정규식과 replaceAll() 메소드를 사용하였다.

정규식에는 변수를 사용할 수 있다.(!중요)

class Solution {
public int solution(String skill, String[] skill_trees) {
    int count = 0;

    for(String tree : skill_trees){
        String removedSkill = remove(skill, tree);
        // 선행스킬을 아무것도 익히지 않은 경우도 카운트
        if(removedSkill.isEmpty()) {
            count++;
            continue;
        } else {
            StringBuilder sb = new StringBuilder();
            // 선행스킬을 순서대로 하나씩 익힌 것과 removedSkill 이 일치하면 카운트
            for(char ch : skill.toCharArray()){
                sb = sb.append(ch);
                if(sb.toString().equals(removedSkill)){
                    count++;
                    break;
                }
            }
        }
    }

    return count;
}

// 선행스킬 외의 스킬들을 스킬트리에서 모두 제거
private String remove(String skill, String skill_tree){
    return skill_tree.replaceAll("[^" + skill + "]","");
}
}

회고

동일한 방법으로 접근한 사람의 코드를 보다 선행스킬을 올바른 순서로 익혔는지 확인하는 코드를 for문이 아닌 indexOf() 메소드를 사용하여 간결하게 정리한 것을 보고 리팩토링 하였다.

리팩토링

        if(skill.indexOf(removedSkill) == 0) {
            count++;
        }

기존

   else {
            StringBuilder sb = new StringBuilder();
            // 선행스킬을 순서대로 하나씩 익힌 것과 removedSkill 이 일치하면 카운트
            for(char ch : skill.toCharArray()){
                sb = sb.append(ch);
                if(sb.toString().equals(removedSkill)){
                    count++;
                    break;
                }
            }

두 코드는 같은 기능을 수행한다.
아래의 코드는 처음 접근했던 방식으로 다른사람이 잘 정리해둔 코드가 있어 가져와보았다.

이렇게 보면 참 간단한 코드인데 막상 풀려고 하면 조건식을 적절히 작성하기가 힘들다.

class Solution {
public int solution(String skill, String[] skill_trees) {
    int answer = 0;
    for (String skillTree : skill_trees) {
        int learningIdx = 0;
        boolean isAble = true;
        for (char curSkill : skillTree.toCharArray()) {
            int skillIdx = skill.indexOf(curSkill);
            if (skillIdx == -1)
                continue;
            else if (skillIdx == learningIdx)
                learningIdx++;
            else {
                isAble = false;
                break;
            }
        }
        if (isAble)
            answer++;
    }
    return answer;
}
}

SDeung01 commented 11 months ago

문제 2 : 올바른 괄호

문제

문제링크
괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어
- "()()" 또는 "(())()" 는 올바른 괄호입니다.
- ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.
제한사항
- 문자열 s의 길이 : 100,000 이하의 자연수
- 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

입출력 예

문제풀이

1번 문제와 마찬가지로 별다른 자료구조 없이 if문으로 조건을 세워가며 풀어보려다 잔뜩 헤맨 문제
스택을 사용한 후에도 괄호의 형태가 올바른지 판별하기 위한 조건을 찾지 못해 많이 고민하다 질문하기의 코드를 조금 참고하여 풀었다.
```
import java.util.*;
```

class Solution { boolean solution(String s) {

    Stack<Character> bracketStk = new Stack<>();

    if(!s.startsWith("(") || !s.endsWith(")")) { return false; }

    for(int i = 0; i < s.length(); i++){
        char nowBracket = s.charAt(i);
        if(nowBracket == '(') { bracketStk.push('('); }
        if(bracketStk.isEmpty()) { return false; }
        if(nowBracket == ')') { bracketStk.pop(); }
    }

    return bracketStk.size() == 0 ? true : false;

)

## 회고
- 스택이냐 큐 같이 1단계 문제에서는 자주 보이지 않던 자료구조를 사용하는 문제가 늘며 풀이에 난항을 겪고 있다. 매번 쓰던 리스트나 맵, 셋 뿐만 아니라 더 많은 자료구조에 대한 학습이 필요하다.
- 다른 사람의 코드를 보면 Stack과 같은 자료구조를 사용하지 않고도 복잡한 조건 없이 깔끔하게 풀 수 있었다.
```java
class Solution {
    boolean solution(String s) {
        boolean answer = false;
        int count = 0;
        for(int i = 0; i<s.length();i++){
            if(s.charAt(i) == '('){
                count++;
            }
            if(s.charAt(i) == ')'){
                count--;
            }
            if(count < 0){
                break;
            }
        }
        if(count == 0){
            answer = true;
        }

        return answer;
    }
}

SDeung01 commented 11 months ago

문제 3 : 혼자놀기의 달인

문제

문제 링크
문제 길이가 길어 생략합니다. 링크를 참고해주세요.
제한사항
- 2 ≤ cards의 길이 ≤ 100
- cards의 원소는 cards의 길이 이하인 임의의 자연수입니다.
- cards에는 중복되는 원소가 존재하지 않습니다.
- cards[i]는 i + 1번 상자에 담긴 카드에 적힌 숫자를 의미합니다.

입출력 예

cards | result -- | -- [8,6,3,7,2,5,1,4] | 12

문제풀이

class Solution {
    public int solution(int[] cards) {
        int highScore = Integer.MIN_VALUE;
        for(int i = 0; i < cards.length; i++){
            int[] cardArr = cards.clone();
            //group1
            int score1 = group(cardArr, i);
            if(score1 == cardArr.length) { return 0; }
            //group2
            for(int j = 0; j < cardArr.length; j++){
                int[] leftCards = cardArr.clone();
                // 1번 그룹에서 선택한 상자는 제외했기 때문에 2번 그룹에서 뽑을 일이 없다.
                // 따라서 -1 일 경우 continue
                if(leftCards[j] == -1) { continue; }
                int score2 = group(leftCards, j);
                int newScore = score1 * score2;
                if(newScore > highScore) {
                    highScore = newScore;
                }
            }
        }

        return highScore;
    }

    // 고른 상자 안의 카드에 적힌 숫자에 따라 다음 뽑을 상자를 고름
    // 연 상자에는 표시(-1)를 하고 이미 연 상자를 다 시 고를 때 까지 반복하며 그때까지의 횟수를 반환
    private int group (int[] cardArr, int startIdx){
        int selectIdx = startIdx;
        int cnt = 0;
        while(cardArr[selectIdx] > -1){
            int card = cardArr[selectIdx];
            cardArr[selectIdx] = -1;
            selectIdx = card - 1;
            cnt++;
        }
        return cnt;
    }
}

회고

문제를 푸는 중 크게 엇나간 부분이 없는 것 같은데도 값이 너무 이상하게 나와 확인해보니 처음 주어진 배열 cards를 반복문에서 계속 사용하고 있었다.
반복문 사용 시 매 루프마다 동일한 형태의 배열로 시작해야 할 경우 배열의 초기화가 필요하며 아래와 같은 방식으로 배열의 초기화를 시도할 시 같은 배열의 주소를 참조하여 어느쪽의 요소를 변경하여도 두 변수로 호출한 배열의 값은 모두 변경된 것처럼 보인다.(두 변수가 가리키는 배열은 하나이므로)
```
    int[] test1 = {1,2,3,4,5};
    int[] test2 = test1;
    System.out.println(Arrays.toString(test1));  // [1, 2, 3, 4, 5]
    System.out.println(Arrays.toString(test2));  // [1, 2, 3, 4, 5]
    test2[4] = 1;
    System.out.println(Arrays.toString(test1)); // [1, 2, 3, 4, 1]
    System.out.println(Arrays.toString(test2)); // [1, 2, 3, 4, 1]
```
따라서 이번문제와 같이 아규먼트로 주어진 배열을 매 루프마다 동일한 형태로 시작해야 할 경우 배열의 값을 복사하여 복사한 배열의 값을 가공한다.
배열의 복사방법에는 반복문, Arrays 클래스의 copyOf() 메소드, Object 클래스의 'clone()` 메소드 등이 있다.

enoch012 / JavaBasicStudy

11월 12일 / 코딩테스트 연습(gwangho) #41

문제1 : 스킬트리

문제

입출력 예

문제 풀이

회고

문제 2 : 올바른 괄호

문제

입출력 예

문제풀이

문제 3 : 혼자놀기의 달인

문제

입출력 예

문제풀이

회고