반응형

문제풀이

1.  각 행을 탐색하며 첫번째 #과 마지막 #의 위치를 찾습니다. (ES 버전문제인지, 마지막 #의 위치는 findLastIndex() 함수가 사용되지 않아 reverse()를 이용하여 뒤집어서 찾았습니다.)

2. 행의 위치의 경우 #이 존재하는 첫번째 행과, 마지막행+1(드래그 때문)로 설정해줍니다.

 

JS Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//https://school.programmers.co.kr/learn/courses/30/lessons/161990
function solution(wallpaper) {
    var answer = [-1,51,0,0];
    let rSize = wallpaper.length;
    let cSize = wallpaper[0].length;
    
    wallpaper.map(function(row, i){
        const tmp = row.split('');
        const min = tmp.findIndex((e) => e == '#');
        // findLastIndex 함수가 사용 안되서 뒤집어서 맨 뒤의 # 위치 찾기
        const maxTmp = tmp.reverse().findIndex((e) => e == '#');
        const max = (maxTmp != -1) ? cSize - maxTmp : -1
        
        if ( min != -1 && max != -1){
            if ( answer[0] == -1 ){
                answer[0] = i;
            }
            answer[2] = i;
        }
        if ( min != -1 && min < answer[1] ){
            answer[1] = min;
        }
        if ( max != -1 && max > answer[3]){
            answer[3] = max;
        }
    })
    answer[2]++;
    return answer;
}
 cs

 

 

문제 링크

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

반응형

'알고리즘 > 프로그래머스' 카테고리의 다른 글

[프로그래머스] 미로 탈출 JS  (1) 2023.03.05
[프로그래머스] 카드 뭉치 JS  (0) 2023.03.01
[프로그래머스] 대충 만든 자판 JS  (0) 2023.03.01
[프로그래머스] 보석 쇼핑 Python  (0) 2022.03.05
[프로그래머스] 후보키 Python  (0) 2022.03.01
반응형

문제풀이

1. 주어진 maps에서 S, L, E의 위치를 탐색합니다.

2. 다익스트라 알고리즘을 활용하여 S -> L, L ->E 까지의 최단시간을 탐색합니다.

3. S -> L, L -> E 모두 도달 가능한 경우, 두 시간을 합친 값을 반환합니다.

 

JS Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
//https://school.programmers.co.kr/learn/courses/30/lessons/159993
function solution(maps) {
    var answer = 0;
    let start = [0,0];
    let end = [0,0];
    let lever = [0,0];
    // S, L, E 좌표 탐색
    maps.map(function(row, i){
        let chk = 0;
        row.split('').map(function(r, j){
            if ( r == 'S' ){
                start = [i,j];
                chk += 1;
            }
            if ( r == 'E'){
                end = [i,j];
                chk += 1;
            }
            if ( r == 'L'){
                lever = [i,j];
                chk +=1
            }
            if ( chk == 3 ){
                return ;
            }
        })
        if ( chk ==3 ){
            return ;
        }
    })
    
    // S -> L 시간
    let a = dij(maps, start[0], start[1], lever[0], lever[1]);
    if ( a == 10001){
        return -1;
    }
    
    // L -> E 시간
    let b = dij(maps, lever[0], lever[1], end[0], end[1]);
    
    if ( b != 10001){
        return a+b;
    }else {
        return -1;
    }
}
 
// (r,c) -> (tr,tc) 걸리는 시간 반환
function dij(maps, r, c, tr, tc){
    let chk = Array.from(Array(maps.length), () => Array(maps[0].length).fill(0));
    let dist = Array.from(Array(maps.length), () => Array(maps[0].length).fill(10001));
    
    dist[r][c] = 0;
    
    let q = [[r,c]];
    while (q.length>0){
        let n = q.shift();
        if ( n[0]>0 && chk[n[0]-1][n[1]] == 0 && maps[n[0]-1][n[1]] != 'X'){
            dist[n[0]-1][n[1]] = Math.min(dist[n[0]][n[1]] + 1)
            chk[n[0]-1][n[1]] = 1;
            q.push([n[0]-1,n[1]]);
        }
        if ( n[0]<maps.length-1 && chk[n[0]+1][n[1]] == 0 && maps[n[0]+1][n[1]] != 'X'){
            dist[n[0]+1][n[1]] = Math.min(dist[n[0]][n[1]] + 1)
            chk[n[0]+1][n[1]] = 1;
            q.push([n[0]+1,n[1]]);
        }
        if ( n[1]>0 && chk[n[0]][n[1]-1] == 0 && maps[n[0]][n[1]-1] != 'X'){
            dist[n[0]][n[1]-1] = Math.min(dist[n[0]][n[1]] + 1)
            chk[n[0]][n[1]-1] = 1;
            q.push([n[0],n[1]-1]);
        }
        if ( n[1]<maps[0].length-1 && chk[n[0]][n[1]+1] == 0 && maps[n[0]][n[1]+1] != 'X'){
            dist[n[0]][n[1]+1] = Math.min(dist[n[0]][n[1]] + 1)
            chk[n[0]][n[1]+1] = 1;
            q.push([n[0],n[1]+1]);
        }
    }
    return dist[tr][tc]
}
 cs

 

 

문제 링크

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

반응형

'알고리즘 > 프로그래머스' 카테고리의 다른 글

[프로그래머스] 바탕화면 정리 JS  (0) 2023.03.05
[프로그래머스] 카드 뭉치 JS  (0) 2023.03.01
[프로그래머스] 대충 만든 자판 JS  (0) 2023.03.01
[프로그래머스] 보석 쇼핑 Python  (0) 2022.03.05
[프로그래머스] 후보키 Python  (0) 2022.03.01
반응형

문제 풀이

1. dfs를 이용하여 cards1의 첫번째 요소와 goal의 첫번째 요소가 같은 경우, cards2의 첫번째 요소와 goal의 첫번째 요소가 같은 경우에 대하여 탐색합니다.

2. cards1[2]의 첫번째 요소와 goal의 첫번째 요소가 같은 경우는 cards1[2]과 goal의 첫번째 요소를 제거한 후에 다시 dfs를 호출해줍니다.

3. goal의 모든 요소가 제거되는 경우에는 'Yes'를, cards1과 cards2의 첫번째 요소 중 어느것도 goal의 첫번째 요소와 같지 않은 경우에는 'No'를 반환합니다.

 

JS Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//https://school.programmers.co.kr/learn/courses/30/lessons/159994
 
function solution(cards1, cards2, goal) {
    return dfs(cards1, cards2, goal);
}
 
function dfs(cards1, cards2, goal){
    if ( goal.length == 0){
        return 'Yes'
    }
    if ( cards1[0] == goal[0]){
        return dfs(cards1.slice(1), cards2, goal.slice(1));
    }
    if ( cards2[0] == goal[0]){
        return dfs(cards1, cards2.slice(1), goal.slice(1));
    }
    return 'No'
};
 cs

 

문제 링크

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

반응형

'알고리즘 > 프로그래머스' 카테고리의 다른 글

[프로그래머스] 바탕화면 정리 JS  (0) 2023.03.05
[프로그래머스] 미로 탈출 JS  (1) 2023.03.05
[프로그래머스] 대충 만든 자판 JS  (0) 2023.03.01
[프로그래머스] 보석 쇼핑 Python  (0) 2022.03.05
[프로그래머스] 후보키 Python  (0) 2022.03.01
반응형

문제 풀이

1. key는 keymap의 알파벳, value는 해당 알파벳의 인덱스의 최솟값으로 갖는 딕셔너리를 만듭니다.

2. targets의 target 별로 각 알파벳의 위의 딕셔너리의 value 값의 합을 answer에 넣습니다. 알파벳 중 하나라도 keymap에 없으면 -1을 answer에 넣습니다.

 

JS Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
function solution(keymap, targets) {
    let answer = [];
    
    // 알파벳 : 입력을 위한 최소 입력
    let dictObj = {};
    
    // 특정 알파벳을 입력하기 위한 키보드 최소 입력값
    keymap.forEach(keys => {
        keys.split('').map(function(k,i){
            if ( k in dictObj ){
                dictObj[k] = Math.min(dictObj[k], i+1);
            } else {
                dictObj[k]=i+1;
            }
        })
    })
    
    targets.forEach(target => {
        answer.push(count(dictObj,target));
    })
    
    return answer;
}
 
// 문자열 target을 작성하기 위해 필요한 키보드 입력 횟수 반환
function count(keymap, target){
    let answer = 0;
    for (t of target.split('')){
        if ( t in keymap ){
            answer += keymap[t];
        } else {
            return -1;
        }
    }
    return answer;
}
 cs

 

문제 링크

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

반응형

'알고리즘 > 프로그래머스' 카테고리의 다른 글

[프로그래머스] 미로 탈출 JS  (1) 2023.03.05
[프로그래머스] 카드 뭉치 JS  (0) 2023.03.01
[프로그래머스] 보석 쇼핑 Python  (0) 2022.03.05
[프로그래머스] 후보키 Python  (0) 2022.03.01
[프로그래머스] 신고 결과 받기 Python  (0) 2022.01.28
반응형

문제풀이

1. n을 3진수로 변환한다.

2. 1의 결과를 뒤집는다.

3. 2의 결과를 다시 10진수로 변환한다.

 

n=10을 예로 들면, 10을 3진수로 변환한 1의 결과는 101이다. 이를 뒤집은 2의 결과는 101이다. 이를 다시 10진수로 변환한 3의 결과는 1*3^2 + 0*3^1 + 1* 3^0 = 10 이다. (예시의 n과 최종 답이 같은 것은 우연이다.)

 

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def solution(n):
    return r_convert(convert(n,3)[::-1],3)
 
# 10진수인 n을 base진수로 변환
def convert(n, base):
    T = "0123456789ABCDEF"
    q, r = divmod(n, base) # n을 base로 나눈 몫과 나머지를 튜플형태로 반환
    if q == 0:
        return T[r]
    else:
        return convert(q, base) + T[r]
 
# base진수인 n을 10진수로 변환
def r_convert(n, base):
    l = len(n)
    ans = 0
    for i, v in enumerate(n):
        ans += int(n[i])*pow(base,l-i-1)
        print(ans)
    return ans
 cs

Line 2 : str[::-1]을 통해 convert(v,3)의 결과를 뒤집어 준다.

 

문제 링크

 

코딩테스트 연습 - 3진법 뒤집기

자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요. 제한사항 n은 1 이상 100,000,000 이하인 자연수

programmers.co.kr

 

반응형

'알고리즘 > 프로그래머스' 카테고리의 다른 글

[프로그래머스 ] 예산 Python  (0) 2021.04.29
[프로그래머스] 신규 아이디 추천 - Python  (0) 2021.04.03
프로그래머스 불량 사용자  (0) 2020.12.03
프로그래머스 캐시  (0) 2020.12.01
프로그래머스 튜플  (0) 2020.11.30
반응형

2019 카카오 개발자 겨울 인턴십 문제입니다.

문제풀이

1. 정규표현식에서 '.'은 모든 문자 1개를 의미합니다. 따라서 banned_id의 모든 '*'을 '.'으로 바꾼 후 이를 컴파일러로 사용합니다.

2. user_id의 아이디 하나 u가 banned_id의 하나 b에 해당되기 위해서는 b로 만든 컴파일러에 u가 걸리고, b와 u의 길이가 같아야합니다. 저는 정규표현식의 match를 활용하였는데, match를 활용하면 'a.b'로 만든 컴파일러에 'aabb' 또한 매칭되므로 두번째 조건이 필요합니다.

3. 2 과정을 통해 모든 b에 해당하는 u의 리스트를 만듭니다.

user_id banned_id
["frodo", "fradi", "crodo", "abc123", "frodoc"] ["fr*d*", "abc1**"]

이 예를 사용하면 3의 결과는 다음과 같습니다.

{0: ['frodo', 'fradi'], 1: ['abc123']}

여기서 key값인 숫자는 b의 index입니다.

4. 3의 결과인 dictionary를 dfs 하여 최종 결과를 만들어냅니다.

 

*말로는 설명이 잘 안되어 아래 코드에서 자세히 다시 설명하겠습니다.

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import re
 
def solution(user_id, banned_id):
    # 가능한 제재id
    global answer
    answer = []
    # key : banned_id의 id의 index, value : 아래의 checked
    candidate = {}
    for i, b in enumerate(banned_id):
        # re.sub를 활용하여 b의 모든 *을 .으로 변환
        checker = re.compile(re.sub('\*','.',b))
        # banned_id 중 하나인 b에 매칭되는 user_id
        checked = []
        for u in user_id:
            # match가 안되면 결과가 None으로 두번째 조건 만족x
            if len(u) == len(b) and checker.match(u):
                checked.append(u)
        candidate[i] = checked
    # candidate를 활용하여 dfs
    for x in candidate[0]:
        dfs([x],candidate,len(banned_id))
 
    return len(answer)
 
'''
selected는 list로 selected[i]는 candidate[i]의 원소 중 하나. 즉 i번째 banned_id에 매칭되는 user_id 중 하나.
n은 banned_id의 길이.
dfs의 탈출 조건은 selected에 들어있는 원소의 수가 n이 되는 것이다.
'''
def dfs(selected,candidate, n):
    # 탈출조건
    if len(selected) == n:
        global answer
        # 중복을 제거하기 위해 selected를 정렬한 후 비교
        tmp = sorted(selected)
        if tmp not in answer:
            answer.append(tmp)
        return ;
    '''
    <selected의 원소 수가 n이 아닌 경우.>
    selected의 원소 수는 다음 banned_id의 index를 의미한다.
    ex) selected에 한개가 들어있으면 banned_id[1](banned_id의 두번째 요소)에 매칭되는 user_id의 집합인 
        candidate[1]의 원소 중 하나를 selected에 넣는다.
    '''
    for x in candidate[len(selected)]:
        if x not in selected:
            dfs(selected+[x],candidate,n)
 
 cs

문제링크

 

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

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

programmers.co.kr

 

반응형

'알고리즘 > 프로그래머스' 카테고리의 다른 글

[프로그래머스] 신규 아이디 추천 - Python  (0) 2021.04.03
[프로그래머스] 3진법 뒤집기 - Python  (0) 2021.02.08
프로그래머스 캐시  (0) 2020.12.01
프로그래머스 튜플  (0) 2020.11.30
프로그래머스 n진수 게임  (0) 2020.11.10
반응형

2018 카카오 블라인드 채용 문제입니다.

문제풀이

먼저, LRU 알고리즘 : 새로운 페이지가 등장했을 때, 가장 오래전에 사용된 페이지를 캐시에서 삭제합니다.

즉, 캐시 사이즈가 2이고, 캐시에 t=1일 때 A, t=2일 때 B가 들어오면, A와 B는 캐시가 비어있으므로 그냥 캐시에 추가합니다. t=3 일 때 C가 등장한다면, 가장 오래전에 사용된 A를 캐시에서 제거하고 C를 캐시에 추가합니다.

=> 큐 자료구조를 활용합니다.

1. cities에서 city를 꺼내고 대소문자를 구분하지 않는다고 했으므로 전부 대문자로 변환합니다.

2. queue 자료구조로 cache를 선언합니다. cache의 앞에 있을수록 사용한지 오래된 페이지입니다.

위의 예에서 cache는 [A] -> [A, B] -> [B, C]로 변화합니다.

3-1. city가 cache에 있다면 cache에서 city를 삭제하고 city를 다시 넣어줍니다. answer에는 1을 더해줍니다.

* pop()으로 꺼내지 않고 remove(cache)로 지워야합니다. 여기서 city를 지우는 이유는 city를 가장 최근에 사용된 것으로 바꾸기 위해 cache의 맨 끝에 넣기 위함인데, pop()으로 지우면 cache에서 city가 아니라 가장 오래된 것이 지워집니다.

** cache가 [A, B, C] 일 때, B가 들어오면, cache를 [A, C, B]로 바꾸기 위해 B를 지운 후 다시 넣는 것을 말합니다.

3-2. city가 cache에 없다면 cache의 첫번째 요소를 제거(pop())한 후, city를 cache에 넣어줍니다. answer에는 5를 더해줍니다.

*cache의 크기가 cacheSize보다 작을 때는 첫번째 요소를 제거하지 않고 city를 cache에 넣어주는 작업만 수행합니다.

Python Code 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from collections import deque
 
def solution(cacheSize, cities):
    if cacheSize == 0 : return len(cities) * 5
    answer = 5
    cache = deque([cities[0].upper()])
    for city in cities[1:]:
        c = city.upper()
        if c in cache:
            answer +=1
            cache.remove(c)
            cache.append(c)
        else:
            answer += 5
            cache.append(c)
            if len(cache) > cacheSize:
                cache.popleft()
    
    return answer
 cs

Line 4 : cacheSize가 0인 경우에는 cities의 요소 수에 5를 곱해 반환합니다.

Line 6 : cache에 cities의 첫번째 요소를 넣은 채 선언합니다. 따라서 answer 역시 5로 초기화합니다.

Line 9 : city가 cache에 있는 경우입니다.

Line 13 : city가 cache에 없는 경우입니다.

 

문제 링크

 

코딩테스트 연습 - [1차] 캐시

3 [Jeju, Pangyo, Seoul, NewYork, LA, Jeju, Pangyo, Seoul, NewYork, LA] 50 3 [Jeju, Pangyo, Seoul, Jeju, Pangyo, Seoul, Jeju, Pangyo, Seoul] 21 2 [Jeju, Pangyo, Seoul, NewYork, LA, SanFrancisco, Seoul, Rome, Paris, Jeju, NewYork, Rome] 60 5 [Jeju, Pangyo, S

programmers.co.kr

 

반응형

'알고리즘 > 프로그래머스' 카테고리의 다른 글

[프로그래머스] 3진법 뒤집기 - Python  (0) 2021.02.08
프로그래머스 불량 사용자  (0) 2020.12.03
프로그래머스 튜플  (0) 2020.11.30
프로그래머스 n진수 게임  (0) 2020.11.10
프로그래머스 SQL 동명 동물 수 찾기  (0) 2020.11.09
반응형

2019 카카오 개발자 겨울 인턴십 문제입니다.

문제풀이

1. 문제가 잘 이해가 안되는데, 예로 [2,1,3,4]를 설명하면 다음과 같다.

[2,1,3,4]는 {{2},{2,1},{2,1,3},{2,1,3,4}}로 쓸 수 있는데, 이 집합의 순서를 아래와 같이

{{2,1},{2,1,3},{2},{2,1,3,4}} 등으로 바꿀 경우, 이 집합을 통해 [2,1,3,4]를 맞추는 문제이다.

2. 집합의 각 요소를 살펴보면, 2가 4번, 1이 3번, 3이 2번, 4가 1번 등장하는 것을 볼 수 있다.

즉, 많이 순서대로 앞에 위치하는 요소가 된다.

Python Code

1
2
3
4
5
6
7
8
9
10
11
def solution(s):
    s = s[2:-2]
    co = {}
    for tuple in s.split('},{') :
        for t in tuple.split(','):
            tmp = int(t)
            if tmp in co:
                co[tmp] = co[tmp] + 1
            else:
                co[tmp] = 1
    return sorted(list(co.keys()), key = lambda x : co[x], reverse = True)
 cs

Line 4 : 각 집합을 꺼냅니다.

Line 5 : 각 집합의 요소를 꺼내 int로 변환해줍니다(Line 6).

Line 3, 7 - 10 : co는 각 요소가 key, 등장하는 횟수가 value인 딕셔너리 자료구조입니다.

Line 11 : co의 key들을 등장 횟수를 기준으로 정렬하여 리스트로 반환합니다.

 

문제링크

 

코딩테스트 연습 - 튜플

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

programmers.co.kr

 

반응형

'알고리즘 > 프로그래머스' 카테고리의 다른 글

프로그래머스 불량 사용자  (0) 2020.12.03
프로그래머스 캐시  (0) 2020.12.01
프로그래머스 n진수 게임  (0) 2020.11.10
프로그래머스 SQL 동명 동물 수 찾기  (0) 2020.11.09
프로그래머스 SQL 우유와 요거트가 담긴 장바구니  (0) 2020.11.09

+ Recent posts

티스토리툴바