[AI class day 5] 프로그래머스 코딩 테스트 문제 풀기 TIL

*lv 1부터 lv 4까지의 프로그래머스 문제들을 푸는 시간.

일단 lv1과 lv2를 최대한 풀어보는 것을 목표로 시작

 

 

lv1_완주하지 못한 선수

속도가 문제다.

해시형 자료 구조가 유리하다.

리스트를 딕셔너리로 바꿔서 해결

lv1_좌석 구매

마찬가지

키값이 중요하지는 않아서 set으로 바꿔서 해결

lv1_대중소 괄호 짝 맞추기

괄호 문제는 가장 마지막에 열린 괄호부터 닫아야 하기 때문에 LIFO 스택을 활용한다.

스택은 리스트를 활용하여 구현한다.

 

* 참고 

딕셔너리는 key, value 쌍인데 key를 가지고 value를 찾는게, value를 가지고 key를 찾는 것 보다 훨씬 간결하다.

찾고 싶은 것을 value에 넣자.

lv1_세 소수의 합

문제 지문에 아예 에라토스테네스의 체를 활용해서 풀라고 제시되어 있다. (이걸 가르쳐 줘서 레벨 1인가)

문제를 잘 읽는 것이 중요한 게 

처음에는 n이 주어지고 세 소수의 합이라고 해서

세 소수의 합의 경우의 수를 return 하는 건 줄 알았는데,

자꾸 틀려서 다시 꼼꼼히 읽어보니

세 소수의 합이 n과 같은 경우의 수를 return해야 했다.

lv2_올바른 괄호

괄호 맞추기 문제는 역시 스택으로 푼다.

이 문제는 오직 () 괄호만 쓰기 때문에, lv1_ 대중소 괄호 짝 맞추기 보다 더 쉬운 것 같은데, lv_2로 표시되어있다.

아마도 옛날에 만들어서 레벨 표기가 잘못되어 있는 거 아닐까?

 

참고로 마지막 리턴문을 나는 이렇게 썼는데

    return True if len(stack) == 0 else False

 

다른 사람의 풀이를 보니

    return len(st) == 0

이렇게만 써도 충분하다.

쓸 때 없이 중언부언하지 말고 간결하게 쓰는 훈련도 필요할 것 같다.

lv2_스킬트리

문제 이름이 트리.

트리라고 힌트를 주고 있다. 

방향이 있는 경로니까 DFS?

모든 정점을 다 거치지 않아도 된다.

단 제일 첫 루트 노드부터 순서를 거쳐야 한다.

 

필수 스킬과 스킬 트리가 있는데

스킬 리스트에 없는 스킬 트리내의 아이템은 무시하면 된다.

 

*참고

python

for-else 문

for문이 break로 끊기지 않고 끝까지 수행되면 실행되는 코드

def is_in(str, lst):
    for i in str:
        if i not in lst:
            print("fail")
            break
    else:
        print("success")

str = "LOVE"
lst = ["L","O","V", "E" ]
is_in(str, lst)

>>success

str = "LOVE!"
is_in(str, lst)

>>fail

lv2_최대 용량이 정해진 FIFO 큐 클래스

 

stack (LIFO) 2개를 활용해서 queue(FIFO)를 구현하는 원리를 코드로 작성하는 것이 핵심

lv2_더 맵게

최소값과 그 다음 값을 꺼내야 하고,

새 값을 집어넣으면 다시 정렬을 해서 최소값을 찾아야 하므로

--> 최소 힙으로 푸는 문제

 

파이썬의 힙 큐 모듈을 사용하자

lv2_배상 비용 최소화

제곱의 합이 가장 작은 경우를 찾는 문제

제곱의 합이 가장 작은 경우 '최소자승합' 이라고 부른다.

'최소자승합'은 각 수 사이의 편차가 가장 적을 때 나온다.

즉, 리스트에서 제일 값이 큰 item에서 계속 1씩 빼준 다음, item의 제곱의 합을 구하면 최소자승합이 나온다.

 

--> 제일 큰 값을 꺼내고, 처리한 새 값을 넣은 다음 매번 정렬해야 하므로 최대 힙으로 해결

--> 그냥 for 안에서 sorted() 해도 효율성 테스트 통과한다 (파이썬의 sorted()는 팀소트 알고리즘을 사용해서 그렇다고 한다)

lv2_짝지어 제거하기

알파벳 짝을 제거하라고 했지만, 결국 연속해서 같은 문자가 나오면 지워지는 과제 --> 괄호 문제와 같다

--> 스택으로 해결

lv2_사전순 부분문자열

숫자와 알파벳의 차이만 있지, 알파벳 오더를 key값으로 바꿔 생각해보면, 3일차에 풀었던 '큰 수 만들기'와 같은 원리의 문제다.

문제 설명에 여러 가지 경우의 수를 제시해 주는 것에 현혹되어 순열로 풀려고 하면 안된다.

효율성 테스트에서 실패한다.

.append 로 제일 큰 값를 만들어 나가는 식으로 풀어야 한다. 

뒤에 오는 문자보다 앞에 오는 문자의 키값이 더 작으면 pop해주면서 풀어나가는 문제.

제일 마지막에 들어갔던 값을 다시 pop해주니까 일종의 스택 구조인 것 같다.

'큰 수 만들기' 문제보다 횟수 제약이 없으니까 더 쉽게 해결이 가능하다.

lv2_주사위 게임

금방 풀 수 있을 줄 알았는데, 의외로 한참 헤맸다.

식은 금방 세웠는데, 계속 결과와 다른 값이 나왔기 때문.

주사위 3개를 돌렸을 때, 3개의 값을 더한 만큼 말이 움직이는 규칙이었는데, 나는 순서가 없다고 생각하고 답을 구했는데,

결국 순서가 있다고 계산해야 맞다고 나왔다.

즉, 주사위 1,2,3의 값이

(1, 1, 2) 라고 나오는 것과

(2, 1, 1) 이라고 나오는 것을 따로 count 해야지만 맞다는 것.

이렇게 주사위를 던지는 건 (1, 1, 1)처럼 중복된 값이 나오고, 순서가 있기 때문에 중복 순열 product()로 풀 수 있다.

lv2_문자열 압축

내게 어려움

모든 길이 단위로 다 조각내서 살펴보는 완전 탐색

겹치는 만큼 압축하는 과정이 들어가야 함

일단 패스

 

lv3_배달

내게 어려움

다익스트라 알고리즘으로 풀어야 한단다.

다익스트라 알고리즘은 그래프 알고리즘 중 하나로 최단 경로를 구하는 알고리즘 입니다.

 https://m.blog.naver.com/kks227/220796029558 

그래프 문제

우선순위 큐로 해결

 

lv3_FloodFill

내게 어려움

BFS 문제

데크

 

lv3_방문 길이

아직  못 봄

lv3_게임아이템

아직  못 봄

lv3_야근 지수

lv2_ 배상 비용 최소화와 완전히 동일한 문제이다.

그런데 이건 lv_3로 표시되어있다.

아마도 옛날에 만들어서 레벨 표기가 잘못되어 있는 거 아닐까?

 

lv3_빙고

빙고를 만들 수 있는 조건은 크게 3개로 나눌수 있다.

1) 가로 줄의 원소가 모두 불려질 경우

2) 세로 줄이 원소가 모두 불려질 경우

3) 대각선 줄 원소들이 지워질 경우

 

1)와 2)는 n개 만큼의 case가 있지만,

3)은 딱 2개가 있다.

 

불려진 숫자는 다 0개로 바꾸고,

즉 판정해야 하는 line은 2*n + 2에서 0의 갯수를 세서 0이 n개이면 빙고인 줄이고 count를 +1 한다. 

lv3_N-Queen

내게 어려움

구글 검색해보니 자주 등장하는 유형의 문제인 것 같다.

 

lv3_N으로 표현

내게 어려움

4일차 강의에서 문제 풀이 동영상 으로 다룬 적이 있는 문제다.

그럼에도 불구하고 다시 풀어보려고 하니 끝까지 못 풀겠다.

다이내믹 프로그래밍으로 문제 해결하는 방법을 완전히 이해하지 못한 것 같다.

 

lv3_2 x n 타일링

n= 1 result=1

n=2 result=2

n=3일 때는
처음에 가로길이 1로 놓으면 나머지는 n=2 일 때 경우의 수
처음에 가로길이 2로 넣으면 나머지는 n=1 일 때 경우의 수 이므로
f(1)+f(2)

n=4일 때는
처음에 가로길이 1로 놓으면 나머지는 n=3 일 때 경우의 수
처음에 가로길이 2로 넣으면 나머지는 n=2 일 때 경우의 수 이므로
f(3)+f(2)

...

피보나치수와 마찬가지임을 알 수 있다.

 

그런데 재귀 함수로 결과를 짜면 효율성 테스트를 통과 못하는 문제가 발생한다.

lv3_등굣길

내게 어려움

어려워서 다른 사람들의 풀이를 건색했는데 DP로 해결해야 한다고 함

lv3_가장 긴 팰린드롬

팰린드롬은 뒤집어도 똑같은 값이 나오는 문자열이다.

s = s[::-1]

이렇게 정의할 수 있다.

 

자주 출제되는 문제유형인가보다. 지금 보고 있는 <파이썬 알고리즘 인터뷰> 에 거의 똑같은 문제가 나온다.

책에 나오는 팰린드롬 문제 풀이를 참고로 해서 해결했다.

 

two pointer를 이용해 문제를 해결하는데, 

제일 작은 팰린드롬 길이인 2개(짝수 개일 경우)와 3개(홀수 개일 경우)짜리 슬라이스를 만들고, 이를 이동시켜 팰린드롬 조각을 찾으면, 2개의 포인터를 이동시켜 더 긴 팰린드롬이 성립하는지 확인한다.

lv3_자물쇠와 열쇠 

내게 어려움

ㅁ

lv3_기둥과 보 설치

아직  못 봄

ㅁ

lv3_블록 이동하기

아직  못 봄

ㅁ

lv4_버스 여행

아직  못 봄