프로그래머스

프로그래머스 고득점 Kit 의 해시, 완전탐색, 정렬 문제와 Level 1 문제, 모의 테스트 두 문제다. 2021년 11월에 Python 으로 풀고, 2022년 3월에 Level 1 을 더 풀었다. 가장 큰 수와 타겟 넘버는 JavaScript 로도 다시 썼다. 소수 찾기의 첫 풀이는 소수 판별 조건이 틀려 있어서 해설을 보고 다시 썼고, 그 다시 쓴 쪽도 check(int(i)) 에 순열이 아니라 길이를 넘기는 실수가 남아 있다.

해시: 완주하지 못한 선수

# 1. collections Counter객체 풀이
# 1) 원소:빈도의 딕셔너리형태, multiset이라고도 부름
# 2) Counter객체로 뺄셈이 가능하다

import collections as col

def solution(p, c):
    answer = col.Counter(p) - col.Counter(c)
    return list(answer.keys())[0]


# 2. zip 풀이
# 1) 인데스별로 묶이며, 가장 짧은 리스트를 기준으로 맞춰진다.
def solution(p,c):
    p.sort()
    c.sort()
    for p,c in zip(p,c):
        if p!=c:
            return p
    return p[-1]

# 3. hash 풀이
def solution(p,c):
    temp = 0
    dic={}
    for p in p:
        dic[hash(p)] = p
        temp += int(hash(p))
    for c in c:
        temp -= hash(c)
    answer =dic[temp]

    return answer

해시: 전화번호 목록

# 1. 문제를 100% 이해하지 못했다.
# 2. 출제자의 의도, 풀이의 핵심을 이해해보도록 하자
'''
'접두어'에 FOCUS!
'''

# 1. startswith() 풀이 방법
def solution(phoneBook):
    phoneBook = sorted(phoneBook)
    # 새로 안 사실
    # 접두어별로 있는지 확인 = 문자열 기준 앞의 인덱스 부터 확인
    for p1, p2 in zip(phoneBook,phoneBook[1:]):
        if p2.startswith(p1):
            return False
    return True

# 2. hash 풀이 방법
def solution(phoneBook):
    dic={}

    for phone in phoneBook:
        dic[phone] = 1

    for phone in phoneBook:
        temp =""
        for number in phone:
            temp +=number
            # 각 자리를 붙은 게 dic안에 있으면 and 자기 자신은 제외(어차피 중복 안되니까)
            if temp in dic and temp != phone:
                return False
    return True

해시: 위장

# 곱집합 연산
# (A+1) x (B+1) - 1 로 계산했다. 1 을 빼주는 이유는
# (A+1) x (B+1) 의 경우에는 비어있는 경우도 포함되기 때문이다.

def solution(clothes):
    dic={}
    for item in clothes:
        if item[1] not in dic:
            dic[item[1]] = 1
        else:
            dic[item[1]] +=1

    cases = 1

    for item in dic.values():
        cases *= item+1

    return cases-1

해시: 베스트앨범

def solution(genres, plays):

    answer = []
    dic = {}
    li = []

    # genres와 plays 합치기
    for music in zip(genres,plays):
        li.append(music)

    # 딕셔너리에 넣기
    for idx,music in enumerate(li):
        if music[0] not in dic:
            dic[music[0]] =[]
        dic[music[0]].append([idx,music[1]])
    print(dic)

    # 장르내에서 정렬하기
    new_dic={}
    for genre in dic.items():
        music_list = sorted(genre[1],key=lambda x:x[1],reverse=True)
        new_dic[genre[0]] = music_list
    print(new_dic)

    print("-------------------")
    # 장르별 플레이 수 합치기
    plays_sum={}
    for genre, plays in dic.items():
        sum_play = 0
        for play in plays:
            sum_play += play[1]
        plays_sum[genre] = sum_play

    # 많이 플레이 된 장르문 정렬
    plays_list = sorted(plays_sum.items(),key=lambda x:x[1],reverse=True)

    # 많이 플레이 된 장르문에서 노래 찾기
    for genre in plays_list:
        print(new_dic)
        for i in range(2):
            answer.append(new_dic[genre[0]][i][0])

        # 만약 중복이 나오면 sort후 낮은 번호대로, idx리턴하기

    return answer


def solution(genres, plays):
    answer = []

    dic1 = {}
    dic2 = {}

    for i, (g, p) in enumerate(zip(genres, plays)):
        if g not in dic1:
            dic1[g] = [(i, p)]
        else:
            dic1[g].append((i, p))

        if g not in dic2:
            dic2[g] = p
        else:
            dic2[g] += p

    for (k, v) in sorted(dic2.items(), key=lambda x:x[1], reverse=True):
        for (i, p) in sorted(dic1[k], key=lambda x:x[1], reverse=True)[:2]:
            answer.append(i)

    return answer

완전탐색: 모의고사

처음 풀이

def solution(answers):
    # 문제 개수
    num = len(answers)

    # 찍는 패턴
    # 문제 수 만큼 리스트 추가하기
    no1 = [1,2,3,4,5] * (num // 5 + 5)
    no2 = [2,1,2,3,2,4,2,5] * (num // 8 + 8)
    no3 = [3,3,1,1,2,2,4,4,5,5] * (num // 10 + 10)
    count1 = 0
    count2 = 0
    count3 = 0

    # answers순서대로 답이 맞는지 카운트 하기
    for i in range(num):
        if answers[i] == no1[i]:
            count1 +=1
        if answers[i] == no2[i]:
            count2 +=1
        if answers[i] == no3[i]:
            count3 +=1

    # max 카운트 출력하기
    max_val = max(count1,count2,count3)

    # 가장 큰 수의 수포자 찾기
    answer = []
    if count1 == max_val:
        answer.append(1)
    if count2 == max_val:
        answer.append(2)
    if count3 == max_val:
        answer.append(3)

    return answer

다시 풀기. 인덱스를 패턴 길이로 나눈 나머지로 돈다

def solution(answers):
    answer = []

    # 패턴 입력
    no1 = [1,2,3,4,5]
    no2 = [2,1,2,3,2,4,2,5]
    no3 = [3,3,1,1,2,2,4,4,5,5]
    count = [0,0,0]
    # 인덱스가 없어서 list index out of range뜸

    # i%배열의크기를 이용한 인덱스 주기 활용
    for idx,val in enumerate(answers):
        if answers[idx] == no1[idx%len(no1)]:
            count[0] +=1
        if answers[idx] == no2[idx%len(no2)]:
            count[1] +=1
        if answers[idx] == no3[idx%len(no3)]:
            count[2] +=1

    # max값을 활용하여 answer에 답 추가
    max_val = max(count)
    answer =[]
    for i in range(1,4):
        if count[i-1] == max_val:
            answer.append(i)

    return answer

완전탐색: 소수 찾기

처음 풀이

from itertools import permutations
import math

def solution(numbers):
    # numbers로 받은 숫자 리스트에 각각 저장하기
    li = list(numbers)
    num = len(li)
    poss =[]
    answer = 0

    # 조합 가능한 숫자 리스트에 저장하기
    for i in range(1,num+1):
        d = list(permutations(li,i))
        for j in range(len(d)):
            if d[j][0] != '0':
                poss.append(''.join(d[j]))

    # 중복되는 숫자 없애기
    set_poss = set(poss)

    # 소수 찾기
    for item in set_poss:
        count = 0
        for dividor in range(2, int(math.sqrt(int(item)))+1):
            # 소수가 아니라면 반복문 바로 끝내기
            if int(item) ==1 and int(item) % dividor == 0:
                count =1
                break
        if count ==0:
            answer +=1

    # 시간탐색: 문자열 길이가 최대 7이라면, 가능한 예비 문자열은
    # 1) 7 + 7*6 + 7*6*5 + 7*6*5*4 + ... + 7*6*5*4*3*2*1
    # 7 + 42 + 200 + 800 + 2400 + 5040  -> 대략 1만 이하
    # 2) 소수확인하는 방법: 2부터 그숫자-1까지 %값이 0이면 break
    # 9,999,999 소수 확인 하려면 엄청난데?
    # 100부터 51이상은 보지 않아도 되는 것 처럼, 쓸데없는 연산은 빼면 됌
    # /2 말고 좀 더 획기적으로 줄 일 수 있는 방법 없나?
    # 제곱근 범위까지 볼까, 천만이면, 제곰근이 3천대된다.

    return answer

print(solution("17"))

해설 참고

from itertools import permutations
import math

def check(n):
    # 0과 1은 무시
    if n < 2:
        return False
    for i in range(2,int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True

def solution(numbers):
    answer = []
    for i in range(1,len(numbers)+1): #len(문자열) 해도 체크가 된다.

        # 조합 가능한 숫자 리스트에 저장하기
        d = list(map(''.join, permutations(list(numbers),i))) # 숫자 합치기
        for j in list(set(d)) : # 중복 제거한 숫자
            if check(int(i)): # 소수인지 확인
                answer.append(int(i))
    answer =len(set(answer)) # 7, 7인 경우 77,77은 두 번 나오기 때문에
    return answer

print(solution("17"))

완전탐색: 카펫

def solution(brown, yellow):
    # w>= h
    # brown = 2w + 2h - 4
    # yellow = w*h-brown
    # w*h = brown+yellow
    # w+h = brown/2 + 2

    for w in range(3,brown//2-2+1):
        for h in range(3,w+1):
            if w*h == brown+yellow and w+h ==brown//2 + 2 :
                return w,h
    return []

정렬: K번째수

def solution(array, commands):
    answer = []
    for i in range(len(commands)):
        li = sorted(array[commands[i][0]-1:commands[i][1]])
        answer.append(li[commands[i][2]-1])
    return answer

'''
    새로 알게 된 사실
        1. list[i][i] = []
        2. 문제에서 흔히 I번째에서 J번째까지라고 함은 list[i-1][j]이다
        3. k번째 수는 인덱스로 k-1이다
'''

정렬: 가장 큰 수

Python

def solution(numbers):
    numbers = list(map(str,numbers))
    numbers.sort(key=lambda x:x*3, reverse=True)
    return str(int(''.join(numbers)))

'''
from itertools import permutations
def solution(numbers):
    li = sorted(map(''.join,list(permutations(list(map(str,numbers)),len(numbers)))),reverse=True)
    answer = li[0]
    return answer
'''
# 시간 복잡도를 생각 못했다.
# 배열의 개수가 100000까지 되니깐, O(100000!)은 당연히 TImeOut이다

'''
변환된 num을 sort()를 사용하여 key 조건에 맞게 정렬한다.
lambda x : x*3은 num 인자 각각의 문자열을 3번 반복한다는 뜻이다.
x*3을 하는 이유? -> num의 인수값이 1000 이하이므로 3자리수로 맞춘 뒤, 비교하겠다는 뜻.
예시가 잘못되서 햇갈렸다.
6,2,10을 비교하는 게 아니라

121 12를 비교할 때
[121,12] 121 21 > 12 112 이므로

121: 121121
12:  121212 12가 더 큰 수 이는 1000이하의 숫자인 것을 감안해봤을 때 단순히 문자열을 반복해줌으로써 값 비교 가능해짐
'''

JavaScript

function solution(numbers) {
  const result = numbers
    .map((number) => String(number))
    .sort((a, b) => b + a - (a + b)) // 💛
    .join('');
  return result[0] === '0' ? '0' : result;
}

console.log(solution([6, 2, 10]));

// sort((a,b) => (b+a)-(a+b)) = 문자로 변환된 숫자를 연결하여 비교정렬
// ( '3', '30' => ('303')-('330'))

정렬: H-Index

def solution(citations):
    citations.sort(reverse=True)
    for idx , citation in enumerate(citations):
        if idx >= citation:
            return idx
    return len(citations)

# h번 이상 인용된 논문이 h개 이상, 나머지 논문이 h개 이하
# 가장 많이 인용된 = h가 최대인 값 부터 차례대로 검색
# idx = 논문의 수, citation은 논문인용횟수
# 논문의 수가 논문인용횟수보다 크거나 같을 경우, 즉 문제에서 나머지 논문이 h개 이하일 때는 고려하지 않아도 된다.

DFS/BFS: 타겟 넘버

Python

answer = 0

def DFS(numbers, target, result):
    global answer
    if numbers ==[]:
        if target == result:
            answer +=1
        return

    DFS(numbers[1:], target, result+numbers[0])
    DFS(numbers[1:], target, result-numbers[0])

def solution(numbers, target):
    global answer
    DFS(numbers, target, 0)
    return answer

JavaScript

let answer = 0;

function DFS(arr, target, sum) {
  if (arr.length === 0) {
    // arr =[] ❌
    if (target === sum) {
      answer += 1;
    }
    return;
  }
  DFS(arr.slice(1), target, sum + arr[0]);
  DFS(arr.slice(1), target, sum - arr[0]);
}

function solution(numbers, target) {
  DFS(numbers, target, 0);
  return answer;
}

console.log(solution([1, 1, 1, 1, 1], 3));

Level 1: 문자열을 정수로 바꾸기

def solution1(s):
    li = list(map(int, s))
    if s[0] is '-':
        return ''.join(li) * -1
    else:
        return ''.join(li)

def solution2(s):
  return int(s[1:]) * -1 if s[0] == '-'  else int(s)

def solution3(s):
    return int(s)
# 형변환 시 부호는 알아서 바뀜

# 진수 변경 로직
def solution4(s):
    result = 0

    for idx, number in enumerate(str[::-1]):
        if number == '-':
            result *= -1
        else:
            result += int(number) * (10 ** idx) # 이부분

    return result

Level 1: 신고 결과 받기

내 방식

def solution(id_list, report, k):
    answer =[0 for _ in range(len(id_list))]

    # 유저별로 신고한 유저들이 저장된다.
    reported_name = {name:[] for name in id_list}
    # 유저별로 몇번 신고된지 저장된다.
    reported_count ={name:0 for name in id_list}

    # set함수를 이용해 동일 신고 무시
    for item in set(report):
        user, reported_user = item.split(" ")[0], item.split(" ")[1]
        reported_count[reported_user] += 1
        reported_name[reported_user].append(user)

    # key: 신고당한 유저, values: 신고한 유저
    for key, values in reported_name.items():
        if reported_count[key] >= k:
            for value in values:
                answer[id_list.index(value)] +=1
    return answer

참고 풀이

def solution(id_list, report, k):
    db = {name:[] for i, name in enumerate(id_list)}
    reports = {name:0 for i, name in enumerate(id_list)}

    for re in set(report):
        user = re.split(" ")[0]
        reported_user = re.split(" ")[1]
        db[user].append(reported_user)
        reports[reported_user] +=1

    answer = [0 for _ in range(len(id_list))]
    for key, values in db.items():
        for value in values:
            if reports[value] >=k:
                answer[id_list.index(key)] += 1
    return answer

Level 1: 나머지가 1이 되는 수 찾기

def solution(n):
    x = 1
    while(x):
        if(n%x==1):
            break
        x+=1
    return x

# 참고, 나머지가 1인 수는 약수-1 % ==0랑 같음

def solution(n):
    for i in range(2,n//2+1):
        if n % i == 1:
            return i
    return n-1

# for문 도중에 return을 하면 반복문 탈출이 아니라 그냥 리턴이 되네
# 범위: n끝까지 볼 게 아니라, 답이 반드시 있다고 했으니까 2로 나눴을 때까지만 보고 아니면 n-1하면 되겠네

모의 테스트: 나머지 한 점

def solution(v):
    x = [i[0] for i in v]
    y = [i[1] for i in v]

    for i in range(2):
        x[0] ^= x[i+1]
        y[0] ^= y[i+1]

    return [x[0],y[0]]

# ^ XOR연산은 다르면 1이다.
# 따라서 x[0]과 x[1], x[2]을 비교해서 x[0]과 다르면 x[0]에 대입하는 형식으로, 다른 좌표를 찾아낸다.
# ^ 비트연산을 통해 같은 값이 두개있으면 나머지 한 값이 나오네

## counter.collection을 이용한 방법
from collections import Counter

def solution(v):
  x = [i[0] for i in v]
  y = [i[1] for i in v]
  x_count = Counter(x)
  y_count = Counter(y)

  x_answer = [i for i in x_count if x_count[i] == 1]
  y_answer = [i for i in y_count if y_count[i] == 1]

  answer = x_answer+y_answer
  return answer

모의 테스트: 순열 확인

def solution(arr):
    arr.sort()
    for index in range(len(arr)):
        if arr[index] != (index+1) : return False
    return True


# 문제의 유니버스를 잘 살폈어야 했다.
# 이 문제는 무조건 소팅하면 1부터 끝까지 가는 유니버스안에 있었다. 이를 캐치했어야 했다.
# 짜잘하게 for문 문법과, 인덱스 문법, sort문법을 복습하는 계기가 됐다.