쌉쌀한 무화과의 개발로그

[문제 설명]

여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브는 사용자들이 편리하게 다양한 뉴스를 찾아볼 수 있도록 문제점을 개선하는 업무를 맡게 되었다.

개발의 방향을 잡기 위해 튜브는 우선 최근 화제가 되고 있는 "카카오 신입 개발자 공채" 관련 기사를 검색해보았다.

​

• 카카오 첫 공채..'블라인드' 방식 채용

• 카카오, 합병 후 첫 공채.. 블라인드 전형으로 개발자 채용

• 카카오, 블라인드 전형으로 신입 개발자 공채

• 카카오 공채, 신입 개발자 코딩 능력만 본다

• 카카오, 신입 공채.. "코딩 실력만 본다"

• 카카오 "코딩 능력만으로 2018 신입 개발자 뽑는다"

​

기사의 제목을 기준으로 "블라인드 전형"에 주목하는 기사와 "코딩 테스트"에 주목하는 기사로 나뉘는 걸 발견했다. 튜브는 이들을 각각 묶어서 보여주면 카카오 공채 관련 기사를 찾아보는 사용자에게 유용할 듯싶었다.

유사한 기사를 묶는 기준을 정하기 위해서 논문과 자료를 조사하던 튜브는 "자카드 유사도"라는 방법을 찾아냈다.

자카드 유사도는 집합 간의 유사도를 검사하는 여러 방법 중의 하나로 알려져 있다. 두 집합 A, B 사이의 자카드 유사도 J(A, B)는 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값으로 정의된다.

예를 들어 집합 A = {1, 2, 3}, 집합 B = {2, 3, 4}라고 할 때, 교집합 A ∩ B = {2, 3}, 합집합 A ∪ B = {1, 2, 3, 4}이 되므로, 집합 A, B 사이의 자카드 유사도 J(A, B) = 2/4 = 0.5가 된다. 집합 A와 집합 B가 모두 공집합일 경우에는 나눗셈이 정의되지 않으니 따로 J(A, B) = 1로 정의한다.

자카드 유사도는 원소의 중복을 허용하는 다중집합에 대해서 확장할 수 있다. 다중집합 A는 원소 "1"을 3개 가지고 있고, 다중집합 B는 원소 "1"을 5개 가지고 있다고 하자. 이 다중집합의 교집합 A ∩ B는 원소 "1"을 min(3, 5)인 3개, 합집합 A ∪ B는 원소 "1"을 max(3, 5)인 5개 가지게 된다. 다중집합 A = {1, 1, 2, 2, 3}, 다중집합 B = {1, 2, 2, 4, 5}라고 하면, 교집합 A ∩ B = {1, 2, 2}, 합집합 A ∪ B = {1, 1, 2, 2, 3, 4, 5}가 되므로, 자카드 유사도 J(A, B) = 3/7, 약 0.42가 된다.

이를 이용하여 문자열 사이의 유사도를 계산하는데 이용할 수 있다. 문자열 "FRANCE"와 "FRENCH"가 주어졌을 때, 이를 두 글자씩 끊어서 다중집합을 만들 수 있다. 각각 {FR, RA, AN, NC, CE}, {FR, RE, EN, NC, CH}가 되며, 교집합은 {FR, NC}, 합집합은 {FR, RA, AN, NC, CE, RE, EN, CH}가 되므로, 두 문자열 사이의 자카드 유사도 J("FRANCE", "FRENCH") = 2/8 = 0.25가 된다.

​

[입력 형식]

입력으로는 str1과 str2의 두 문자열이 들어온다. 각 문자열의 길이는 2 이상, 1,000 이하이다.

입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만든다. 이때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다. 예를 들어 "ab+"가 입력으로 들어오면, "ab"만 다중집합의 원소로 삼고, "b+"는 버린다.

다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다. "AB"와 "Ab", "ab"는 같은 원소로 취급한다.

​

[출력 형식]

입력으로 들어온 두 문자열의 자카드 유사도를 출력한다. 유사도 값은 0에서 1 사이의 실수이므로, 이를 다루기 쉽도록 65536을 곱한 후에 소수점 아래를 버리고 정수부만 출력한다.

​

[예제 입출력]

>문제 풀이

주어진 문자열 str1, str2 사이의 유사도를 찾는 문제였습니다.

소문자와 대문자를 구분하지 않기 때문에 str1과 str2를 소문자 또는 대문자로 맞춰주는 작업을 해줘야합니다.

그리고 char 2개씩 잘라서 array list에 넣어주는데, 이때 구성 문자가 알파벳이 아니라면 넣지 않습니다.

그리고 교집합 개수와(intersection) 합집합 개수를(union) 구해줍니다.

자카드 유사도= intersection/union

​

우리는 (자카드 유사도)*65536 을 소수점 부분을 버리고 리턴해주면 됩니다.

단, 집합 A와 B가 모두 공집합일 경우 자카드 유사도가 1인 것을 처리해주어야 합니다.

>전체 코드

import java.util.ArrayList;
class Solution {
    public int solution(String str1, String str2) {
        int answer = 0, intersection=0, union=0;
		ArrayList<String> list1= new ArrayList<>();
		ArrayList<String> list2= new ArrayList<>();
		
		str1= str1.toUpperCase();
		str2= str2.toUpperCase();
		
		String temp;
		for(int i=0; i<str1.length()-1; i++) { //str1
			temp= str1.substring(i, i+2);
			if(!temp.matches("^[A-Z]*$")) continue;
			list1.add(temp);
		}
		
		for(int i=0; i<str2.length()-1; i++) { //str2
			temp= str2.substring(i, i+2);
			if(!temp.matches("^[A-Z]*$")) continue;
			list2.add(temp);
		}
		
		for(String s: list1) {
			if(list2.remove(s)) intersection++;
			union++;
		}
		
		for(String s: list2) {
			union++;
		}
		
		answer=(int)Math.floor((double)intersection/union*65536);
        if(list1.size()==0&&list2.size()==0) answer=65536;
        return answer;
    }
}

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

[문제 설명]

정수 n이 매개변수로 주어집니다. 다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요.

[제한사항]

n은 1 이상 1,000 이하입니다.

​

[입출력 예]

>문제 풀이

삼각형 모양을 배열에 왼쪽 정렬로 담는다고 생각합니다.

그럼 아래 그림의 우측 그림처럼 값이 들어가야겠죠.

이렇게 되면, 3가지 동작으로 이동하면서 idx++값이 들어가게 됩니다.

이동 횟수는 dx[0][0]~dx[5][0]까지 6번 아래로, 5칸 오른쪽, 대각선 4칸, 아래 3칸, 오른쪽 2칸, 대각선 1칸으로 n--로 반복하게 됩니다.

>전체 코드

class Solution {
    public int[] solution(int n) {
        int[] answer = new int[n*(n+1)/2];
        int[][] mat= new int[n][n];
        
        int x=-1, y=0, idx=1;
        for(int i=0; i<n; i++){
            for(int j=i; j<n; j++){
                if(i%3==0){ //아래로
                    x++;
                }else if(i%3==1){//오른쪽으로
                    y++;
                }else{//대각선으로
                    x--;
                    y--;
                }
                mat[x][y]= idx++;
            }
        }
        
        idx=0;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(mat[i][j]==0) break;
                answer[idx++]= mat[i][j];
            }
        }
        
        return answer;
    }
}

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

*참고한 블로그

https://minhamina.tistory.com/58

[문제설명]

셀수있는 수량의 순서있는 열거 또는 어떤 순서를 따르는 요소들의 모음을 튜플(tuple)이라고 합니다. n개의 요소를 가진 튜플을 n-튜플(n-tuple)이라고 하며, 다음과 같이 표현할 수 있습니다.

• (a1, a2, a3, ..., an)

​

튜플은 다음과 같은 성질을 가지고 있습니다.

1. 중복된 원소가 있을 수 있습니다. ex : (2, 3, 1, 2)

2. 원소에 정해진 순서가 있으며, 원소의 순서가 다르면 서로 다른 튜플입니다. ex : (1, 2, 3) ≠ (1, 3, 2)

3. 튜플의 원소 개수는 유한합니다.

​

원소의 개수가 n개이고, 중복되는 원소가 없는 튜플 (a1, a2, a3, ..., an)이 주어질 때(단, a1, a2, ..., an은 자연수), 이는 다음과 같이 집합 기호 '{', '}'를 이용해 표현할 수 있습니다.

• {{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4}, ... {a1, a2, a3, a4, ..., an}}

​

예를 들어 튜플이 (2, 1, 3, 4)인 경우 이는

• {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}

와 같이 표현할 수 있습니다.

​

이때, 집합은 원소의 순서가 바뀌어도 상관없으므로

• {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}

• {{2, 1, 3, 4}, {2}, {2, 1, 3}, {2, 1}}

• {{1, 2, 3}, {2, 1}, {1, 2, 4, 3}, {2}}

는 모두 같은 튜플 (2, 1, 3, 4)를 나타냅니다.

​

특정 튜플을 표현하는 집합이 담긴 문자열 s가 매개변수로 주어질 때, s가 표현하는 튜플을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

​

[제한사항]

s의 길이는 5 이상 1,000,000 이하입니다.

s는 숫자와 '{', '}', ',' 로만 이루어져 있습니다.

숫자가 0으로 시작하는 경우는 없습니다.

s는 항상 중복되는 원소가 없는 튜플을 올바르게 표현하고 있습니다.

s가 표현하는 튜플의 원소는 1 이상 100,000 이하인 자연수입니다.

return 하는 배열의 길이가 1 이상 500 이하인 경우만 입력으로 주어집니다.

​

[입출력 예]

* 입출력 예에 대한 설명

입출력 예 #1

문제 예시와 같습니다.

​

입출력 예 #2

문제 예시와 같습니다.

​

입출력 예 #3

(111, 20)을 집합 기호를 이용해 표현하면 {{111}, {111,20}}이 되며, 이는 {{20,111},{111}}과 같습니다.

​

입출력 예 #4

(123)을 집합 기호를 이용해 표현하면 {{123}} 입니다.

​

입출력 예 #5

(3, 2, 4, 1)을 집합 기호를 이용해 표현하면 {{3},{3,2},{3,2,4},{3,2,4,1}}이 되며, 이는 {{4,2,3},{3},{2,3,4,1},{2,3}}과 같습니다.

>문제 풀이

s= {{2, 1, 3}, {2}, {2, 1}, {2, 1, 3, 4}};

​

1. 주어진 문자열을 쪼갠다.

arr[0]= "{2, 1, 3}"

arr[1]= "{2}"

arr[2]= "{2, 1}"

arr[3]= "{2, 1, 3, 4}"

​

2. arr를 문자열의 길이에 따라 정렬합니다.

arr[0]= "{2}"

arr[1]= "{2, 1}"

arr[2]= "{2, 1, 3}"

arr[3]= "{2, 1, 3, 4}"

​

3. 중복체크를 하면서 LinkedList에 넣어주고 다시 answer에 넣어줍니다.

list= 2, 1, 3, 4

answer[]={2, 1, 3, 4};

​

코드 개선

* 얼마전 코테 를 보면서,,

값의 들어온 순서대로 출력을 해야할 때 LinkedList를 써야한다는 것을 깨달았었다.

그래서 이번에도 LinkedList를 사용했는데, 다른분의 코드를 보고 리스트를 안써도 set을 사용해서 중복 체크만 하고 바로 answer[]에 넣어도 된다는 걸 알았다.

​

그래서 위에서는 1)s.split 및 정렬 // 2)중복체크 해서 list만들기 // 3)list를 다시 answer로 옮겨주기 3단계로 구현했지만, 아래의 로직이면 3)번 과정을 없앨 수 있다.

HashSet<Integer> set= new HashSet<>();
//String s를 split하고//
answer= new int[arr.length];

for(int i=0; i<arr.length; i++){
    String[] tuple= arr[i].split(",");
    for(int j=0; j<tuple.length; j++){
        if(!set.contains(Integer.parseInt(tuple[j])))
            answer[idx++]= Integer.parseInt(tuple[j]);
    }
}

근데 나는 s를 split해서 arr에 넣을때 "" 값이 들어가 있었기 때문에, 위의 방법으로 answer의 크기를 미리 지정해주려면 split 코드를 약간 수정해서 넣어야 할 것 같다.

+) 정렬 코드도 이런식으로 개선 할 수 있다.

Arrays.sort(arr, new Comparator<String>(){
    public int compare(String s1, String s2){
        return s1.length()-s2.length();
    }
});

//위의 코드를 아래처럼 수정 가능
Arrays.sort(arr, (s1, s2)->{return s1.length()-s2.length();});

>전체 코드

import java.util.*;
class Solution {
    public int[] solution(String s) {
        int idx=0;
        int[] answer = {};
        LinkedList<Integer> list= new LinkedList<>();
        
        String[] arr= s.split("\\{|\\},\\{|\\}");
        
        Arrays.sort(arr, new Comparator<String>(){
            public int compare(String s1, String s2){
                return s1.length()-s2.length();
            }
        });
        
        for(int i=0; i<arr.length; i++){
            if(arr[i].equals("")) continue;
            String[] tuple= arr[i].split(",");
            for(int j=0; j<tuple.length; j++){
                if(!list.contains(Integer.parseInt(tuple[j])))
                    list.add(Integer.parseInt(tuple[j]));
            }
        }
        
        answer= new int[list.size()];
        for(int i=0; i<list.size(); i++){
            answer[i]= list.get(i);
        }
        
        return answer;
    }
}

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

[문제 설명]

ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.

지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.

위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.

아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.

첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.

두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.

위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.

만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.

게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.

​

[제한사항]

maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.

n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.

maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.

처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.

​

[입출력 예]

* 입출력 예 설명

입출력 예 #1

주어진 데이터는 다음과 같습니다.

캐릭터가 적 팀의 진영까지 이동하는 가장 빠른 길은 다음 그림과 같습니다.

따라서 총 11칸을 캐릭터가 지나갔으므로 11을 return 하면 됩니다.

입출력 예 #2

문제의 예시와 같으며, 상대 팀 진영에 도달할 방법이 없습니다. 따라서 -1을 return 합니다.

>문제 풀이

최단거리를 구하기 위한 bfs 문제였습니다.

상하좌우로 갈 수 있게 하되, maps[][]==0인 곳은 못가고 이미 방문했던 곳은 못가도록 visited[][]를 체크해주며 카운트해나갑니다.

마지막 칸에 도달하지 못할수도 있으므로 bfs를 다 돌고나서 maps[n-1][m-1]==1이면 answer=-1;

​

>전체 코드

import java.util.*;
class Solution {
    public int solution(int[][] maps) {
        int n=maps.length, m=maps[0].length;
        int answer, x, y, nx, ny;
        int[] dx={-1, 0, 1, 0};
        int[] dy={0, -1, 0, 1};
        boolean[][] visited= new boolean[n][m];
        Queue<Integer> queue= new LinkedList<>();
        
        queue.offer(0);
        queue.offer(0);
        visited[0][0]= true;
        while(!queue.isEmpty()){
            x= queue.poll();
            y= queue.poll();
            
            for(int i=0; i<dx.length; i++){
                nx= x+dx[i];
                ny= y+dy[i];
                
                if(nx<0||nx>=n||ny<0||ny>=m) continue;
                if(maps[nx][ny]==0) continue;
                if(!visited[nx][ny]){
                    queue.offer(nx);
                    queue.offer(ny);
                    maps[nx][ny]=maps[x][y]+1;
                    visited[nx][ny]= true;
                }
            }
        }
        answer= maps[n-1][m-1];
        if(maps[n-1][m-1]==1) answer=-1;
        
        return answer;
    }
}

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

[문제 설명]

△△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N번의 참가자끼리 게임을 진행합니다. 각 게임에서 이긴 사람은 다음 라운드에 진출할 수 있습니다. 이때, 다음 라운드에 진출할 참가자의 번호는 다시 1번부터 N/2번을 차례대로 배정받습니다. 만약 1번↔2번 끼리 겨루는 게임에서 2번이 승리했다면 다음 라운드에서 1번을 부여받고, 3번↔4번에서 겨루는 게임에서 3번이 승리했다면 다음 라운드에서 2번을 부여받게 됩니다. 게임은 최종 한 명이 남을 때까지 진행됩니다.

이때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 궁금해졌습니다. 게임 참가자 수 N, 참가자 번호 A, 경쟁자 번호 B가 함수 solution의 매개변수로 주어질 때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 return 하는 solution 함수를 완성해 주세요. 단, A번 참가자와 B번 참가자는 서로 붙게 되기 전까지 항상 이긴다고 가정합니다.

​

[제한사항]

N : 21 이상 220 이하인 자연수 (2의 지수 승으로 주어지므로 부전승은 발생하지 않습니다.)

A, B : N 이하인 자연수 (단, A ≠ B 입니다.)

​

[입출력 예]

입출력 예 설명

입출력 예 #1

첫 번째 라운드에서 4번 참가자는 3번 참가자와 붙게 되고, 7번 참가자는 8번 참가자와 붙게 됩니다. 항상 이긴다고 가정했으므로 4번 참가자는 다음 라운드에서 2번이 되고, 7번 참가자는 4번이 됩니다. 두 번째 라운드에서 2번은 1번과 붙게 되고, 4번은 3번과 붙게 됩니다. 항상 이긴다고 가정했으므로 2번은 다음 라운드에서 1번이 되고, 4번은 2번이 됩니다. 세 번째 라운드에서 1번과 2번으로 두 참가자가 붙게 되므로 3을 return 하면 됩니다.

>문제 풀이

level 2 중에도 쉬운 문제 였습니다.

문제에 a, b는 N이하의 자연수라고만 적혀있어서 Math.min, Math.max로 순서 정리를 해주고

한 step 씩 올라가는 과정을 cnt++로 카운트 해주면 됩니다.

​

홀수 일때 ex) b=7이면 8이랑 붙어서 올라가게 되며 다음 단계에서 index 4가 됩니다.

즉, a, b가 홀수일 경우 (a+1)/2가 다음 단계의 index가 됩니다.

짝수일 경우에는 a/2를 넘겨주면 됩니다.

​

이것만 알면 풀 수 있는 문제였습니다.

>전체 코드

class Solution
{
    public int solution(int n, int a, int b)
    {
        return round(Math.min(a, b), Math.max(a, b));
    }
    
    public int round(int a, int b){
        int cnt=1;
        
        while(true){
            if (b%2==0 && a+1==b) break;
            if(a%2!=0) a+=1;
            if(b%2!=0) b+=1;
            a/=2;
            b/=2;
            cnt++;
        }
        
        return cnt;
    }
}

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