내일은 알고리즘

https://school.programmers.co.kr/learn/courses/30/lessons/43162

기본적인 DFS로 풀이가능한 문제입니다.

이 문제도 기본유형의 문제라 레벨이 높은 상태인것 같습니다.

아직 탐색하지 않은 computer를 만나면 DFS로 연결된 모든 컴퓨터들을 탐색하고, 방문처리해주면 됩니다.

DFS 한번에 연결된 컴퓨터들이 전부 방문되기 때문에 정답인 네트워크의 갯수는 DFS의 호출횟수와 같습니다.

def solution(n, computers):
    answer = 0
    visited = [False for i in range(n)]

    for i in range(n):
        if not visited[i]:
            visited[i] = True
            findNetwork(i, computers, visited)
            answer += 1

    return answer


def findNetwork(now, computers, visited):
    for next in range(len(computers[now])):
        if computers[now][next] == 1 and not visited[next]:
            visited[next] = True
            findNetwork(next, computers, visited)
            


print(solution(3, [[1, 1, 0], [1, 1, 1], [0, 1, 1]]))

https://school.programmers.co.kr/learn/courses/30/lessons/42576

참가자와 완주자 사이에 맞지 않는 한 명을 찾는 문제입니다.

HashMap (파이썬의 Dictionary)자료구조를 사용해 풀이했습니다.

문제를 처음 보면 참가자들을 저장하고, 완주자들을 제외 한 뒤 남은 한 명을 구하는 식으로 구현해야할것 같습니다.

하지만 가만히 생각해보면 완주자들을 저장한 뒤 참가자들을 순회하면서 완주자 목록에 없는 사람을 찾는 역순으로 구현하는게 더 간단합니다. 

완주자들의 이름을 key로 Dictionary에 넣어 존재하지 않는다면 value를 1로 저장하고 동명이인이 있다면 value+1로 갱신해줍니다.

이후 참가자들의 이름을 완주자를 저장한 Dictionary에서 확인하면서 하나씩 지워주다가 존재하지 않는 이름이나 완주 목록이 이미 0이 된 이름이 나오면 그 참가자가 우리가 찾는 답이 됩니다.

def solution(participant, completion):
    map = {}

    for i in completion :
        if(i in map):
            map[i] = map.get(i) + 1
        else : 
            map[i] = 1

    for i in participant:
        if(i in map and map[i] > 0):
            map[i] = map.get(i) - 1
        else : 
            return i


participant = [["leo", "kiki", "eden"], ["marina", "josipa", "nikola", "vinko", "filipa"], ["mislav", "stanko", "mislav", "ana"]]
completion = [["eden", "kiki"], ["josipa", "filipa", "marina", "nikola"], ["stanko", "ana", "mislav"]]

for i in range(0,3):
    print(solution(participant[i], completion[i]))

https://school.programmers.co.kr/learn/courses/30/lessons/12977

특정 범위의 소수를 구하는 에라토스테네스의 채와 조합을 응용하는 문제입니다.

우선 세가지 수를 뽑아 나올수 있는 합의 범위는 3000입니다.

매번 합을 구해 소수인지 판별하는것 보다 미리 소수를 구해놓고 비교하는게 더 빠릅니다. 특정 범위안의 모든 소수를 구하는 방법으론 에라토스테네스의 채가 있습니다. 이를 활용해서 3000이하의 모든 수에 관해 소수 여부를 미리 구해놓습니다.

다음으론 더할 세가지 수를 뽑습니다. 순서와 상관없이 합을 구하기 때문에 조합을 응용해 구하면 됩니다.

이번 경우에는 뽑아야할 수가 3개로 정해져 있으므로 3중 for문을 사용해도 구현이 가능합니다.

import copy

def solution(nums):

    def sumCombination(combination):
        return combination[0] + combination[1] + combination[2]

    def makeCombination(list, idx, count):
        if(count == 3):
            combinationList.append(copy.deepcopy(list))
            return
        
        for i in range(idx,len(nums)):
            list[count] = nums[i]
            makeCombination(list, i+1, count+1)


    def makePrimeNumber():
        number = [0 for i in range(3_001)]
        number[1] = 1
        for i in range(2,3_001):
            if(number[i] == 0):
                j = i * 2
                while(j < 3_001):
                    number[j] = 1
                    j += i
        return number

    combinationList = []
    primeNumber = makePrimeNumber()
    makeCombination([0]*3, 0, 0)
    answer = 0
    for i in combinationList:
        sum = sumCombination(i)
        if(primeNumber[sum] == 0):
            answer += 1
            
    return answer


nums = [1,2,7,6,4]
print(solution(nums))

def solution(nums):

    def makePrimeNumber():
        number = [0 for i in range(3_001)]
        number[1] = 1
        for i in range(2, 3_001):
            if(number[i] == 0):
                j = i * 2
                while(j < 3_001):
                    number[j] = 1
                    j += i
        return number

    primeNumber = makePrimeNumber()
    answer = 0

    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            for k in range(j+1, len(nums)):
                sum = nums[i] + nums[j] + nums[k]
                if(primeNumber[sum] == 0):
                    answer += 1
            
    return answer


nums = [1,2,7,6,4]
print(solution(nums))

https://school.programmers.co.kr/learn/courses/30/lessons/81301

오늘 푼 다른 문제들과 비슷한 간단한 시뮬레이션 문제입니다.

앞에서부터 입력된 List를 쭉 읽어가면서 영어로 된 숫자가 나오면 변환하고 단어의 길이만큼 점프해 진행했습니다.

숫자가 나오면 바로 answer에 누적해주었습니다.

자릿수 문제는 앞에서부터 List를 읽어가기 때문에 새로운 숫자가 더해지기 전에 기존의 answer에 10을 곱하고 더하는 식으로 구현했습니다. 

List에 각 자릿수의 숫자를 하나씩 append하고 반복문이 끝난 후 마지막에 List를 숫자로 변환시켜도 같은 결과가 나옵니다.

def solution(s):
    answer = 0
    i = 0
    # numList = []
    while(i < len(s)):
        character = ord(s[i])
        num = 0
        if(48 <= character and character <= 57):
            num = int(s[i])
            i += 1
        else : 
            if(s[i] == 'z'): 
                num = 0
                i += 4
            elif(s[i] == 'o'):
                num = 1
                i += 3
            elif(s[i] == 'e'):
                num = 8
                i += 5
            elif(s[i] == 'n'):
                num = 9
                i += 4
            elif(s[i] == 't'):
                if(s[i+1] == 'w'):
                    num = 2
                    i += 3
                else : 
                    num = 3
                    i += 5
            elif(s[i] == 'f'):
                if(s[i+1] == 'o'):
                    num = 4
                    i += 4
                else : 
                    num = 5
                    i += 4
            else :
                if(s[i+1] == 'i'):
                    num = 6
                    i += 3
                else : 
                    num = 7
                    i += 5
        answer = answer * 10
        answer += num
        # numList.append(str(num))
    # print(numList)
    # numString = "".join(numList)
    # answer = int(numString)
    return answer

input = ["one4seveneight","23four5six7","2three45sixseven","123"]

for i in input:
    print(solution(i))

https://school.programmers.co.kr/learn/courses/30/lessons/72410

문자열이나 문자의 비교, 아스키코드를 알아야 쉽게 풀 수 있는 시뮬레이션 문제입니다.

입력된 문자열을 7단계를 거쳐 요구하는 조건에 맞는 문자열로 변형시켜야 하는데, 한 함수 안에서 동작해도 상관 없지만 구현시에 헷갈리지 않기 위해 7단계를 step 1~7로 쪼개어 각각 구현했습니다.

def solution(new_id):
    
    id = step1(new_id)
    id = step2(id)
    id = step3(id)
    id = step4(id)
    id = step5(id)
    id = step6(id)
    id = step7(id)

    answer = ""
    for i in id:
        answer += i
    return answer

def step1(id):
    result = []
    for i in id:
        character = ord(i)
        if(65 <= character and character <= 90):
            result.append(chr(character + 32))
        else:
            result.append(i)

    return result

def step2(id):
    result = []
    for i in id:
        character = ord(i)
        if((97 <= character and character <= 122) or (48 <= character and character <= 57) or character == 45 or character == 46 or character == 95):
            result.append(i)

    return result

def step3(id):
    result = []
    before = ''
    for i in id:
        if(before == '.' and i == '.'):
            continue
        else :
            result.append(i)
            before = i

    return result

def step4(id):
    if(len(id) > 0 and id[0] == '.'):
        id = id[1:]
    if(len(id) > 0 and id[-1] == '.'):
        id = id[0:-1]
    return id

def step5(id):
    if(len(id) == 0):
        return ['a']
    return id

def step6(id):
    if(len(id) > 15):
        id = id[0:15]
        if(len(id) > 0 and id[-1] == '.'):
            id = id[0:-1]
    return id

def step7(id):
    while(len(id) < 3):
        id.append(id[-1])
    return id


input = ["...!@BaT#*..y.abcdefghijklm","z-+.^.","=.=","123_.def","abcdefghijklmn.p"]
# input = ["...!@BaT#*..y.abcdefghijklm"]

for i in range(len(input)):
    print(solution(input[i]))

https://school.programmers.co.kr/learn/courses/30/lessons/67256

조금 머리를 써야하는 시뮬레이션 문제입니다.

왼손과 오른손의 엄지를 써서 누르는 방법이 정해진 번호 (1,4,7,*)과 (3,6,9,#)은 그대로 진행하면 되지만 중앙의 (2,5,8,0) 번호는 현재 상황에서 더 가까운 손가락을 사용해야 합니다.

저는 각 번호마다 해당 번호와의 거리를 미리 계산해놓고, 현재 손가락의 위치를 통해 거리를 비교하는 식으로 구현했습니다.

def solution(numbers, hand):
    distance = [[3,1,0,1,2,1,2,3,2,3,4,4],[2,2,1,2,1,0,1,2,1,2,3,3],[1,3,2,3,2,1,2,1,0,1,2,2],[0,4,3,4,3,2,3,2,1,2,1,1]]
    # 순서대로 2,5,8,0과 각 버튼(0~9,*,#)의 거리
    flag = (hand == "right")
    left = 10
    right = 11
    answer = ''

    for i in numbers :
        if(i == 1 or i == 4 or i == 7):
            left = i
            answer += 'L'
        elif(i == 3 or i == 6 or i == 9):
            right = i
            answer += 'R'
        else : 
            target = 0
            if(i == 5):
                target = 1
            if(i == 8):
                target = 2
            if(i == 0):
                target = 3
            
            if(distance[target][left] == distance[target][right]):
                if(flag) : 
                    right = i
                    answer += 'R'
                else : 
                    left = i
                    answer += 'L'
            elif(distance[target][left] < distance[target][right]):
                    left = i
                    answer += 'L'
            else : 
                    right = i
                    answer += 'R'
    return answer

numbers = [[1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5],[7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2],[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]]
hand = ["right", "left", "right"]

for i in range(0,3):
    print(solution(numbers[i],hand[i]))

https://school.programmers.co.kr/learn/courses/30/lessons/64061

프로그래머스 사이트가 리뉴얼 되었습니다.

전보다 훨씬 세련되고 보기 좋아졌습니다. 또 새로운 컨텐츠가 들어갈 페이지도 생긴것 같습니다.

파이썬을 오랜만에 쓸 겸 1 레벨 문제를 쭉 풀어봤습니다.

아주 간단한 시뮬레이션 문제입니다.

요구사항대로 입력을 탐색해서 인형을 고르고, 먼저 뽑힌 바구니의 인형과 비교해서 터트려주면 됩니다.

바구니의 구현은 Stack을 이용해도 될것 같지만 List로도 충분하고 더 간단할 것 같아서 List로 구현했습니다.

def solution(board, moves):
    answer = 0
    besket = []

    for i in moves:
        for j in range(0, len(board)):
            if(board[j][i-1] != 0):
                pick = board[j][i-1]
                # print(pick)
                board[j][i-1] = 0

                if(len(besket) > 0 and besket[-1] == pick):
                    besket = besket[0: -1]
                    answer += 2
                else : 
                    besket.append(pick)
                break
    return answer


board = [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]]
moves = [1,5,3,5,1,2,1,4]
print(solution(board, moves))

https://programmers.co.kr/learn/courses/30/lessons/1831

원래는 이분탐색의 Lv.4 문제를 풀려고 했는데, 저도 구현하다가 애매한 부분이 있어 확인해보니 문제에 오류가 있다는 얘기가 많아서 다른 Lv.4 문제를 가져왔습니다.

연산후의 값이 주어지고 그 값이 연산을 통해 만들 수 있는가를 검증하거나 가능한 경우의 수를 찾는 문제는 주어진 값부터 연산을 거꾸로 짚어가며 풀이하면 쉽고 빠르게 풀리는 경우가 많습니다. 이번 문제도 그런 유형이었는데요.

처음엔 3단고음이라는 연산이 중첩되어 계산되는 것을 stack처럼 중첩의 갯수를 카운팅해서 풀이하려고 했는데 구현 난이도가 어마어마 했을 뿐만 아니라 통과도 실패했습니다.

QnA의 도움을 얻어, 이 3단고음이라는 연산은 뒤에서부터 읽어들어갈때, +의 갯수가 2개보다 큰 경우 *하나와 묶어서 사라질 수 있다는걸 알았습니다. 즉, 거꾸로 3단고음 연산이 동작할때 1을 뺄때 +의 갯수를 늘려주고 (+를 역산), +의 갯수가 두개이상이면 3으로 나눠지면서 두개와 소멸하고, 초기값인 1에 도달했을때 +와 *가 모두 상쇄되었으면 카운트를 1 늘려주었습니다.

재귀호출 중간에 ++의 갯수만큼 *의 역산이 이루어져야 하는데 불가능한 경우 가지치기 했습니다.

해당 아이디어를 바탕으로 dfs를 응용한 재귀문을 작성해 테스트케이스를 통과했습니다.

테스트케이스가 하나뿐이라 예외에 걸릴지는 잘 모르겠네요.

public class q1831_Programmers_4단고음 {
	static int answer;

	public static void main(String[] args) {

//		int[] input = { 15, 24, 41 };
		int[] input = { 15, 24, 41, 2147483647 };

		for (int i = 0; i < input.length; i++) {
			System.out.println(solution(input[i]));
		}
	}

	private static int solution(int n) {
		answer = 0;

		dfs(n, 0);

		return answer;
	}

	private static void dfs(int now, int depth) {
		//System.out.println("now:" + now + "   depth:" + depth);
		
		if (now == 1 && depth == 0) {
			answer++;
			return;
		}
		
		if (now < Math.pow(3, (depth / 2))) {
			return;
		}

		dfs(now - 1, depth + 1);
		
		if (depth >= 2 && now >= 3 && now % 3 == 0) {
			dfs(now / 3, depth - 2);
		}

	}

}