문제

카약과 강풍

풀이

이 문제는 카약이 부서진 팀과 카약을 하나 더 가져온 팀이 동일할 수 있다는 개념을 알고 하면 된다 하나 더 가져오면 부서져도 대체가 가능하기 때문이다. 어려운 문제는 아닌데 그래서 이부분을 모르면 무조건 한번은 틀린다. 나는 더 틀렸는데 그 이유는 마지막에 -1을 샐때 n번째를 포함하지 않고 샜기 때문에 틀렷다... 또 바보짓함;;

일단 나는 전체 카약이 부서진 배의 인덱스를 -1으로 해주었고 카약을 하나 더 가져왔으면 1을 셋팅해주었다

여기서 중요한점은 부서진 배를 가지고 있는 값이 -1 인경우 배열을 다시 0으로 저장하는 작업이다

...
for (int i = 0; i < s; i++) {
    arr[Integer.parseInt(st.nextToken())] = -1;
}
st = new StringTokenizer(br.readLine());
for (int i = 0; i < r; i++) {
    int k = Integer.parseInt(st.nextToken());
    if (arr[k] == -1) {
        arr[k] = 0;
    } else {
        arr[k] = 1;
    }
}
...

전체 코드

전체 코드

후위 표기식2

풀이

표기식에 관한 문제라면 역시 스택이지! 이 문제는 스택에는 문자를 넣어주지 않고 현재의 값을 넣어주는데에 있다 시나리오는 대충 이렇다 A에 해당하는 배열을 스택에 문자이면 넣는다.(Character.isLetter()) 스택에 넣는값은 알파벳에 해당하는 숫자를 넣으면 된다 만약 문자가 아니라면 연산을 해줄 값을 스택에서 꺼내서 연산하면 된다. 후위표기식이기 때문에 2개를 연속해서 꺼내야한다 나중에 꺼낸것이 연산에 앞에 오는 것이므로 주의해야한다.!

전체 코드

전체코드

걸그룹 마스터 준석이

풀이

해시맵 두개를 가지고 하나는 그룹명을 키로두고 값은 배열로 둔 것으로 문제에서 요구하는 전체 멤버의 이름을 출력하기 위해저장하는 것 하나와 나머지 하나는 키가 이름이고 값은 그룹 명으로 저장해서 바로 불러올수 있게 저장하였다.

전체 코드

전체 코드

좋은 단어

풀이

이 문제는 처음에는 replace로 하려고 했다 좋은 단어의 조건은 인접한 것끼리 묶어서 단어에서 제외해주면 되기 때문에 replace('AA','').replace('BB','') 를 해주면 되지 않을까 그런 다음 남아있는 값이 아무것도 없다면 그것은 좋은 단어 일 것 이다.

하지만 이 문제는 스택이기 때문에 스택의 아이디어로 푼다면 처음에 스택이 비어있을때는 현재 값을 무조건 스택에 값을 넣어주고 스택에 값이 존재 한다면 스택에 가장상위에 있는 값과 비교해서 같으면 스택에 있는 값을 빼주고, 다르면 스택에 현재 값을 넣어준다. 그런다음 스택에 남아있는 값이 없다면 그것은 좋은 단어라는 것이다.

Stack<Character> stack = new Stack();

while (n-- > 0) {
    String s = br.readLine();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        // 값이 존재 하지 않으면 비교해줄 대상을 늘려준다
           if (stack.isEmpty()) {
            stack.push(c);
        } else {
            if (stack.peek() == c) { // 인접한 단어가 현재 단어와 일치한다
                stack.pop();
            } else {
                stack.push(c);
            }
        }

        if (stack.isEmpty()) {
            answer++;
        }
    }
}

전체 코드

전체 코드

두 수의 합

풀이

이 문제는 마이너스 인덱스를 비교 하게 되어서 indexoutofBound 가 계속 났다. 알고리즘 자체는 문제가 없었는데 배열을 두개로 두고 한개는 주어지는 배열을 저장할 용도 이고 나머지 하나는 값이 존재하는지만 볼거라 boolean 배열을 선언해주면 된다

그래서 이문제에서 가장 중요한 점은 x값보다 작은 값들로만 더해져야 하기 때문에 값이 존재하는 지 알아보기 전에 x값보다 작은 값인지를 먼저 비교해야 한다

for (int i = 0; i < n; i++) {
    if (arr[i] < x) { // x보다 작은 값이어야 a + b를 할수 있습니다.
        if (arr1[x - arr[i]]) {
            answer++;
        }
    }
}

전체 코드

전체 코드

문제

Project Teams

풀이

뭐지 이문제는 ? 정답률 보면 날먹문제 같다..

가장 평균의 가깝게 짝지어 주기 위해서는 정렬을 하고 가장 작은 수와 가장 큰 수끼리 짝을 지어주면 됩니다.

오늘도 스트릭 호로록 합니다..

전체 코드

전체 코드

가운데를 말해요

풀이

중간값을 뽑을때는 자료구조를 두개 두고 작은 값이 나오면 상대적으로 작은 값을 앞으로 보내주는 작업을 하면 된다

이 문제에서 주어지는 내용중에 작은 값을 출력하라고 되어있으므로 상대적으로 작은 값을 가지는 우선순위 큐 보다 상대적으로 큰 값을 가지는 우선순위 큐의 양이 많아지면 큰 값을 가지는 우선순위 큐에서 앞에 있는 값을 하나빼줘서 반대 큐에 옮겨 담는다

참고로 큰 값을 가지는 우선순위 큐는 정렬 순서를 반대로 고정하여 오름차순으로 만들어주는 것이 이문제에서 가장 중요한 부분이다

PriorityQueue<Integer> minpq = new PriorityQueue<>();
PriorityQueue<Integer> maxpq = new PriorityQueue<>(Collections.reverseOrder());

minpq.add(Integer.parseInt(br.readLine());

for (int i = 1; i < n; i++) {
    int k = Integer.parseInt(br.readLine());


    if (minpq.size() < maxpq.size()) {
           minpq.add(k);
     } else { 
        maxpq.add(k); 
    }

    int min = minpq.peek();
    int max = maxpq.peek();

     if (min < max) {
           minpq.poll(); maxpq.poll();
           minpq.add(max);
        maxpq.add(min);
     }
    sb.append(max.peek()).append("\n");
}

전체 코드

전체 코드

문제

N과 M (11)

풀이

이번엔 같은 수를 여러번 출력할 수 있는 대신에 중복된 순서로 출력되는 라인만 제거하면 된다 이전에 9번문제에서 영감을 주신 그분 덕택에 이 문제를 풀 수 있다. 10 번 문제도 이런식으로 풀었다

이제 n과 m문제를 졸업할 시간이 다가온다. 아쉽다. (이젠 너무 익숙해져서 스트릭 날먹하고있었는데... )

전체 코드

전체 코드

문제

N과 M (9)

풀이

백트래킹에 대한 내용은 이전이랑 너무 비슷해서 생략하고, 중복된 순서대로 나오면 안되서 뭘쓸까하다가..그냥만만한 hashset을 사용했다 근데 생각해보니 적재순서를 보장해줘야 해서 LinkedHashSet을 사용해서 풀었다.

메모리 공간이 너무 많이 차지하려나? 했는데 맞았다. 그리고 지금보니까 vistied 배열도 공간을 줄이면 메모리도 더줄일수 있을거같고

자료 구조를 이용한 것도 괜찮긴한데...

이런풀이말고 다른게 더 괜찮을거 같아서 다른 분들 풀이 보니까 visited 체크와 동시에 backtracking 안에서 변수를 선언해서 이전에 들어간 값이랑 겹치지 않는 값을 선택하기 위해 이전값을 저장하고 있다가 비교를 하고있었다. 자바코드는 아니지만 너무 좋자나

void func(int cnt) {
    if (cnt == m) {
        for (int i = 0; i < m; i++)
            printf("%d ", res[i]);
        printf("\n");
        return;
    }
    int xx = 0;
    for (int i = 0; i < n; i++) {
        if (!chk[i] && arr[i] != xx) {
            res[cnt] = arr[i];
            xx = res[cnt];
            chk[i] = true;
            func(cnt + 1);
            chk[i] = false;
        }
    }
}

출처 나중에 보고 배껴야지~

이제보니까 hash사용한 풀이들도 많구나 휴 다행이다,

전체 코드

전체 코드

문제

N과 M (7)

풀이

이제 이쯤됬으면 백트래킹에 대해서 그냥 출퇴근 시간에 무심결에 생각하게 됬다. 이문제는 이전에 6번문제,, 포스팅을 안했지만 그문제 보다 더 쉽다,

private static void backtracking(int depth) {
    // 멈추는 조건
    if (depth == m) {
        ..
        return;
    }

    // 반복조건
    for (int i = 0; i < n; i++) {
        ..
        backtracking(depth + 1);
    }
}

일단 멈추는 조건은 m번째에 멈추면 되고 반복조건은 중복이 가능하기 때문에 visited 체크는 하지않아도 되고, 멈추는 조건에서 출력할 데이터를 저장할 곳에 입력으로 받은 데이터를 i부터 n번째 까지 순서대로넣어주면 됩니다. 처음에는 백트래킹이 정말 어려운거같은데, 손으로 스택을 그려가면서 하면 정말 쉽게 이해가 가능합니다

전체 코드

전체 코드

문제

N과 M (3)

풀이

1-n가지의 자연수를 m개씩 뽑는 경우의 수를 전부 출력하면 된다 백트래킹 문제중에선 굉장히 유명하고 연습하기 좋은 문제같다.

백트래킹은 반복문과 멈추는 조건을 정의를 먼저 해야한다. 멈추는 조건은 3개까지 모두 뽑혔을때 멈추면 된다. 그리고 1-n의 숫자를 사용하는 경우의 수기 때문에 1-n까지 반복해야한다.

private static int dfs(int depth, int m) {
    // m개를 모두 고름
    if (depth == m) {
        for (int x : arr) {
            sb.append(x).append(" ");
        }
        sb.append("\n");
        return;
    }

    // 1- N 의 숫자를 모두 쓰는 경우의 수
    for (int i = 1; i <= n; i++) {
        arr[depth] = i;
        dfs(depth + 1, m);
    }
}

전체 코드

전체 코드

문제

카드놀이

풀이

마지막에 이긴 사람을 저장하는 String변수를 만들고 마지막에 한번더 sumA와 sumB를 비교를 해줘야 한다. 마지막에 이겼다고 모든 카드 놀이에서 이긴것이 아니기 때문에 마지막에 비교하는 문장이 없으면 틀린다. 실제로 이런 문제에서 코테에서 당황해버린 경우가 많았던것같다.

전체 코드

전체 코드

문제

팩토리얼 2

풀이

팩토리얼은 너무 많이 쓰던거라 익숙하다. 재귀형으로 쓰면 라인 하나만써도 뚝딱 .. 다만 이 문제는 long 형으로 리턴 받아야한다.

    private static long factorial(int n) {
        if (n == 1 || n == 0) return 1;
        return n * factorial(n - 1);
    }

전체 코드

전체 코드

문제

수강신청

풀이

linkedlist 를 했는데도 시간초과가 납니다.. 왜ㅈ ... ㅣ... contains도 안썼는데...

이유가 너무 궁금해서 찾아보니 linkedhashset은 add 및 remove의 속도가 O(1) 이고 linkedlist는 O(n) 이기 때문입니다 그래서 시간초과 인것이에용..[참고]

전체 코드

전체 코드

문제

숫자

풀이

a > b일수도 있고 b > a 일수도 있고 a = b 일수도 있기 때문에 케이스를 나누어서 작성해주어야 했다.

전체 코드

전체 코드

문제

ROT13

풀이

문제 자체에서 원하는것은 ascii코드에서 + 13을 하는것인데 char의 자료형이 취급하는 숫자는 -128부터 127 입니다. char에서 +13을 했울경우 (만약 주어진 문제에서 소문자 z가 주어졌을 경우) 이 범위를 초과할 수 있습니다. 이걸 의도하고 만들어진 문제같습니다

저의 경우에는 공백이 중복으로 계속 주어진 경우에 대해서 예외처리가 되지 않아서 몇번씩 틀렸던 문제였습니다

전체 코드

전체 코드

문제

토마토

풀이

이 문젠 솔직히 bfs의 전형적인 문제라 알고리즘을 틀렸다기 보다는 3차원 배열을 정의하는데 있어서 시간을 좀 더 많이 들였던것 같습니다. 저는 개인적으로 3차원 배열을 다를 수 있는 기회가 실제 프로젝트에서 있지는 않아서.. 아마 게임개발쪽이시면 그냥 푸실거같으네요.

BFS하면 큐겠죠. 큐를 정의하는데 저는 배열로 넣고 빼겠습니다.

Queue<int[]> q = new LinkedList<>();
// 높이
for (int i = 0; i < h; i++) {
    // 세로
    for (int j = 0; j < n; j++) {
        st = new StringTokenizer(br.readLine());
        // 가로
        for (int k = 0; k < m; k++) {
            box[i][j][k] = Integer.parseInt(st.nextToken());
            if (box[i][j][k] == 1) {
                q.add(new int[] {i, j, k});
            }
        }
    }
}

높이(h) 세로(y) 가로(x) 순으로 for문을 돌리고 높이, 세로, 가로 순으로 큐에 넣습니다. 큐에 넣는 이유는 1인 것부터 차례대로 BFS 큐에넣고 0인것을 바꿔주기 위해서 입니다.

    static int[] dx = {0, 0, -1, 1, 0, 0};
    static int[] dy = {-1, 1, 0, 0, 0, 0};
    static int[] dz = {0, 0, 0, 0, -1, 1};

이거는 그냥 문제에서 주어지는 대로 움직이는 범위를 정의한 배열입니다. 6개의 방향이있기때문에 정의해주는것입니다.

while (!q.isEmpty()) {
    int[] xy = q.poll();
    int z = xy[0];
    int x = xy[1];
    int y = xy[2];

    for (int i = 0; i < dx.length; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        int nz = z + dz[i];
        if (nx >= 0 && ny >= 0 && nz >= 0
                && nx < n && ny < m && nz < h) {
            if (box[nz][nx][ny] == 0) {
                box[nz][nx][ny] = box[z][x][y] + 1;
                q.add(new int[] {nz, nx, ny});
            }
        }
    }
}

본격적인 bfs 입니다. box배열에는 몇번째로 접근이 되는지를 depth + 1을 해주는 것입니다. 0인경우에만 접근해주면 되기 때문에 넘나 쉬움..

private static int validate() {
    int result = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < m; k++) {
                if (box[i][j][k] == 0) {
                    return -1;
                }
                result = Math.max(result, box[i][j][k]);
            }
        }
    }
    return result - 1;
}

그런다음에 배열이 모두 접근하였는지를 비교하겠습니다. depth는 앞서서 box배열에 넣어놨기 때문에 가장 큰 값으로 넣어주면 그 값이 문제어서 원하는 최소 일수가 됩니다. -1을 해주는 이유는 처음부터 배열에 1부터 정의되었기 때문에 이값을 없에주기 위함입니다.

전체 코드

전체 코드

문제

동전 1

풀이

dp배열은 n개를 만드는데 경우의 수를 값으로 넣습니다. 그래서 n개를 만들때 경우의수 k는 dp[n] = k 로 나타내기로 합니다 다이나믹 프로그래밍의 경우에는 규칙성을 파악해보기로 하는데 예시에서 주어진 1, 2, 5를 가지고 문제를 풀어볼수있는데요

dp[0] = 1; // 1개
dp[1] = 1; // 1 => 1개
dp[2] = 2; // 1,1 / 2 => 2개
dp[3] = 2; // 1,1,1 / 2,1 => 2개
dp[4] = 3; // 1,1,1,1 / 2,1,1 / 2,2 => 3개
dp[5] = 4; // 1,1,1,1,1 / 2,1,1,1 / 2,2,1 / 5 => 4개
...

이렇게 경우의 수를 나열하다 보면 규칙성이 존재함을 알수 있습니다. 바로 dp[n]은 이전의 dp[n]의 값에 영향을 받는 다는 것입니다.

일단 모든 n은 1로만 이루어질 수 있기에 모든 경우에 수(dp[n])에 +1를 기본적으로 해줍니다 또 2를 포함한 경우의 수는 dp[n] n은 2보다 큰 경우의 수 전부에 포함될것입니다. 그렇기 때문에 2이상인 경우 +1를 반복적으로 해주는 작업이 필요합니다.

또 dp[4] 의 경우인 4의 경우에는 2로만 이루어진 경우에 수가 딱하나더 추가가 될것입니다. 이 경우의 수를 나열하면서 규칙을 찾아보면 다음과같습니다.

dp[n] = dp[n] + dp[n - arr[i]];

더해지는 dp[n]은 이전의 dp[n]의 값을 말합니다. 그래서 이전의 값에 해당하는 것을 가져와서 dp[n - arr[i]] 을 더하면 이것이 바로 n이 가지는 값이겠습니다.

이 수식을 가지고 전개합니다. 잘 이해했다면 정말 쉬운문제였겠지만 저는 이부분에 도달하는데도 오래걸렸기 때문에 ㅠㅠ

// 동전 n개를 차례대로 넣습니다.
for (int i = 0; i < n; i++) {
    // 가치 k가될때까지 경우의 수를 계속 더해줍니다.
    for (int j = arr[i] ; j <= k; j++) {
        dp[j] += dp[j - arr[i]];
    }
}

전체 코드

전체 코드

문제

이항 계수 2

풀이

이항계수는 수학 공식이 따로 있어서 거기에 대입해도 되는데요. 공식에서는 팩토리얼을 구현해야하는데.. 자바 내장함수에는 팩토리얼이 없어서 구현을 해야하는디, 팩토리얼 구현하면 스택 오버 플로우 일것입니다.

대부분은 파스칼의 삼각형을 가지고 구현하는 것이 나은가봅니다. 파스칼의 삼각형은... 베스트셀러 수학귀신에 나오는 내용입니다

1
11
121
1331
14641
...
...

여기에서 배열 arr[a][b] 를 구하면 그것이 이항계수입니다.

for (int i = 0; i <= a; i++) {
    for (int j = 0; j <= i; j++) {
        if (i == 0 || j == 0) arr[i][j] = 1;
        else arr[i][j] = (arr[i - 1][j - 1] + arr[i - 1][j]) % 10007;
    }
}

전체 코드

전체 코드

문제

주유소

풀이

이문제에서 주어지는 n은 주유소가 n개 있으며 가야하는 거리는 n - 1개 있다고 생각하는 것이다. 문제가 조금 장황하게 써있지만 그런 내용이다. 그래서 이전 리터당 금액이 저렴하면 이전주유소에서 갈만큼의 양을 전부 주유하면 된다.

이전에 연료 채우기문제 와는 다른 내용인데 여기에선 각 주유소 마다 주유할 수 있는 연료의 양이 정해져있었다

이문제서는 리터당 가격만 정해져있고 주유 제한이 없다. 그렇기 때문에 정말 싼곳에서만 많이 주유하면 되겠다

일단 처음에 갈수있는 곳은 전부 주유해야 하기 때문에 다음과 같이 정의하겠다

// 총 금액 = 리터당 금액 * 가야하는 거리
int answer = oil[0] * arr[1];
// 리터 당 금액
int current = oil[0];

일단 이렇게 셋팅해주는 이유는 arr[1]은 가야 하기 때문이다. 그렇기 때문에 1부터 마지막까지 가기 위해서는 반복문을 사용해준다

for (int i = 1; i < n; i++) {
    // 가장 적은 기름 당 가격을 갱신한다
    current = Math.min(current, oil[i]);
    // 다음 정류장을 가기 위해 기름을 충전한다
    answer += current * arr[i + 1];
}

리터당 금액이 가장 적은 곳을 갱신하고 그 금액만큼 더해주면 가장 적은 금액으로 주유할 수 있다

전체 코드

전체 코드