'알고리즘/프로그래머스' 카테고리의 글 목록

문제풀이

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;
}
Colored by Color Scripter

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]
}
Colored by Color Scripter

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'
};
Colored by Color Scripter

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;
}
Colored by Color Scripter

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. 딕셔너리 자료형 c을 활용하여 보석의 종류 수를 셉니다. c[보석 종류 x] = i~j까지 있는 보석 중 보석 종류 x의 수

2. gems의 맨 앞 인덱스 j부터 보석을 체크합니다. (i는 0부터 시작합니다.)

2-1. c의 모든 value가 1 이상이 되어야 모든 보석 종류를 최소한 하나씩 사게 됩니다.

2-2. 2-1의 조건을 만족하기 시작하면 c[i번째 보석의 종류] > 1인 경우에는 i를 하나 증가시켜 줍니다. ( i번째 보석을 빼도 모든 종류의 보석을 살 수 있습니다.)

* 문제에서는 0이 아닌 1부터 시작하므로 i와 j는 1씩 더해서 계산해야합니다.

for 문이 한번 돌아가므로 시간 복잡도는 O(n)이 됩니다.

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

def solution(gems):
    tmp = set(gems)
    # 각 보석이 몇 개 있는 지
    c = {}
    for t in tmp:
        c[t] = 0
    # 보석의 종류 수 
    check = 0
    # 보석의 전체 종류
    tot = len(tmp)
    i = 0
    answer = [0,len(gems)]
    for j, item in enumerate(gems):
        if c[item] == 0 : check += 1
        c[item] += 1
        while i < j and c[gems[i]] > 1 :
            c[gems[i]] -= 1
            i += 1
        if check == tot and j-i < answer[1] - answer[0]:
            answer = [i+1,j+1]
    
    return answer
Colored by Color Scripter

cs

Line 19 : 모든 보석을 포함하며 이전보다 구간 길이가 줄어든 경우 answer를 i와 j로 바꿔줍니다.

문제 링크

코딩테스트 연습 - 보석 쇼핑

["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7]

programmers.co.kr

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

[프로그래머스] 카드 뭉치 JS (0)	2023.03.01
[프로그래머스] 대충 만든 자판 JS (0)	2023.03.01
[프로그래머스] 후보키 Python (0)	2022.03.01
[프로그래머스] 신고 결과 받기 Python (0)	2022.01.28
[프로그래머스] 메뉴 리뉴얼 Python (0)	2021.09.26

문제풀이

1. 조합 함수(combination)을 활용하여 가능한 인덱스 조합을 만든다.

2. 각 행에서 1에서 뽑은 인덱스에 해당하는 값들만 추출하여 중복값이 없는지 찾는다. => 유일성

(set에 넣어서 요소의 수를 총 행의 수와 비교한다.)

3. 각 단계에서 추출된 익덱스 집합이 이전에 선택된 인덱스 집합의 부분집합이 되는 경우는 없는지 확인한다. => 최소성

(combination을 통해 추출한 조합의 인덱스 개수는 1부터 늘어남으로 이전에 선택된 인덱스 조합만 확인하면 된다.)

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

from itertools import combinations
 
def solution(relation):
    rows = len(relation)
    cols = len(relation[0])
    keys = []
    
    for n in range(1,cols+1):
        for idxs in combinations(range(cols),n):
            # 최소성 and 유일성
            if min_check(keys,idxs) and \
                    len(set(tuple(relation[row][idx] for idx in idxs) for row in range(rows))) == rows :
                keys.append(idxs)
    
    return len(keys)
 
#최소성
def min_check(keys, target):
    for k in keys:
        if set(k).issubset(set(target)):
            return False
    return True
Colored by Color Scripter

cs

문제 링크

코딩테스트 연습 - 후보키

[["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]] 2

programmers.co.kr

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

[프로그래머스] 대충 만든 자판 JS (0)	2023.03.01
[프로그래머스] 보석 쇼핑 Python (0)	2022.03.05
[프로그래머스] 신고 결과 받기 Python (0)	2022.01.28
[프로그래머스] 메뉴 리뉴얼 Python (0)	2021.09.26
[프로그래머스] 행렬 테두리 회전하기 Python (0)	2021.09.16

문제풀이

1. 각 id가 신고한 id를 저장한다.

a[id] = [신고한 id, ...]

2. 각 id가 신고당한 횟수를 저장한다.

c[id]=id가 신고당한 횟수

3. 각 id가 신고한 id a[id] 의 요소들 x 중 신고당한 횟수 c[x] 가 기준값 k를 넘는 요소 x의 수를 반환한다.

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#https://programmers.co.kr/learn/courses/30/lessons/92334?language=python3
def solution(id_list, report, k):
    # 신고 당한 횟수
    c = {}
    # 신고한 id
    a = {}
    
    for i in id_list:
        c[i] = 0
        a[i] = []
    
    for r in set(report):
        #x가 y를 신고
        x, y = r.split()
        c[y] += 1
        a[x].append(y)
        
    return [sum(1 if c[t] >= k else 0 for t in a[i]) for i in id_list]

cs

문제링크

코딩테스트 연습 - 신고 결과 받기

문제 설명 신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다. 각 유저는 한 번에 한 명의

programmers.co.kr

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

[프로그래머스] 보석 쇼핑 Python (0)	2022.03.05
[프로그래머스] 후보키 Python (0)	2022.03.01
[프로그래머스] 메뉴 리뉴얼 Python (0)	2021.09.26
[프로그래머스] 행렬 테두리 회전하기 Python (0)	2021.09.16
[프로그래머스] 위클리 챌린지 4주차 (0)	2021.08.25

문제풀이

1. orders의 각 요소들에 대하여 길이가 c인 요소들을 만듭니다.

2. 1의 결과물을 tmp라 하면, tmp의 각 요소의 등장 빈도수를 셉니다. (코드에서는 collections.Counter() 함수 사용)

3. 빈도수의 최대값이 2 이상인 경우, 빈도수가 최대값과 같은 요소들을 answer 리스트에 넣어줍니다.

4. 1-3의 과정을 모든 길이에 대하여 반복한 후, answer를 사전 순으로 정렬 후 반환합니다.

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# https://programmers.co.kr/learn/courses/30/lessons/72411
from itertools import combinations
from collections import Counter
 
def solution(orders, course):
    answer = []
    for c in course:
        tmp = []
        for order in orders:
            for x in combinations(order, c):
                tmp.append(''.join(sorted(x)))
        # 길이가 c인 조합의 등장 빈도 체크
        counter = Counter(tmp)
        if len(counter.values()):
            # 길이가 c인 조합 중 최대 등장 빈도
            m = max(counter.values())
            if m > 1:
                # 등장 빈도가 최대인 조합들을 answer에 넣는다
                answer += [k for k,v in counter.items() if v==m]
    
    return sorted(answer)
Colored by Color Scripter

cs

문제링크

코딩테스트 연습 - 메뉴 리뉴얼

레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서

programmers.co.kr

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

[프로그래머스] 후보키 Python (0)	2022.03.01
[프로그래머스] 신고 결과 받기 Python (0)	2022.01.28
[프로그래머스] 행렬 테두리 회전하기 Python (0)	2021.09.16
[프로그래머스] 위클리 챌린지 4주차 (0)	2021.08.25
[프로그래머스] 실패율 Python (0)	2021.08.22