Jin의 일상

programmers.co.kr/learn/courses/30/lessons/42860

풀이 전략

조이 스틱 문제는 두 단계의 알고리즘으로 구성된다.

1. 알파벳 올리기 2. 옆으로 이동

* 참고로 옆으로 이동하는 알고리즘으로 구현할 때,

왼쪽 방향으로만 이동하거나, 오른쪽 방향으로만 이동할 수 있는 것이 아니다.

- 이런 알고리즘으로 구현하면 11번 테스트 케이스에서 틀린다.

왼쪽으로 가다가 오른쪽으로 갈 수도 있다.

ABABAAAAAAABA를 예시로 들 수 있다.

- ABAABAB가 정답이다.

1. 알파벳 올리기

- 주어진 문자열을 아스키코드로 변환한다.

    JAN  -> [74, 65, 78]  

- 대문자 A의 아스키코드는 65이므로 각 문자열의 아스키 코드에 65씩 빼준다. 

  [74, 65, 78]  => [9, 0 , 18]

- 13보다 작으면, 해당 인덱스의 값만큼 CNT에 더해준다.

- 13보다 크다면, 해당 26에서 해당 인덱스의 값을 빼서 CNT에 더해준다.

*13이 기준이 된 이유

- A~Z를 아래와 같이 나열했을 때, 제일 가운데가 되는 숫자가 13이다.

[0, 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]

- 문제 조건에서 알파벳을 A,B,C 순서만이 아니고 A,Z,Y와 같이 역순으로도 셀 수 있다고 했다.

따라서 최소 CNT가 되기 위해 13을 기준으로 한다.

2. 옆으로 이동

반복문을 돌며, 각 자리에서 좌측 또는 오른쪽으로 갔을 때 최소의 움직임 횟수를 구한다.

- 0번 인덱스는 중앙에 위치한다.

- 파란색 동그라미를 시작으로 0번 인덱스의 왼쪽 방향에 위치한다.

- 0번 인덱스 오른쪽 방향에는 빨간색 동그라미까지의 인덱스 값이 위치된다.

- 0번 인덱스의 값을 기준으로, 왼쪽 끝까지 탐색하고 오른쪽 끝까지 위치했을 때 움직임 횟수를 구한다.

- 0번 인덱스의 값을 기준으로, 오른쪽 끝까지 탐색하고 왼쪽 끝까지 위치했을 때 움직임 횟수를 구한다.

- 왼쪽과 오른쪽 중 더 짧은 움직임으로 답을 갱신한다.  (비교될 움직임 횟수의 초기 값은 전체길이 - 1) 

코드

import sys


def solution(name):
    s = name
    r = list()
    
    # 알파벳 올리기/내리기
    for c in s:
        print(ord(c))
        r.append(ord(c) - 65)
    cnt = 0
    for i in r:
        if i <= 13:
            cnt += i
        else:
            cnt += (26 - i)
            
    # 옆으로 이동
    min_movement = len(r) - 1
    for red in range(len(r)):
        blue = red + 1
        while blue < len(r) and r[blue] == 0:
            blue += 1
        center = len(r) + red - blue
        LR, RL = red, len(r) - blue
        min_movement = min(min_movement, center + min(LR, RL))
    return min_movement + cnt

if __name__ == '__main__':
    R = input()
    print(solution(R))

이번 글은 여기를 참고하여 작성하였습니다.

따라서 해당 블로그에서의 설명을 바탕으로 알고리즘 원리만 적도록 하겠습니다.

(코드는 해당 블로그를 참고 바랍니다.)

www.acmicpc.net/problem/9251

문제 내용

두 문자열이 주어졌을 때, 공통된 수열의 최장 길이를 구하는 문제다.

즉, DBBE, BDBE 가 주어졌을 때 공통 수열이 될 수 있는 것은 "D, DB, DBE"와 "B, BB, BBE"등이 있다.

그 중 가장 긴 수열은 DBE와 BBE이므로, 답으로 3을 리턴하면 된다.

알고리즘 구상

DBBE와 BDBE를 하나씩 비교하며 공통되는 부분 수열을 구해보자.

1. D와 B      : { }

2. D와 BD    : {D}

3. D와 BDB  : {D}

4. D와 BDBE : {D}

5. DB와 B    : {B}

6. DB와 BD  : {B}, {D}

7. DB와 BDB : {D}, {B}, {D, B}

8. DB와 BDBE : {D}, {B}, {D, B}

9. DBB와 B    : {B}

10. DBB와 BD : {D}, {B}

11. DBB와 BDB : {D}, {B}, {B}, {D, B}, {B, B}

12. DBB와 BDBE : {D}, {B}, {B}, {D, B}, {B, B}

13. DBBE와 B    : {B}

14. DBBE와 BD : {D}, {B}

15. DBBE와 BDB : {B}, {D}, {B}, {D, B}

16. DBBE와 BDBE : {D}, {B}, {B}, {E}, {D, B}, {D, B, E}, {B, B, E}

이러한 과정은 Matrix를 통해 표현될 수 있다.

매트릭스 설명

1. 매트릭의 가장자리는 0으로 덮여있습니다.

2. 세로 축의 DBBE는 첫 번째로 인풋된 데이터를 의미합니다.

3. 가로 축의 BDBE는 두 번째로 인풋된 데이터를 의미합니다.

4. 알고리즘 코드는 맨 위에서부터 가로로 한 줄씩 진행됩니다.

 - 가로 축과 세로 축의 값이 같으면, 왼쪽 대각선 위의 값에서 1을 더해줍니다.

 - 가로 축과 세로 축의 값이 다르면, 왼쪽 또는 위의 값 중 큰 것을 받아옵니다.

위의 매트릭스를 분석해보자

각 칸은 왼쪽과 위측, 왼쪽 대각선 위로부터의 진행 방향을 갖는다.

가로 축과 세로 축의 값이 다르면, 왼쪽 또는 위측이 가진 최장 길이를 그대로 받아오면 된다.

왼쪽 대각선 위의 값을 받아오지 않는 이유는, 알고리즘이 맨 위부터 가로로 한 줄씩 진행됐기 때문이다.

만약 가로 축과 세로 축의 값이 같다면, 왼쪽 대각선 위의 값에서 1을 더해서 가져와야 한다.

왼쪽이나 위쪽에서 값을 가져와서 1을 더한다면, 세로 축(DB)와 가로 축(BDB)의 경우 2가 된다.

(이 경우에는 2가 맞긴 하다. 어쨌든 설명을 더 들어보자)

여기서 나타낸 DB와 BDB의 최장 길이의 공통 수열로 {D, B}를 나타낸 것이지만, 동시에 {B, B}를 의미하게 되고 반례에 해당한다.

코드

밑의 블로그를 참고하길 바랍니다.

suri78.tistory.com/11

www.acmicpc.net/problem/2810

문제 설명

SLLS와 같이 문제가 주어진다.

- S는 *S*로 표현된다.

- LL은 항상 한 쌍으로 주어지며, *LL*로 표현된다.

즉, 예제인 SLLS는 *S*LL*S*로 이해하면 된다.

이 때, *는 컵홀더를 의미하고, S 또는 L은 사람을 의미한다.

S와 L은 본인 옆에 있는 컵홀더를 한 개씩 사용할 수 있다.

이 때, 최대 몇 명이 컵홀더를 사용할 수 있는지를 출력하면 된다.

위 예제의 이 경우 4명이 사용할 수 있다.

문제 분석

왼쪽 필기에 대한 설명으로는,

1. 다양한 경우의 수를 통해 예제를 만들어 보았다.

2. 이 때, 최대의 인원이 컵 홀더를 사용할 수 있도록 매칭시켰다.

3. 오른쪽에 3/3과 같이 적은 숫자는 컵홀더를 사용한 사람/ 총 사람의 수를 의미한다.

결론적으로,

"총 인원 >= 컵홀더 수" 일 때, 컵홀더의 수가 정답으로 출력된 것을 알 수 있었다.

반대로 "총 인원 < 컵홀더의 수"인 경우에는 "총 인원의 수"가 정답으로 출력된다.

알고리즘 구상

문제 분석에서 총 인원과 컵 홀더의 수만 알면 정답을 낼 수 있었다.

1. 총 인원은 첫 번째 INPUT에서 주어진다.

2. 컵 홀더(*)의 수를 구해보자.

 - 예제로 SLLS 가 있다고 가정하자.  컵 홀더는 *S*LL*S*와 같이 배치되어야 한다.

 - 이 때, LL을 한 사람으로 보고 *S*L*S*과 같이 표현할 수 있다. (replace 함수 적용)

 - *S*L*S*를 살펴보면, 컵 홀더의 갯수는 SLS 의 총 길이보다 1 만큼 더 많은 것을 발견할 수 있다.

3. 컵 홀더와 총 인원을 비교

코드

import sys
nPeople = int(input())
seats = input().replace('LL', 'L')
nCups = len(seats) + 1
People >= nCups:
    print(nCups)
else:
    print(nPeople)

www.acmicpc.net/problem/1343

문제 분석

XXXX의 패턴을 보이면 AAAA로 바꾸고,

XX의 패턴을 보이면 BB로 바꾼다.

이 두 패턴을 이용해서 X를 못 없앤다면, -1을 출력한다.

[예제] XX....XXXX..XX  ->> [출력] BB....AAAA..BB

전략

- 파이썬에 내장된 str의 replace()를 쓰자 : 

- 가장 넓은 범위인 'XXXX' 부터 'XX'로 범위를 좁혀가며 replace를 해주면 되겠다.

풀이

import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")

s = input()
s = s.replace('XXXX', 'AAAA')
s = s.replace('XX', 'BB')

if 'X' in s:
    print(-1)
else:
    print(s)

programmers.co.kr/learn/courses/30/lessons/42839

풀이 전략

1. 모든 경우의 수를 탐색해서 숫자의 집합을 만들자

  ex) input =>"14" ,  nums = [1, 4, 14, 41]

2. 소수를 판별하는 함수를 만들어서 총 몇 개의 소수를 만들 수 있는지 return하자

코드

import itertools

def isPrimeNum(n):
    if n == 0 or n == 1:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

def solution(numbers):
    nums = list()
    for i in range(1, len(numbers) + 1):
        N = itertools.permutations(numbers, i)
        nums.extend(map(lambda x: int(''.join(x)), N))       
    nums = set(nums)
    
    res = 0
    for num in nums:
        if isPrimeNum(num):
            res += 1
    return res

www.acmicpc.net/problem/2661

좋은 수열이 될 수 있는 과정 나열

1. 최소 값으로 만들기 위해 1, 2, 3 순으로 넣는다.

2. 반복 수열이 발생하면 맨 뒤의 수를 지우고 다음 수를 넣는다.

구상한 전략

- 1, 2, 3을 반복적으로 리스트 배열에 넣고, DFS를 실행하자.

- 이 때, 좋은 수열인지 확인하는 함수를 만들자(check)

특별히 고려한 점

1. check 함수를 만들 때 어떻게 비교를 시켜야하지?

(1) 1 ~ len(res)//2 의 범위를 갖는다.

(2) 빨강의 범위를 슬라이싱 해보자.

  - res = [1,2,3,4,5,6]에서 뒤의 3개를 선택하기 위해서는 res[-3], 즉 res[-i]

(3) 파랑의 범위를 슬라이싱 해보자.

  - res = [1,2,3,4,5,6]에서 뒤의 빨강 3개와 비교할 파랑 3개를 선택하기 위해서 정할 범위는

     -  빨강에서 -i까지 선택했으므로 res[:-i-1]까지 선택할 수 있다. 

     -  빨강에서 3개를 선택했으므로, 맨 뒤를 기준으로 3*2가 되는 지점을 선택하면 되겠다.

    -  결론적으로, 파랑색은 res[-i-i :-i-1]의 범위를 갖는다. 

코드

import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/codingtest/venv/input.txt", "rt")

def checker(a):
    for i in range(1, len(a)//2 + 1):
        if a[-i:] == a[-i-i:-i]:
            return False
    return True

def DFS(L):
    global res
    global flag

    if flag == 1:
        return

    if x == L:
        flag = 1
        for i in res:
            print(i, end = '')
        return

    else:
        for i in range(1, 4):
            res.append(i)
            if checker(res):
                DFS(L+1)
            res.pop(-1)

if __name__ == '__main__':
    flag = 0
    res = []
    x = int(input())
    DFS(0)

유튜브로 풀이를 녹화했습니다. 아래 링크에서 확인하세요.

youtu.be/rrQ4J-GJC2k

import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/codingtest/venv/input.txt", "rt")
n = int(input())
milks = list(map(int, input().split()))

cnt = 0
turn = 0
for i in range(n):
    if milks[i] == turn:
        cnt += 1
        turn += 1
    if turn == 3:
        turn = 0
print(cnt)

유튜브로 풀이를 녹화했습니다. 아래 링크에서 확인하세요.

www.youtube.com/watch?v=ycHCX-79ZhI