반응형

 

문제출처

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

 

1062번: 가르침

첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문

www.acmicpc.net

 

문제풀이

문자열을 처리하는 문제이다. 문제에서 남극언어는 "anta"로 시작되고 "tica"로 끝난다고 주어졌다. 즉 모든 언어를 읽기 위해서는 "a", "n", "t", "i", "c"는 무조건 배워야 한다는 것이다. 즉 k가 주어졌을때 이 5개는 배웠다 생각하고 처리했다. 주어진 n개의 단어에서 replaceAll 메서드를 활용해 5개 문자를 제외시켰고 문자를 배웠음을 의미하는 visit배열을 true처리해줬다.

이후 dfs를 이용해서 k개의 단어를 배울때까지 모든 방법을 전체 탐색해 k개의 단어를 배웠다면 읽을 수 있는 단어의 갯수를 카운팅해주는 방식으로 풀이했다.

 

지금 생각해보니 visit배열대신 비트마스크를 사용해도 될것같다. 아래글처럼 visit배열대신 비트마스크를 사용할 수 있다. 

 

프로그래머스 64064] - 카카오 불량 사용자

 

[프로그래머스 64064] - 카카오 불량 사용자

문제출처 https://programmers.co.kr/learn/courses/30/lessons/64064 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 무지는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법

swjeong.tistory.com

 

 

 

소스코드

https://github.com/sw93/algorithm/blob/master/BOJ_PS/BOJ_1062.java

 

sw93/algorithm

problem solve. Contribute to sw93/algorithm development by creating an account on GitHub.

github.com

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ1062 {
    private static int n, k, ans;
    private static String[] words = new String[51];
    private static boolean[] visit = new boolean[26];
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer st;

    private static void init() throws Exception {
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        for (int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            String word = st.nextToken();

            // a n t i c 필수
            word = word.replaceAll("a" , "");
            word = word.replaceAll("n" , "");
            word = word.replaceAll("t" , "");
            word = word.replaceAll("i" , "");
            word = word.replaceAll("c" , "");
            words[i] = word;
        }
        visit['a'-'a'] = true;
        visit['n'-'a'] = true;
        visit['t'-'a'] = true;
        visit['i'-'a'] = true;
        visit['c'-'a'] = true;

    }
    private static void checkString() {
        int count = 0;

        for (int i=0; i<n; i++) {
            boolean isRead = true;
            for (int j=0; j<words[i].length(); j++) {
                if (!visit[words[i].charAt(j) - 'a']) {
                    isRead = false;
                    break;
                }
            }

            if (isRead) {
                count++;
            }
        }
        ans = Math.max(ans, count);
    }

    private static void dfs(int index, int depth) {
        if (depth == k) {
            checkString();
            return;
        }

        for (int i=index; i<26; i++) {
            if (visit[i]) continue;

            visit[i] = true;
            dfs(i, depth+1);
            visit[i] = false;
        }
    }

    public static void main(String[] args) throws Exception {
        init();
        // a n t i c 필수
        if (k < 5) {
            System.out.println(0);
            return;
        } else if (k == 26) {
            System.out.println(n);
            return;
        }
        k -= 5;
        dfs(0, 0);
        System.out.println(ans);
    }
}
반응형
반응형

문제출처

https://programmers.co.kr/learn/courses/30/lessons/1829

 

코딩테스트 연습 - 카카오프렌즈 컬러링북

6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5]

programmers.co.kr

 

문제풀이

삼성 역량테스트를 준비할때 많이 풀어본 유형이다. 기본적인 BFS문제로 완전탐색을 했다. BFS탐색을 할때마다 영역의 개수가 1개씩 증가하고 각 영역의 크기를 구하면 되는 문제다.

 

 

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20-%20%EC%B9%B4%EC%B9%B4%EC%98%A4%ED%94%84%EB%A0%8C%EC%A6%88%20%EC%BB%AC%EB%9F%AC%EB%A7%81%EB%B6%81.cpp

 

sw93/algorithm

problem solve. Contribute to sw93/algorithm development by creating an account on GitHub.

github.com

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int dy[] = { 0, -1, 0, 1 };
const int dx[] = { 1, 0, -1, 0 };
bool visit[100][100] = { 0, };
int bfs(int sy, int sx, int m, int n, vector<vector<int>> picture) {
    int color = picture[sy][sx];
    int size = 1;
    queue<pair<int, int> > q;
    q.push(make_pair(sy, sx));
    visit[sy][sx] = 1;
    
    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        
        for (int i=0; i<4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny<0 || nx<0 || ny>=m || nx>=n || visit[ny][nx] || picture[ny][nx] != color) continue;
            visit[ny][nx] = 1;
            q.push(make_pair(ny, nx));
            size++;
        }
    }
    return size;
}
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    for (int y=0; y<m; y++) {
        for (int x=0; x<n; x++) {
            visit[y][x] = 0;
        }
    }
    int areaCount = 0;
    int maxAreaCount = 0;
    for (int y=0; y<m; y++) {
        for (int x=0; x<n; x++) {
            if (visit[y][x] || picture[y][x] == 0) continue;
            maxAreaCount = max(maxAreaCount, bfs(y, x, m, n, picture));
            areaCount++;
        }
    }
    vector<int> answer(2);
    answer[0] = areaCount;
    answer[1] = maxAreaCount;   
    return answer;
}
반응형
반응형

문제 출처

https://programmers.co.kr/learn/courses/30/lessons/49994

 

코딩테스트 연습 - 방문 길이

 

programmers.co.kr

 

문제 풀이

문제가 엄청 직관적이라 금방 풀었다. 방향문자열을 1개씩 받아와 동,서,남,북 방향을 결정하고 위치를 이동하면 됩니다.

visit배열이 4차원배열인 이유는 방향성그래프가 아니기 때문입니다. 즉 (y, x) -> (ny, nx)로 이동했다면 (ny, nx) -> (y, x)의 길을 걸었기 때문에 이를 체크하기 위함입니다.

삼성 역량테스트 기출과 유형이 비슷한 문제

 

 

소스 코드

https://github.com/sw93/algorithm/blob/master/Programmers/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20-%20%EB%B0%A9%EB%AC%B8%20%EA%B8%B8%EC%9D%B4.java

 

sw93/algorithm

problem solve. Contribute to sw93/algorithm development by creating an account on GitHub.

github.com

class Solution {
    private static int dy[] = { 0, 1, 0, -1 };
    private static int dx[] = { 1, 0, -1, 0 };
    private static boolean visit[][][][] = new boolean[11][11][11][11];
    
    public int solution(String dirs) {
        int answer = 0;
        int y = 5;
        int x = 5;
        
        int dirIndex = 0;
        for (int i=0; i<dirs.length(); i++) {
            char dir = dirs.charAt(i);
            if (dir == 'U') {
                dirIndex = 3;
            } else if (dir == 'D') {
                dirIndex = 1;
            } else if (dir == 'R') {
                dirIndex = 0;
            } else if (dir == 'L') {
                dirIndex = 2;
            }
            
            int ny = y + dy[dirIndex];
            int nx = x + dx[dirIndex];
            
            // 지도를 벗어난 경우는 제외
            if (ny<0 || nx<0 || ny>=11 || nx>=11) continue;
            
            // (y,x) => (ny, nx)로 가는 길을 처음 걸을때
            if (!visit[y][x][ny][nx] == true && !visit[ny][nx][y][x] == true) {
                visit[y][x][ny][nx] = true;
                visit[ny][nx][y][x] = true;   
                answer++;            
            }
            
            // 현재 좌표 갱신
            y = ny;
            x = nx;
        }
        return answer;
    }
}

 

반응형
반응형

문제출처

https://programmers.co.kr/learn/courses/30/lessons/64064

 

코딩테스트 연습 - 불량 사용자

개발팀 내에서 이벤트 개발을 담당하고 있는 무지는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 ��

programmers.co.kr

 

문제풀이

정규표현식과 완전탐색으로 풀이하면 되는 문제입니다. DFS시 저는 bitmask를 visit배열 대신 사용해서 풀이했습니다. 

문제를 풀이할때 제가 생각한 알고리즘은 다음과 같습니다.

 

1. *문자를 정규표현식에 맞게 .로 치환

2. pattern과 matcher를 사용해 응모자 아이디와 매칭되는지 판단

3. 매칭이 된다면 길이가 같은지 판단

4. 이미처리한 사항(방문한 사항)이라면 건너뛰고 처리하지 않았다면 dfs함수를 호출

5. banned_id와 지금까지 찾아낸 제제된 아이디의 사이즈(bannedIdSize)가 같다면 set에 추가

6. 중복없는 set의 사이즈를 반환

 

비트마스크가 익숙하지 않은 분이면 아래 포스팅을 참고하시면 도움이 되실겁니다.

2019/01/28 - [Algorithm 이론] - [Bitmask] 비트마스크 기초

 

[Bitmask] 비트마스크 기초

Bitmask 컴퓨터는 이진번 관련 연산들을 매우 빠르게 진행할 수 있는데, 이러한 특성들을 사용하여 이진수 표현을 자료구조로 사용하는 기법을 비트마스크라고 합니다. 비트마스크는 자료구조라�

swjeong.tistory.com

레벨3문제인데 개인적으로 어렵게 풀이한 문제였습니다. 정규표현식과 비트마스크 개념을 다시 확인할 수 있던 문제

 

 

 

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%EC%B9%B4%EC%B9%B4%EC%98%A4%20-%20%EB%B6%88%EB%9F%89%20%EC%82%AC%EC%9A%A9%EC%9E%90.java

 

sw93/algorithm

problem solve. Contribute to sw93/algorithm development by creating an account on GitHub.

github.com

import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

// * 문자 . 로 치환
// Pattern matcher를 사용해 해당되는 문자인지 판단
// 해당된다면 길이도 같은지 확인하고 이미 추가한 아이디가 아니라면 set에 추가
class Solution {
    private static HashSet<Integer> set;
    public int solution(String[] user_id, String[] banned_id) {
        set = new HashSet<>();
        dfs(user_id, banned_id, 0, 0, 0);
        return set.size();
    }
    
    private static void dfs(String[] user_id, String[] banned_id, int index, int bannedIdSize, int visitBit) {
        if (bannedIdSize == banned_id.length) {
            set.add(visitBit);
            return;
        }
        
        for (int i=0; i<user_id.length; i++) {
            String changeBannedId = banned_id[index].replace("*", ".");
            Pattern pattern = Pattern.compile(changeBannedId);
            Matcher matcher = pattern.matcher(user_id[i]);
            
            // 정규 표현식에 매칭되고 길이가 같으면
            if (matcher.find() && user_id[i].length() == banned_id[index].length()) {
                
                // 이미 방문한 것은 건너뜀
                if ((visitBit & (1<<i)) == 1<<i) continue;
                dfs(user_id, banned_id, index+1, bannedIdSize+1, (visitBit | (1<<i)));
            }
        }
    }
}

 

반응형
반응형

문제출처

https://programmers.co.kr/learn/courses/30/lessons/64062

 

코딩테스트 연습 - 징검다리 건너기

[2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3

programmers.co.kr

 

문제풀이

문제를 풀기 이전에 이분탐색에 대해 익숙하지 않다면 이글을 먼저 읽는게 이해가 빠르실 겁니다.

[Algorithm] - [프로그래머스 43238] - 입국심사

 

[프로그래머스 43238] - 입국심사

문제출처 https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시�

swjeong.tistory.com

입국심사 문제와 같이 이분탐색을 이용한 문제입니다. 

한번에 건너뛸 수 있는 칸수 = k
stones = 징검다리 값

lowCount = 최소 인원수

highCount = 최대 인원수

averageCount = 건널 수 있는 인원수

 

문제의 핵심은 이분탐색 문제로 재해석 하는 것이다. 건넌 사람이 3명인경우 stone[i] - 3의 값이 양수여야 다리가 남아있는 경우이다. 이외의 경우 징검다리가 사라진 경우여서 건너뛰어야 하며 건너뛰는 징검다리 수를 저장하는 jumpCount변수에 저장한다.

jumpCount 변수는 최대 점프 횟수인 k를 넘을 수 없으며 k이상인 경우 최대 건너뛸 수 있는 사람의 제한을 줄여 재 탐색한다.

 

n = 건넌 사람

stones[i] = 징검다리 값

 

 

문제를 푸는데 입국심사 문제가 큰 도움이 되었다. 이해가 잘 되지 않는다면 위에있는 입국심사 포스팅을 읽고 문제를 풀어보면 더 쉬울거라 생각된다.

 

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%EC%B9%B4%EC%B9%B4%EC%98%A4%20-%20%EC%A7%95%EA%B2%80%EB%8B%A4%EB%A6%AC%20%EA%B1%B4%EB%84%88%EA%B8%B0.java

 

sw93/algorithm

problem solve. Contribute to sw93/algorithm development by creating an account on GitHub.

github.com

class Solution {
   
    public int solution(int[] stones, int k) {
        int answer = 0;
        
        // 건너뛰는 최소 인원수
        int lowCount = 1;   
        
        // 건너뛰는 최대 인원수
        int highCount = Integer.MAX_VALUE;  
        
        // 이분탐색에서 이용할 중간값
        int averageCount = (lowCount + highCount) / 2;  
        
        while (lowCount <= highCount) {
            averageCount = (lowCount + highCount) / 2;
            
            // 건너뛴 징검다리 수
            int jumpCount = 0;
            for (int i=0; i<stones.length; i++) {
                if (stones[i] - averageCount <= 0) {
                    jumpCount++;
                } else {
                    jumpCount = 0;
                }
                
                // k개 이상 건너뛰어야 하는경우 건너뛰는 인원수를 반으로 줄인다
                if (jumpCount >= k) {    
                    highCount = averageCount - 1;
                    break;
                }
            }
            
            // 건너뛴 징검다리 개수가 k개 미만인 경우 인원수를 늘린다.
            if (jumpCount < k) {
                lowCount = averageCount + 1;
                answer = lowCount;
            }  
        }

        return answer;
    }
}
반응형
반응형

문제출처

https://programmers.co.kr/learn/courses/30/lessons/43238

 

코딩테스트 연습 - 입국심사

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 �

programmers.co.kr

 

문제풀이

이분탐색을 응용한 문제입니다. 처음에 왜 이문제가 이분탐색인지 몰랐는데 다른 블로그를 보면서 이해할 수 있었습니다. 이 문제는 times배열에 각 심사관이 한명을 심사하는데 걸리는 시간 정보가 주어지고 n명을 모두 심사할 때 심사시간의 최소값을 구하는 문제입니다.

 

n의 최대값은 10억이며 times의 최대 크기는 10만입니다. n의 값이 크기 때문에 일반적인 풀이로는 풀수 없고 시간복잡도를 줄일 수 있는 답안을 생각해야 합니다.

 

입출력 예시로 주어진 대로 6명을 심사하고 각각 7분, 10분이 걸리는 2명의 심사관이 있는 경우를 생각해보겠습니다.

걸리는 시간을 기준으로 이분탐색을 할 예정이며 최소시간은 1분 최대시간은 n X 가장 오래걸리는 심사관의 시간 으로 시작했습니다. 이 문제에서 이분탐색을 할 때 핵심은 mid시간 이내에 심사가능한 인원의 수는 sum(mid / times[i])라는 것입니다.

 

최소시간을 left, 최대시간을 right변수에 담아 평균 시간을 mid에 저장합니다. 즉 1 // 30 // 60 으로 이분탐색을 시작합니다.

mid = 30

30분 이내에 심사가능한 인원은 (30 / 7) + (30 / 10) 으로  4 + 3 = 7명입니다.

7은 6보다 크므로 6명을 심사하기 위해서는 30분보다 더 적은 시간에도 가능한 것을 유추할 수 있습니다. 즉 rigth 변수값을 mid - 1을 해 29로 저장한뒤 재탐색 합니다. 이때 29분에는 6명을 심사할 수 없을 수도 있기 때문에 answer에 mid값을 저장합니다.

 

mid = (1 + 29) / 2 = 15

1 // 30 // 60 에서 1 // 15 // 30 으로 탐색범위가 반으로 줄었습니다. 15분 이내에 심사가능한 인원은 (15 / 7) + (15 / 10) = 2 + 1 = 3명입니다. 3은 6보다 작으므로 6명을 심사하기 위해서는 15분보다는 더 시간이 필요한 것을 알 수 있습니다. 이분탐색을 위해 left 값을 1에서 16으로 바꾼 후 탐색을 다시 시작합니다.

 

mid = (16 + 30) / 2 = 22

1 // 15 // 30 에서 16 // 22 // 30 으로 탐색범위가 또 반으로 줄었습니다. 22분 이내에 심사가능한 인원은 (22 / 7) + (22 / 10) = 3 + 2 = 5명입니다. 5는 6보다 작으므로 6명을 심사하기 위해서는 22분보다 시간이 더 필요합니다. left 값을 16에서 23으로 바꾼 뒤 탐색을 다시 시작합니다.

 

반복해서 나아가면

mid = (23 + 30) / 2 = 26

....

 

mid =  (26 + 30) / 2 = 28

(28 / 7) + (28 / 10) = 4 + 2 = 6명이므로 28이 정답임을 알 수 있습니다.

 

각각의 탐색과정에서 범위가 반으로 줄고 있으므로 시간복잡도는 O(logN)입니다.

 

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20-%20%EC%9E%85%EA%B5%AD%EC%8B%AC%EC%82%AC.java

 

sw93/algorithm

problem solve. Contribute to sw93/algorithm development by creating an account on GitHub.

github.com

 

import java.util.Arrays;
class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        Arrays.sort(times);
        
        long left = 1;
        long right = (long)n * times[times.length - 1];
        while (left <= right) {
            long mid = (left + right) / 2;
            long count = 0;
            
            // 심사 가능한 인원 = 시간 / 심사하는데 걸리는 시간
            for (int i=0; i<times.length; i++) {
                count += mid / times[i];
            }
            
            // mid 시간동안 심사한 인원이 n명보다 적은 경우 시간이 더 필요
            if (count < n) {
                left = mid + 1;
            } else { // 심사한 인원이 n명 이상인 경우 시간을 줄여도 됨
                right = mid - 1;
                answer = mid;
            }
        }
        
        return answer;
    }
}
반응형
반응형

문제출처

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

 

코딩테스트 연습 - 영어 끝말잇기

3 [tank, kick, know, wheel, land, dream, mother, robot, tank] [3,3] 5 [hello, observe, effect, take, either, recognize, encourage, ensure, establish, hang, gather, refer, reference, estimate, executive] [0,0]

programmers.co.kr

 

문제풀이

이 문제도 역시 중복을 검사하는 문제다. 중복을 검사하길래 바로 set자료구조를 떠올려서 풀었다. 사실 set 자료구조보다 사람순서와 언제 틀렸는지 구하는 규칙을 찾아내는게 주요 목적이다. 중복검사는 set이 아니여도 충분히 가능하기 때문이다.

전에 말했던 마지막글자와 첫글자가 다르거나 중복된경우 순서를 저장하고 retrun하면 되기 때문에 같은 if문에 묶어 처리했다.

 

같은 level2문제여도 카카오 level2가 더 어렵게 느껴진다 ㅠ 생각할 것도 많고... 이 문제는 level1정도로 생각된다.

 

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20-%20%EC%98%81%EC%96%B4%20%EB%81%9D%EB%A7%90%EC%9E%87%EA%B8%B0.java

 

sw93/algorithm

problem solve. Contribute to sw93/algorithm development by creating an account on GitHub.

github.com

 

import java.util.*;
class Solution {
    // n명 
    // i % n 값에 +1 한게 사람순서
    // i / n 값에 +1 한게 차례
    // 끝글자랑 다음의 처음글자 확인
    public int[] solution(int n, String[] words) {
        int[] answer = {0, 0};
        Set<String> historySet = new HashSet<>();
        historySet.add(words[0]);
        char prevCharacter = words[0].charAt(words[0].length() - 1);
        
        for (int i=1; i<words.length; i++) {
            historySet.add(words[i]);
            if (!words[i].startsWith(Character.toString(prevCharacter)) || historySet.size() != i+1) {
                answer[0] = (i%n)+1;
                answer[1] = (i/n)+1;
                break;
            }
            prevCharacter = words[i].charAt(words[i].length() - 1);
        }
        return answer;
    }
}
반응형
반응형

문제출처

https://programmers.co.kr/learn/courses/30/lessons/12980

 

코딩테스트 연습 - 점프와 순간 이동

OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈�

programmers.co.kr

문제풀이

이런 문제는 계속 예제를 만들고 시뮬레이션을 돌리며 규칙을 찾아야 하는거 같다. 시간도 많이 잡아먹고 어렵게 느껴진다 ㅠ

문제에서 주어진대로 위치 0에서 n까지 가는 구조로 하다보니 규칙을 찾기 어려웠다. 그래서 n에서 0으로 가는 구조로 다시 생각해봤다. 문제를 풀때 핵심 키워드로 작용한 내용은 순간이동에 대한 조건이다. (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동

즉, 순간이동을 하면 짝수가 된다는 점에서 짝수와 홀수간 규칙이 있지 않을까 의심해봤다. 짝수인 경우 순간이동을 하고 홀수인 경우 1칸만 점프하면 배터리 사용량을 최소화 할 수 있다.

 

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20-%20%EC%A0%90%ED%94%84%EC%99%80%20%EC%88%9C%EA%B0%84%EC%9D%B4%EB%8F%99.java

 

sw93/algorithm

problem solve. Contribute to sw93/algorithm development by creating an account on GitHub.

github.com

 

import java.util.*;
/**
* k칸 앞으로 점프 || 현재까지 온거리 * 2
* k칸 점프시 건전지 사용
* n만큼 떨어져 있는 곳으로 이동할 때 건전지 사용량을 최소로하는 값 return
* top - down 방식으로 풀이
*/
public class Solution {
    public int solution(int n) {
        int ans=0;
        while (n > 0) {
            if (n % 2 == 0) {
                n /= 2;
            } else {
                ans++;
                n -= 1;
            }
        }
        return ans;
    }
}

 

 

문제를 다 풀고 다른사람 풀이를 찾아보는 중에 생각지도 못한 방법이 있었다. 비트를 사용하는 방법인데 자세한 설명은 아래 블로그를 참조하면 된다.

public int solution(int n) {
	return Integer.bitCount(n);
}

출처 : https://taesan94.tistory.com/142

반응형
반응형

문제출처

https://programmers.co.kr/learn/courses/30/lessons/1845

 

코딩테스트 연습 - 폰켓몬

당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. �

programmers.co.kr

 

문제풀이

단순하게 구현을 할 수도 있지만 Set자료구조를 사용하면 더 빠르고 쉽게 풀수 있는 문제다. nums배열의 크기가 n인경우 선택할 수 있는 폰켓몬의 수는 n/2마리인데 n/2마리를 선택할 때 폰켓몬의 종류를 출력하는 문제다.

폰켓몬의 종류의 수만 알면 되기 때문에 몇번째 폰켓몬이 선택되었는지는 중요하지 않다. 즉 중복되지 않은 자료만 유효하다. 그래서 Set자료구조를 생각하게 되었다.

선택한 폰켓몬의 최대값은 n/2이고 최소값은 1이다. 즉, Set에 모든 폰켓몬의 자료를 넣어 중복을 없앤뒤 Set의 크기가 n/2보다 크면 n/2를 아니면 Set의 크기를 반환해주면 된다.

 

 

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20-%20%ED%8F%B0%EC%BC%93%EB%AA%AC.java

 

sw93/algorithm

problem solve. Contribute to sw93/algorithm development by creating an account on GitHub.

github.com

 

import java.util.*;
class Solution {
    public int solution(int[] nums) {
        Set<Integer> phoneketmonSet = new HashSet<>();
        int pickSize = nums.length / 2;
        for (int num : nums) {
            phoneketmonSet.add(num);
        }
        
        return pickSize > phoneketmonSet.size() 
                    ? phoneketmonSet.size() : pickSize;
    }
}
반응형
반응형

문제출처

https://programmers.co.kr/learn/courses/30/lessons/17686

 

코딩테스트 연습 - [3차] 파일명 정렬

파일명 정렬 세 차례의 코딩 테스트와 두 차례의 면접이라는 기나긴 블라인드 공채를 무사히 통과해 카카오에 입사한 무지는 파일 저장소 서버 관리를 맡게 되었다. 저장소 서버에는 프로그램��

programmers.co.kr

문제풀이

Java에서 사용자 정의로 정렬을 진행할때 Comparator를 사용한다. 이 문제는 Comparator를 사용할 줄 아는지 묻는 문제이다. 파일명을 head, number, tail로 분리한뒤 정렬을 다음 순서에 맞게 진행하면 된다.

head를 기준으로 문자열 오름차순으로 먼저 정렬한다. 이 때 대소문자 구분을 하지 않기 때문에 본인은 소문자로 통일한뒤 진행했다. head가 같은경우 number로 정렬하고 number도 같다면 기존 files의 순서를 지키면 된다.

 

풀이 자체가 Comparator 인터페이스를 구현하고 있다. 정렬을 할때 Comparator와 Comparable을 사용하곤 하는데 자세한 내용은 https://swjeong.tistory.com/198?category=778818 이 글을 참조하면 된다.

 

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%EC%B9%B4%EC%B9%B4%EC%98%A4%20-%20%ED%8C%8C%EC%9D%BC%EB%AA%85%20%EC%A0%95%EB%A0%AC.java

 

sw93/algorithm

problem solve. Contribute to sw93/algorithm development by creating an account on GitHub.

github.com

 

import java.util.*;
class Solution {
    public String[] solution(String[] files) {
        
        Arrays.sort(files, new Comparator<String>() {
           public int compare(String s1, String s2) {
               String head1 = s1.split("[0-9]")[0];
               String head2 = s2.split("[0-9]")[0];
               s1 = s1.replace(head1, "");
               s2 = s2.replace(head2, "");
               
               head1 = head1.toLowerCase();
               head2 = head2.toLowerCase();
               
               // compareTo(x, y) => [ -1 : x < y | 0 : x == y | 1 : x > y ]
               int headCompareValue = head1.compareTo(head2);
               if (headCompareValue == 0) {
                   
                  // head정렬 값이 같으므로 number로 정렬
                  String num1 = "";
                  for (char c : s1.toCharArray()) {
                      if (!(c >= '0' && c <= '9')) break;
                      num1 += c;
                  }
                  String num2 = "";
                  for (char c : s2.toCharArray()) {
                     if (!(c >= '0' && c <= '9')) break;
                     num2 += c;
                  }
                  return (Integer.parseInt(num1) - Integer.parseInt(num2));
               } else {
                   return headCompareValue;
               }
           }
        });
        
        return files;
    }
}
반응형

+ Recent posts