문제 풀이
-
[프로그래머스] 순위문제 풀이 2020. 5. 18. 20:33
문제 설명n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.제한사항선수의 수는 1명 이상 100명 이하입니다.경기 결과는 1개 이상 4,500개 이하입니다.results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.모..
-
[프로그래머스] 섬 연결하기문제 풀이 2020. 5. 18. 20:20
문제 설명n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.제한사항섬의 개수 n은 1 이상 100 이하입니다.costs의 길이는 ((n-1) * n) / 2이하입니다.임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.같은 연결..
-
[프로그래머스] 위장문제 풀이 2020. 5. 17. 16:00
문제 설명스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.종류이름얼굴동그란 안경, 검정 선글라스상의파란색 티셔츠하의청바지겉옷긴 코트스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.제한사항clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.같은 이름을 가진 의상은 존재하지 않습니다.clothes의 모든 원소는 문자열로 이루..
-
[프로그래머스] 소수찾기문제 풀이 2020. 5. 16. 17:41
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.제한사항numbers는 길이 1 이상 7 이하인 문자열입니다.numbers는 0~9까지 숫자만으로 이루어져 있습니다.013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.입출력 예)numbersreturn1730112 풀이)내가 한 코드에서 무엇을 수정할 수 있을 지 적어보겠다.1. 순열을 이용해서 나올 수 있는 모든 수를 확인했다. 순열은 재귀방식을 통해 구했는데, vector의 next_perm..
-
[프로그래머스] 가장 큰수문제 풀이 2020. 5. 16. 16:48
문제 설명0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.제한 사항numbers의 길이는 1 이상 100,000 이하입니다.numbers의 원소는 0 이상 1,000 이하입니다.정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.입출력 예numbersreturn [6, 10, 2] 6210[3,..
-
[프로그래머스] 여행경로문제 풀이 2020. 5. 15. 17:06
문제 설명주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발합니다.항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.제한사항모든 공항은 알파벳 대문자 3글자로 이루어집니다.주어진 공항 수는 3개 이상 10,000개 이하입니다.tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.주어진 항공권은 모두 사용해야 합니다.만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.입출력 예ticketsreturn[[ICN, JFK], [HND, IAD..
-
[SWEA] 5656 벽돌깨기문제 풀이 2020. 5. 14. 22:04
5656 벽돌깨기 풀이)모든 경우를 확인해보는 문제였다. 처음에 없애는 벽돌에 적힌 숫자만큼이나 상하좌우 다른 벽돌을 제거하는 걸 어떻게 처리할까 싶었는데그냥 벽돌에 적힌 수만큼 상하좌우 모두 방문 해보고 바꿔주면 되었다.-> 다 방문한다!! 간단히 풀이과정을 말해보자면 1. dfs을 통해 어떤 행의 벽돌을 없앨 건지, 행들의 순열(n개 길이)을 구한다.2. 그 순열 순서대로 벽돌을 없애고, 벽돌을 내리는 행위를 반복한다. -> 벽돌없애는 과정도 dfs를 통해 없앤다. 벽돌을 없애는 함수는 -> change()벽돌을 내리는 함수는 -> relocate() 주의할 점재귀 방법을 이용해서 벽돌을 없애므로, 이전 상태의 값을 저장해놓고되돌아 왔을 때 원래 값으로 다시 바꿔줘야한다는 점이다. 코드) 123456..
-
[SWEA] 4012 요리사문제 풀이 2020. 5. 13. 23:03
4012 요리사 풀이)문제 자체는 어렵지 않았다.dfs를 이용해 각 음식마다 어떤 식쟤료를 가질건지 결정한 다음, 시너지 계산하는 완전 탐색 문제였다. 그런데 처음에 시간초과 나길래 당황했다.알고보니, n개의 식재료가 있다면 음식 1을 위해 n/2 개까지만 고르고 나머지 쟤료들은 음식 2를 위해 쓰면되는데쓸데없이 식재료 n개의 나올 수 있는 모든 조합을 다 보고 있었다.즉, 음식 1을 위해 n/2개만 고르면 되는데 1~n개까지 고르는 경우를 다 확인한 것이다.(그리고 나서 n/2개씩일때만 계산하게 함) 다시 풀때는 n/2개만 고르고 나머지들은 자동적으로 다른 음식 2를 위해 쓰이게 풀어줬다. 코드) 12345678910111213141516171819202122232425262728293031323334..