수학과의 개발자 도전기

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/17686

Lv2. 문제이다!

생각보다 쉽지 않았던 문제다.

문제 이해

1. Head, Number, Tail을 조건에 맞춰서 분리한다

문자를 탐색하다가 최초로 숫자가 나오면 그 전까지는 무조건 Head이다.(Head는 앞에 위치하고, 문자로만 이루어져있기 때문이다) Head를 제외한 부분부터 숫자가 나오는 구간은 모두 Number로 하고, 그 외의 문자가 나올 때부터 끝까지는 모두 Tail로 지정한다 

2. 우선 순위대로 파일명을 정렬해서 출력한다

2-1. Head(문자)는 사전 순으로 정렬(대소문자 구분하지 않음)

2-2. Number는 01과 1을 같게 정렬한다(숫자 앞의 0은 무시한다)

2-3. Head와 Number가 같다면 원래 입력에 주어진 순서를 유지한다(중복된 파일명에 대해서는 입력된 순서대로 출력한다) 이거는 따로 고려할 필요가 없다. 왜냐하면 파이썬에서 제공하는 sort()함수는 stable 정렬이기 때문이다

(stable은 중복된 값을 입력된 순서와 동일하게 정렬한다)

어려웠던 점

1. Head는 대소문자 구분없이 정렬해야하는데 막상 Head.sort()를 하면 대소문자가 구분되어서 정렬된다. 그렇다고 Head의 모든 값을 lower()를 이용해 소문자로 만들면 또 원상복귀를 해야하고,, 그래서 이부분을 어떻게 해야할지 몰랐다

2. 01과 1을 같게 구분해야하는데 이부분도 sort()로는 잘되지 않았다 

위의 문제를 해결할 코드는 다음과 같다 

    result = sorted(result, key = lambda x : (x[0].lower(), int(x[1])))

3. 그리고 0인덱스는 head,  1인덱스는 number, 2인덱스는 tail로 생각하고 로직을 처음에 작성했지만 이렇게 하면 파일명이 중복될 수 있다. 따라서  head, number, tail에 해당하는 문자열을 명확히 지정해줘야한다 

- 정답 풀이 :

파일명이 중복으로 추가되지 않게 하기 위해 for문에서 두번째 break를 설정해준다

참고한 블로그

def solution(files):
    
    result = []
    head, number, tail = '', '', ''
    for file in files:
        for i in range(len(file)):
            if file[i].isdigit():
                head = file[: i]
                number = file[i:]
                for j in range(len(number)):
                    if not number[j].isdigit():
                        tail = number[j : ]
                        number = number[: j]
                        break
                result.append([head, number, tail])
                head, number, tail = '', '', ''
                break
                      
    result = sorted(result, key = lambda x : (x[0].lower(), int(x[1])))
    
    answer = []
    for x in result:
        answer.append(x[0] + x[1] + x[2])
        
    return answer

- 시도해본 풀이:

소문자로 정렬하는 방법이랑 숫자 정렬하는 법에 대해서 몰랐다

그리고 head, number, tail 잘못 나눈 것 같다

-> 반례 

["foo010bar020.zip", "foo9.txt", "F-15"]일 때, result = [['foo', '010', 'bar020.zip', 'bar020'], ['foo', '9', '.txt'], ['F-']]

로 의도와 다른 값이 생성되므로 틀린 풀이다

def solution(files):
    
    result = []
    #문자는 소문자로 바꾸고 head, number, tail분리 해서 result 배열에 추가한다 
    #숫자 정렬이랑 문자 정렬 
    for file in files:
        temp = []
        idx = 0
        for i in range(1, len(file)):
            if not file[i - 1].isdigit() and file[i].isdigit():
                if idx == 0:
                    temp.append(file[idx : i])
                    idx = i
            if file[i - 1].isdigit() and not file[i].isdigit():
                if idx != 0 :
                    temp.append(file[idx : i])
                    idx = i
            if len(temp) == 2 and idx != 0:
                temp.append(file[idx : ])
                
        result.append(temp)
    
    result = sorted(result, key = lambda x : (x[0].lower(), int(x[1])))
    
    answer = []
    for x in result:
        answer.append(x[0] + x[1] + x[2])
        
    return answer

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/49994

Lv2. 문제이다!

풀이를 진행하면서 놓쳤던 부분이 크게 두 부분이 있는데, 

1. 경로를 양방향이 아닌 단방향으로 생각했기에 a 점 -> b점 가는 건 거를 수 있어도, b점 -> a점으로 가는 경우는 거르지 못해서 틀린 답을 도출할 수 있다

그래서 조건을 만족하는 경로를 roots에 추가할 때 [(x,y), (nx,ny)] 와 [(nx,ny), (x,y)] 모두 추가해야한다

2. 다음 지점인 nx,ny 설정에 미흡했다. 

문제 조건에서는 (-5,-5) ~ (5,5) 외로 이동할 경우에는 그 이동은 무시하고, 유효한 이동을 이어나가면 된다고 했다

2-1.  nx, ny가 범위를 벗어난다면 nx, ny를 x,y(이전 지점)으로 옮기고 다시 범위 안으로 들어올 때까지 반복문을 돌린다

2-1.  nx,ny가 범위에 있다면 이를 다시 시작점으로 옮기면 된다 

풀이 이해 

1. dirs의 문자에 해당하는 이동 좌표를 directions에 설정한 후 진행한다

2. dirs의 0인덱스 문자를 꺼낸 후 문자에 해당하는 만큼 이동한다

3. nx,ny가 범위 내이고, 이전에 가보지 않았던 경로라면 count += 1을 해준다

4. nx,ny가 범위 내이지만, 이전에 가봤던 경로라면 count 값에 변화를 주지 않고 routes에 경로 추가만 하고, 이동한 값을 출발값으로 설정한다

5. nx,ny가 범위 외라면 움직이기 전 값으로 재설정해준다

6. 처음가는 경로만 센 count를 반환한다 

-정답 풀이 :

def solution(dirs):
    #(from, to) 
    routes = []
    directions = {'U': (0, 1), 'D': (0, -1), 'R' : (1, 0), 'L' : (-1, 0)}
    dirs = list(dirs)
    
    count = 0
   
    x,y = 0,0
    while dirs:        
        d = dirs.pop(0)
        nx, ny = x + directions[d][0], y + directions[d][1]
        if -5 <= nx <= 5 and -5 <= ny <= 5:
            if [(x,y), (nx,ny)] not in routes:
                count += 1
            routes.append([(x,y), (nx, ny)])     
            routes.append([(nx, ny), (x,y)]) 
            x, y = nx,ny
        else:
            nx, ny = x, y
            continue
    
    return count

- 시도해본 풀이 :

35%에서 막혔다 

위에서 언급한 문제들 때문에 막혔던 것 같다   

def solution(dirs):
    #(from, to) 
    roots = []
    directions = {'U': (0, 1), 'D': (0, -1), 'R' : (1, 0), 'L' : (-1, 0)}
    dirs = list(dirs)
    
    d = dirs.pop(0)
    roots.append([(0,0), (directions[d][0], directions[d][1])])
    x, y = directions[d][0], directions[d][1]
    count = 1
    
    while dirs:        
        d = dirs.pop(0)
        x, y = roots[-1][1][0], roots[-1][1][1]
        nx, ny = x + directions[d][0], y + directions[d][1]
        if -5 <= nx <= 5 and -5 <= ny <= 5:
            if [(x,y), (nx,ny)] not in roots:
                count += 1
            roots.append([(x,y), (nx, ny)])                
        else:
            continue
    
    return count

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/17679

Lv2 문제다!

로직은 정답과 같은 방향으로 진행한 것 같은데 구현이 시간복잡도가 높아서 계속 시간초과가 발생해서 틀렸던 문제다 

문제 이해

1. 2 x 2 행렬 단위로 탐색하는데, 모두 같은 문자로 이루어져 있는 경우 모든 좌표를 기록한다

2. 해당 좌표의 값들을 모두 0으로 바꾼다(캐릭터가 사라진다)

3. 하나의 열에서 없어진 0의 위에 있는 문자들을 문자가 있는 전 행까지 내린다 

4. 1-3과정을 반복한다

4 -1. 만약 1번을 만족하는 좌표가 더이상 있지 않은 경우(flag == False)에는 루프를 break한다 

3번 과정에 대한 추가 설명

캐릭터가 사라지면 행이 변하므로 열은 신경쓰지 않아도 된다 

가장 마지막 행부터 올라가면서 탐색하는데 이때 0인 값이 있다면 해당 열 위에 0이 아닌 문자인 좌표가 있는지 while을 통해 탐색한다

만약 x < 0이라면 i,j 위로는 문자가 없으므로 board[i][j] = 0 이라 하고,

만약 x >= 0 이라면 i,j 위로는 0이 아닌 문자가 있으므로 위의 문자를 i,j로 옮긴다 

- 정답 풀이 :

board는 모두 문자열로만 이루어져있기 때문에 모두 list로 바꿔줘야한다 

def solution(m, n, board) :
    answer = 0
    board = list(list(b) for b in board)

    while True :
        delete = []
        flag = False
        # 제거할 위치 찾기
        for i in range(m-1) :
            for j in range(n-1) :
                if board[i][j] != 0 and board[i][j] == board[i][j+1] == board[i+1][j] == board[i+1][j+1] :
                    delete.append((i, j))
                    delete.append((i, j+1))
                    delete.append((i+1, j))
                    delete.append((i+1, j+1))
                    flag = True

        if flag == False :
            break

        # 위치 제거
        for x, y in delete :
            board[x][y] = 0

        # 남쪽 방향으로 위치 이동
        for i in range(m-1, -1, -1) :
            for j in range(n) :
                if board[i][j] == 0 :
                    x = i - 1
                    while x >= 0 and board[x][j] == 0 :
                        x -= 1
                    #i,j 위로 0이 아닌 문자가 있는 경우에는 그 문자를 i,j로 옮긴다     
                    if board[x][j] != 0 and x >= 0 :
                        board[i][j] = board[x][j]
                        board[x][j] = 0

    for i in range(m) :
        answer += board[i].count(0)

    return answer

- 시도해본 풀이 :

시간초과 발생

def check(board, alphabet, x, y):
    count = []
    n , m = len(board[0]), len(board)
    if x + 1 < m and y + 1 < n:
        for i in range(x, x + 2):
            for j in range(y, y + 2):
                if board[i][j] == alphabet:
                    count.append([i, j])
    return count
                
def solution(m, n, board):
    for i in range(m):
        board[i] = list(board[i])
    count = 0
    #없애야 할 원소들 좌표 추가하기
    while True:
        result = []
        flag = False
        for x in range(m):
            for y in range(n):
                temp = check(board, board[x][y], x, y)
                if len(temp) == 4:
                    flag = True
                    for i in range(4):
                        result.append(temp[i])
                    
        if not flag:
            break
        
        #원소들 없애기    
        for i in range(len(result)):
            a, b = result[i]
            if board[a][b] != 0:
                count += 1
                board[a][b] = 0        
                
        for j in range(1, n):
            start , end = 0, 0
            for i in range(1, m):
                if board[i - 1][j] != 0 and board[i][j] == 0:
                    start = i
                if board[i - 1][j] == 0 and board[i][j] != 0:
                    end = i - 1
            diff = end - start + 1
            #j열에서 0행부터 start -1 행까지의 원소들
            for i in range(start):
                board[i + diff][j] = board[i][j]
                board[i][j] = 0
                
    return count

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/49993

Lv2문제이고, 스스로 푼 문제다!

처음에는 문제를 코드로 옮기는데 우왕좌왕했던 것 같다 

문제에서 핵심은 skill의 모든 문자를 다 가지고 있지 않아도 skill과 겹치는 알파벳들을 나열했을 때 skill의 순서와 일치하는 skill_tree들만 세는 것이다 

예제에서 0인덱스 문자열은 skill의 알파벳을 다 가지고 있지만, 순서가 맞지 않기 때문에 조건을 만족하지 못한다

그래서 skill_tree중에서 skill에 포함되는 모든 문자들을 모은 후 그것들이 skill의 순서와 같으면 count하고 아니라면 넘어간다

문제 해설

1. skill_trees에 있는 문자열 하나씩 탐색한다. 인덱스를 사용할 것이므로 list로 변환해준다

2. skill_tree에서 skill에 포함되는 문자인 경우 temp에 추가한다

3. temp의 길이만큼 skill을 잘랐을 때, 자른 리스트와 temp가 일치하면 숫자를 count하고, 아니면 넘어간다 

4. 센 문자열의 갯수를 반환한다

- 정답 풀이 :

def solution(skill, skill_trees):
    count = 0
    skill = list(skill)
    
    #skill에 해당하는 알파벳들의 skill_tree에서 인덱스를 순서대로 구한다 
    for skill_tree in skill_trees:
        skill_tree = list(skill_tree)
        temp = []
        for i in range(len(skill_tree)):
            if skill_tree[i] in skill:
                temp.append(skill_tree[i])
                                       
        if temp == skill[: len(temp)]:
            count += 1
                      
    return count