큰 문제를 작은 문제로 나누어 푸는 문제

• 부분문제가 중복되어 상위 문제 해결에 재활용
• Memoization 사용 o

대표적인 예시 문제로 피보나치가 있음.

분할정복과 유사하다고 느끼는 부분이 있었으나 차이점이 존재했다.

분할정복

문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 푸는 알고리즘

• 부분문제가 중복되지 않는다.
• Memoization 사용 x

풀이 방법의 단계

1. DP문제인지 확인
2. 최소한의 매개변수를 활용해 상태표현식을 결정한다.
3. 점화식을 세운다.
4. 상향식(for문 을 통해) or 하향식(재귀함수를 통해)을 이용하여 문제를 해결한다.

2. 상태표현식 결정

상태를 나타내줄 매개변수를 최소한으로 설정하여 어떤 상태를 기준으로 문제를 풀어나갈지 결정해야 한다. << 문제를 쪼개고 점화식을 표현할 때 중요함.

다음단계와 이전관계들 사이의 관계를 찾고 점화식으로 표현할 때 중요함.

문제 링크

성능 요약

메모리: 11148 KB, 시간: 228 ms

분류

다이나믹 프로그래밍(dp)

문제 설명

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

출력

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

접근법

DP(Dynamic Programming)에 대해 공부하고 의도적으로 문제 유형을 맞춰서 푼 문제라 그런지 난이도가 어렵지 않았다.

공부한 내용대로 A_i=[A_i-1+1 || A_i-j+1] 라고 점화식을 두고 푸니 쉽게 풀 수있었다.

** _{i=(전체가격을 모아놓은 배열의 인덱스), j=(주어진 동전가치 배열의 인덱스)}

기본적으로 최솟값을 구하는 문제이다보니 배열에 100000의 큰 수를 채워놓고 시작했다.

내 풀이

const fs = require("fs")
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt"

let [n, ...input] = fs.readFileSync(filePath).toString().trim().split("\n")

const [N, K] = n.split(" ").map(Number)

input = input.map(Number)

const arr = new Array(K + 1).fill(100000)
arr[0] = 0
input.map((e) => {
  arr[e] = 1
})
function solution(target) {
  for (let i = 1; i < target + 1; i++) {
    for (let j = 0; j < N; j++) {
      if (input[j] < i) {
        arr[i] = Math.min(arr[i], arr[i - input[j]] + 1)
      }
    }
  }
  if (arr[target] === 100000) return -1
  return arr[target]
}
console.log(solution(K))

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

문제 설명
H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 
어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 
위키백과1에 따르면, H-Index는 다음과 같이 구합니다.

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 
h의 최댓값이 이 과학자의 H-Index입니다.

어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때,
이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

제한사항
과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.
논문별 인용 횟수는 0회 이상 10,000회 이하입니다.
입출력 예
citations          return
[3, 0, 6, 1, 5]      3


입출력 예 설명
이 과학자가 발표한 논문의 수는 5편이고,
그중 3편의 논문은 3회 이상 인용되었습니다.
그리고 나머지 2편의 논문은 3회 이하 인용되었기 때문에 이 과학자의 H-Index는 3입니다.

처음코드 및 접근

문제를 읽고 아 ! 이건 대놓고 정렬이구나 생각을 했다. 바로 배열(citations)을 정렬하고 정렬한 배열(citations)의 인덱스(i)와 값(citations[i])을 비교하여 k배열에 넣어주고 그 배열에서 최댓값을 뽑아 H-index를 가져오기로 했다.

function solution(citations) {
    var answer = 0;
    citations=citations.sort((a,b)=>a-b)
    let k=[0]
    for(let i=0;i<citations.length;i++){
        if(citations[i]<=(citations.length-i)&&citations[i]>=i+1){
          //논문 인용수(h)<=h번이상인용된논문갯수
            k.push(citations[i])
        }
    }
    answer=Math.max(...k)

    return answer;
}

채점을 시작합니다.
정확성  테스트
테스트 1 〉    실패 (0.30ms, 33.4MB)
테스트 2 〉    실패 (0.40ms, 33.4MB)
테스트 3 〉    실패 (0.58ms, 33.5MB)
테스트 4 〉    실패 (0.50ms, 33.4MB)
테스트 5 〉    실패 (0.60ms, 33.5MB)
테스트 6 〉    실패 (0.80ms, 33.5MB)
테스트 7 〉    실패 (0.38ms, 33.5MB)
테스트 8 〉    실패 (0.26ms, 33.4MB)
테스트 9 〉    실패 (0.18ms, 33.6MB)
테스트 10 〉    실패 (0.26ms, 33.5MB)
테스트 11 〉    통과 (0.50ms, 33.5MB)
테스트 12 〉    실패 (0.30ms, 33.4MB)
테스트 13 〉    실패 (0.50ms, 33.6MB)
테스트 14 〉    실패 (0.39ms, 33.5MB)
테스트 15 〉    실패 (0.64ms, 33.5MB)
테스트 16 〉    통과 (0.08ms, 33.5MB)
채점 결과
정확성: 12.5
합계: 12.5 / 100.0

기본 예제는 맞췄지만 테스트케이스에선 후두둑 틀렸다. 왜지? 한참을 고민해도 이해가 안가서 프로그래머스에 친절하게 공유되어있는 정답코드를 보았다.

참고했던 정답 코드

function solution(citations) {
    let answer = 0;
    citations.sort((a,b) => b-a);//sort를 내림차순으로
    for(let i = 0; i <citations.length ; i ++) {
        if(citations[i] >= i+1 && citations[i] >= (citations.length - i)) {
            answer++;
            continue;
        }
        break;
    }    
    return answer;
}

정답까지 틀렸던 이유

처음엔 잘 이해가 가지 않았는데 내 방식의 코드를 이용하면 인용된 횟수가 같은 것이 존재하는 배열이 나왔을 때 문제가 생기지 않을까 라는 생각을 했고 테스트 케이스를 추가하여 돌려봤다. 아니나 다를까 문제점 발견.. 이게 문제였겠거니.. 하고 생각해 봤는데 볼수록 H-index 자체에 대한 의문이 들었다. H-index에 대한 문제의 해설과 나무위키의 내용이나 프로그래머스 질문게시판의 내용이 내가 이해하기에는 굉장히 상이했다. H-index를 잘못이해해서 한참걸린 문제..

이해하고 문제를 다시풀어보니 프로그래머스의 정답코드가 굉장히 합리적이였다는걸 깨닳았다.

문제를 제대로 이해하고 풀이를 시작하자.

성능 요약

메모리: 126856 KB, 시간: 996 ms

분류

깊이 우선 탐색(dfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal), 정렬(sorting)

문제 설명

오늘도 서준이는 깊이 우선 탐색(DFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 깊이 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.

깊이 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 오름차순으로 방문한다.

dfs(V, E, R) {  # V : 정점 집합, E : 간선 집합, R : 시작 정점
    visited[R] <- YES;  # 시작 정점 R을 방문 했다고 표시한다.
    for each x ∈ E(R)  # E(R) : 정점 R의 인접 정점 집합.(정점 번호를 오름차순으로 방문한다)
        if (visited[x] = NO) then dfs(V, E, x);
}

입력

첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다.

다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방향 간선을 나타낸다. (1 ≤ u < v ≤ N, u ≠ v) 모든 간선의 (u, v) 쌍의 값은 서로 다르다.

출력

첫째 줄부터 N개의 줄에 정수를 한 개씩 출력한다. i번째 줄에는 정점 i의 방문 순서를 출력한다. 시작 정점의 방문 순서는 1이다. 시작 정점에서 방문할 수 없는 경우 0을 출력한다.

정답코드

const fs = require("fs")

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt"

let input = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n")
  .map((val) => val.replace("\r", ""))
  .map((val) => val.split(" "))

let [nodeNum, lineNum, startNode] = input[0].map(Number)
let graph = new Map()
let visited = new Array(nodeNum).fill(0)
let cnt = 1

//그래프 세팅
for (let i = 0; i < nodeNum; i++) {
  graph.set(i + 1, [])
}
//그래프에는 각 노드당 연결되는 노드를 배열로
for (let i = 1; i <= lineNum; i++) {
  let [start, end] = input[i].map(Number)
  graph.get(start).push(end)
  graph.get(end).push(start)
}
//그래프의 배열들을 오름차순 정렬
graph.forEach((v) => {
  v.sort((a, b) => {
    return a - b
  })
})
DFS(startNode)
function DFS(node) {
  //방문하지 않은 노드만 체크
  if (visited[node - 1] == 0) {
    visited[node - 1] = cnt
    cnt++
    graph.get(node).forEach((v) => {
      DFS(v)
    })
  }
}
//[velog]:https://velog.io/@yodiodine/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B83-24479-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%88%98%EC%97%85
//위의 벨로그에서 코드를 보고 공부함 직접작성한코드 x
console.log(visited.join("\n"))

배운점

배열의 map() 메서드를 통해 값을 바꿀 줄 알게되었다. JavaScript에서 그래프를 사용하는 방법을 알게 되었다.

반복과 재귀

반복은 수행 작업이 완료 될 때 까지 계속해서 반복
for/while,do~while 문

재귀 함수(recursive function)

- 주어진 문제의 해를 구하기 위해 동일하면서 더 작은 문제의 해를 이용하는 방법

- 하나의 큰 문제를 해결 할 수 있는 작은 문제로 쪼개고 결과들을 결합한다.

함수 내부에서 직접 혹은 간접적으로 자기자신을 호출하는 함수

- 기본 부분(끊어 주는 부분)과 유도 부분(반복 부분)으로 구성

- 함수 호출은 프로그램 메모리 구조에서 스택을 사용한다.

- 조건에 맞았을 때, return 되도록 구성 해야 한다.

- 스택의 사용을 의미하며 메모리 및 속도에서 성능저하가 발생한다.

배열이란?

일정한 자료형의 변수들을 하나의 이름으로 열거하여 사용하는 것입니다.

배열의 특징

인덱스를 활용하여 접근 할 수 있다.
한번의 선언을 통해 둘 이상의 변수를 선언 할 수 있다.

자바에서 배열의 선언

int arr[] = new int[4]; >> 자료형 배열명[] = new 자료형[배열크기];
int[] arr = new int[4]; >> 자료형[] 배열명 = new 자료형[배열크기];

배열의 순회

for i from 0 to n-1
    Array[i]; 

배열의 원소 Shift

오른쪽 shift 
    arr[i+1]=arr[i];
왼쪽 shift
    arr[i]=arr[i-1];
** 주의 **
    인덱스 범위에 주의할 것!

메모리의 길이를 한번 정하면 크기를 변경할 수 없다. 연속된 공간을 할당해주기 때문

참조 값 할당 : points = new int[3];

index를 통해 접근 가능

for-each with Array : 가독성이 개선된 반복문, 배열 및 Collections 에서 사용 index 대신 직접요소(elements)에 접근하는 변수를 제공 naturally ready only(copied value) 사용법 : int array[]={1,2,3,4,5}; for(int x : array){ 선언문; }

Garbage Collection :더 이상 사용하지 않는 메모리를 자동으로 정리하는 기능

변수 : 메모리 공간 >> 값을 할당하여 사용

공간의 크기는 타입별로 변하게 된다.

Type

Primitive Type(기본형) : 미리 정해진 크기의 Memory Size로 표현 변수 자체에 값 저장

boolean 논리

byte 정수

short 정수

int 정수

long 정수

float 실수

double 실수

char 문자

Reference(참조형) : 크기가 미리 정해질 수 없는 데이터의 표현 변수에는 실제 값을 참조할 수 있는 주소만 저장

최대로 사용할 수 있는 참조형 데이터 타입의 개수 : 무제한

Type Name = Value ;

형변환

묵시적 형변환 >> 타입의 크기가 아니라 표현 범위가 커지는 방향으로 할당할 경우 발생 : 작은 메모리 > 큰 메모리 명시적 형변환 >> 값 손실이 발생할 수 있으므로 프로그래머 책임하에 형변환 진행 : 큰 메모리 > 작은 메모리

메모리 크기 순서 byte < short,char < int < long < float < double

정확성  테스트
테스트 1 〉    통과 (0.02ms, 4.18MB)
테스트 2 〉    통과 (0.38ms, 4.19MB)
테스트 3 〉    통과 (0.36ms, 4.3MB)
테스트 4 〉    통과 (0.02ms, 4.18MB)
테스트 5 〉    통과 (0.08ms, 4.23MB)
테스트 6 〉    통과 (0.06ms, 4.32MB)
테스트 7 〉    통과 (0.37ms, 4.23MB)
테스트 8 〉    통과 (0.39ms, 4.2MB)
테스트 9 〉    통과 (0.05ms, 4.2MB)
테스트 10 〉    통과 (0.02ms, 4.29MB)
테스트 11 〉    통과 (0.02ms, 4.29MB)
테스트 12 〉    통과 (0.39ms, 4.25MB)
테스트 13 〉    통과 (0.05ms, 3.74MB)
테스트 14 〉    통과 (0.02ms, 4.32MB)
테스트 15 〉    통과 (0.02ms, 3.69MB)
테스트 16 〉    통과 (0.02ms, 4.25MB)
테스트 17 〉    통과 (0.02ms, 4.19MB)
테스트 18 〉    통과 (0.79ms, 4.18MB)
테스트 19 〉    통과 (0.81ms, 4.17MB)
테스트 20 〉    통과 (0.85ms, 4.25MB)
테스트 21 〉    통과 (0.02ms, 4.24MB)
테스트 22 〉    통과 (0.02ms, 4.18MB)
채점 결과
정확성: 100.0
합계: 100.0 / 100.0

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    vector<int> Line=times;
    for(int i=0;i<n;i++){
        if(i==n-1){
            answer=*min_element(Line.begin(), Line.end());
            break;}

        Line[min_element(Line.begin(), Line.end()) - Line.begin()]+=times[min_element(Line.begin(), Line.end()) - Line.begin()];

    }


    return answer;
}

정확성  테스트
테스트 1 〉    통과 (0.01ms, 3.76MB)
테스트 2 〉    통과 (0.14ms, 4.34MB)
테스트 3 〉    실패 (4.56ms, 3.71MB)
테스트 4 〉    통과 (7036.43ms, 7.08MB)
테스트 5 〉    실패 (시간 초과)
테스트 6 〉    실패 (시간 초과)
테스트 7 〉    실패 (시간 초과)
테스트 8 〉    실패 (시간 초과)
테스트 9 〉    통과 (7563.87ms, 3.7MB)
채점 결과
정확성: 44.4
합계: 44.4 / 100.0

2회차

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    sort(times.begin(),times.end());
    long long min=1;
    long long max=(long long)times[times.size()-1]*n;

    while(min<=max){
        long long mid=(max+min)/2;
        long long count=0;
        for(int i=0;i<times.size();i++){
            count+=mid/times[i];
        }
        if(count<n)min=mid+1;
        else{
            if(mid<=max){
                answer=mid;
            }
            max=mid-1;
        }


    }

    return answer;
}

정확성  테스트
테스트 1 〉    통과 (0.01ms, 4.34MB)
테스트 2 〉    통과 (0.03ms, 3.98MB)
테스트 3 〉    통과 (0.38ms, 3.99MB)
테스트 4 〉    통과 (43.62ms, 6.82MB)
테스트 5 〉    통과 (45.03ms, 6.83MB)
테스트 6 〉    통과 (49.87ms, 6.57MB)
테스트 7 〉    통과 (54.95ms, 6.82MB)
테스트 8 〉    통과 (53.87ms, 6.82MB)
테스트 9 〉    통과 (0.01ms, 3.92MB)
채점 결과
정확성: 100.0
합계: 100.0 / 100.0

정확성  테스트
테스트 1 〉    통과 (0.01ms, 3.96MB)
테스트 2 〉    통과 (0.01ms, 3.97MB)
테스트 3 〉    통과 (0.01ms, 3.98MB)
테스트 4 〉    통과 (0.01ms, 3.99MB)
테스트 5 〉    통과 (0.01ms, 3.9MB)
테스트 6 〉    통과 (0.01ms, 3.93MB)
테스트 7 〉    통과 (0.01ms, 3.96MB)
테스트 8 〉    통과 (0.01ms, 3.97MB)
테스트 9 〉    통과 (0.01ms, 3.73MB)
테스트 10 〉    통과 (0.01ms, 3.96MB)
테스트 11 〉    통과 (0.01ms, 3.92MB)
테스트 12 〉    통과 (0.01ms, 3.7MB)
테스트 13 〉    통과 (0.01ms, 3.72MB)
테스트 14 〉    통과 (0.01ms, 3.95MB)
테스트 15 〉    통과 (0.01ms, 3.98MB)
테스트 16 〉    통과 (0.01ms, 3.96MB)
테스트 17 〉    통과 (0.01ms, 3.96MB)
테스트 18 〉    통과 (0.01ms, 3.95MB)
테스트 19 〉    통과 (0.01ms, 3.94MB)
테스트 20 〉    통과 (0.01ms, 3.96MB)
테스트 21 〉    통과 (0.01ms, 3.9MB)
테스트 22 〉    통과 (0.01ms, 3.95MB)
테스트 23 〉    통과 (0.01ms, 3.93MB)
채점 결과
정확성: 100.0
합계: 100.0 / 100.0

정확성  테스트
테스트 1 〉    통과 (0.01ms, 3.96MB)
테스트 2 〉    통과 (0.02ms, 3.95MB)
테스트 3 〉    통과 (0.01ms, 3.97MB)
테스트 4 〉    통과 (0.01ms, 3.95MB)
테스트 5 〉    통과 (0.01ms, 3.95MB)
테스트 6 〉    통과 (0.02ms, 3.96MB)
테스트 7 〉    통과 (0.01ms, 3.94MB)
테스트 8 〉    통과 (0.01ms, 3.96MB)
테스트 9 〉    통과 (0.02ms, 3.95MB)
테스트 10 〉    통과 (0.01ms, 3.95MB)
효율성  테스트
테스트 1 〉    통과 (11.23ms, 47.6MB)
테스트 2 〉    통과 (10.91ms, 44.7MB)
테스트 3 〉    통과 (11.34ms, 46.5MB)
테스트 4 〉    통과 (11.71ms, 47.1MB)
테스트 5 〉    통과 (9.67ms, 39.6MB)
테스트 6 〉    통과 (10.49ms, 45.2MB)
테스트 7 〉    통과 (5.83ms, 27.6MB)
테스트 8 〉    통과 (6.18ms, 28.4MB)
테스트 9 〉    통과 (7.33ms, 32.9MB)
테스트 10 〉    통과 (10.47ms, 45.5MB)
채점 결과
정확성: 50.0
효율성: 50.0
합계: 100.0 / 100.0

#include <string>
#include <vector>

using namespace std;

void dfs(int node, vector<vector<int>>& computers, vector<bool>& visited, int n){
    visited[node]=true;
    for(int i=0;i<n;i++){
       if(!visited[i]&&computers[node][i])dfs(i,computers,visited,n); 
    }    
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    vector<bool> visited(n,false);
    for(int i=0;i<n;i++){
        if(!visited[i]){
            answer++;
            dfs(i,computers,visited,n);
        }
    }


    return answer;
}

정확성  테스트
테스트 1 〉    통과 (0.01ms, 3.93MB)
테스트 2 〉    통과 (0.01ms, 3.95MB)
테스트 3 〉    통과 (0.01ms, 3.94MB)
테스트 4 〉    통과 (0.01ms, 3.93MB)
테스트 5 〉    통과 (0.01ms, 3.94MB)
테스트 6 〉    통과 (0.02ms, 3.94MB)
테스트 7 〉    통과 (0.01ms, 3.9MB)
테스트 8 〉    통과 (0.02ms, 3.82MB)
테스트 9 〉    통과 (0.01ms, 3.92MB)
테스트 10 〉    통과 (0.02ms, 3.93MB)
테스트 11 〉    통과 (0.04ms, 4MB)
테스트 12 〉    통과 (0.05ms, 3.96MB)
테스트 13 〉    통과 (0.03ms, 3.72MB)
채점 결과
정확성: 100.0
합계: 100.0 / 100.0

깊이우선 탐색 문제이다.

깊이우선 탐색방식에서 재귀함수를 이용해 보았고 추후 stack을 이용한 코드를 작성 해볼 예정

점의 방문 여부를 판단하고 깊이우선 탐색을 하는 방식을 for문으로 돌렸다.

정확성  테스트
테스트 1 〉    통과 (68.13ms, 3.77MB)
테스트 2 〉    통과 (60.48ms, 3.96MB)
테스트 3 〉    통과 (0.08ms, 3.95MB)
테스트 4 〉    통과 (0.31ms, 3.94MB)
테스트 5 〉    통과 (2.15ms, 3.72MB)
테스트 6 〉    통과 (0.14ms, 3.77MB)
테스트 7 〉    통과 (0.07ms, 3.96MB)
테스트 8 〉    통과 (0.59ms, 3.89MB)
채점 결과
정확성: 100.0
합계: 100.0 / 100.0

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool comp(string a, string b) {
    return a > b;
}

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    sort(participant.begin(), participant.end(), comp);
    sort(completion.begin(), completion.end(), comp);

    for (int i = 0; completion.size(); i++) {
        if (participant[i] != completion[i]) {
            answer = participant[i];
            break;
        }

    }
    if (answer.empty()) {
        answer = participant[participant.size() - 1];
    }



    return answer;
}

정확성 테스트
테스트 1 〉 통과 (0.01ms, 3.97MB)
테스트 2 〉 통과 (0.01ms, 3.96MB)
테스트 3 〉 통과 (0.65ms, 3.88MB)
테스트 4 〉 통과 (1.36ms, 3.96MB)
테스트 5 〉 통과 (1.39ms, 3.95MB)
효율성 테스트
테스트 1 〉 통과 (85.62ms, 14.4MB)
테스트 2 〉 통과 (132.46ms, 19.7MB)
테스트 3 〉 통과 (172.99ms, 23.2MB)
테스트 4 〉 통과 (197.24ms, 25.3MB)
테스트 5 〉 통과 (196.17ms, 25.4MB)
채점 결과
정확성: 50.0
효율성: 50.0
합계: 100.0 / 100.0

다시풀기

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = participant.back();
    sort(participant.begin(),participant.end());

    sort(completion.begin(),completion.end());

    for(int i=0;i<participant.size();i++){
        if(participant[i]!=completion[i]){
            answer=participant[i];
            break;
        }    

    }


    return answer;
}

정확성  테스트
테스트 1 〉    통과 (0.02ms, 3.76MB)
테스트 2 〉    통과 (0.02ms, 3.95MB)
테스트 3 〉    통과 (0.28ms, 3.83MB)
테스트 4 〉    통과 (0.53ms, 3.79MB)
테스트 5 〉    통과 (0.60ms, 3.9MB)
효율성  테스트
테스트 1 〉    통과 (36.61ms, 14.2MB)
테스트 2 〉    통과 (57.06ms, 19.7MB)
테스트 3 〉    통과 (66.59ms, 23.4MB)
테스트 4 〉    통과 (78.05ms, 25.4MB)
테스트 5 〉    통과 (78.39ms, 25.3MB)
채점 결과
정확성: 50.0
효율성: 50.0
합계: 100.0 / 100.0

이전 풀이에서는 불필요하게 comp함수를 작성하여 속도가 두배 이상 차이가 났다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    sort(phone_book.begin(),phone_book.end());
    for(int i=0;i<phone_book.size()-1;i++){
    if(phone_book[i]==phone_book[i+1].substr(0,phone_book[i].size())){
        answer=false;
        break;
    }

    }

    return answer;
}

정확성 테스트
테스트 1 〉 통과 (0.01ms, 3.94MB)
테스트 2 〉 통과 (0.01ms, 3.94MB)
테스트 3 〉 통과 (0.01ms, 3.95MB)
테스트 4 〉 통과 (0.01ms, 3.94MB)
테스트 5 〉 통과 (0.01ms, 3.95MB)
테스트 6 〉 통과 (0.01ms, 3.79MB)
테스트 7 〉 통과 (0.01ms, 3.93MB)
테스트 8 〉 통과 (0.01ms, 3.9MB)
테스트 9 〉 통과 (0.01ms, 3.9MB)
테스트 10 〉 통과 (0.01ms, 3.94MB)
테스트 11 〉 통과 (0.01ms, 3.93MB)
테스트 12 〉 통과 (0.01ms, 3.95MB)
테스트 13 〉 통과 (0.01ms, 3.95MB)
테스트 14 〉 통과 (0.28ms, 3.96MB)
테스트 15 〉 통과 (0.40ms, 3.88MB)
테스트 16 〉 통과 (0.47ms, 3.85MB)
테스트 17 〉 통과 (0.61ms, 4MB)
테스트 18 〉 통과 (0.84ms, 3.91MB)
테스트 19 〉 통과 (0.92ms, 3.95MB)
테스트 20 〉 통과 (0.81ms, 3.93MB)
효율성 테스트
테스트 1 〉 통과 (3.49ms, 4.44MB)
테스트 2 〉 통과 (3.70ms, 4.53MB)
테스트 3 〉 통과 (83.59ms, 35.8MB)
테스트 4 〉 통과 (82.07ms, 31.5MB)
채점 결과
정확성: 83.3
효율성: 16.7
합계: 100.0 / 100.0

다시풀기

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    sort(phone_book.begin(),phone_book.end());
    for(int i=0;i<phone_book.size()-1;i++){
        if(phone_book[i].size()>phone_book[i+1].size())continue;
        for(int j=0;j<phone_book[i].size();j++){
            if(phone_book[i][j]!=phone_book[i+1][j])break;
            if(j==phone_book[i].size()-1)return false;
        }

    }


    return answer;
}

정확성  테스트
테스트 1 〉    통과 (0.01ms, 3.96MB)
테스트 2 〉    통과 (0.01ms, 3.94MB)
테스트 3 〉    통과 (0.01ms, 3.91MB)
테스트 4 〉    통과 (0.01ms, 3.95MB)
테스트 5 〉    통과 (0.01ms, 3.98MB)
테스트 6 〉    통과 (0.01ms, 3.97MB)
테스트 7 〉    통과 (0.01ms, 3.95MB)
테스트 8 〉    통과 (0.01ms, 3.91MB)
테스트 9 〉    통과 (0.01ms, 3.96MB)
테스트 10 〉    통과 (0.01ms, 3.97MB)
테스트 11 〉    통과 (0.01ms, 3.96MB)
테스트 12 〉    통과 (0.01ms, 3.96MB)
테스트 13 〉    통과 (0.01ms, 3.96MB)
테스트 14 〉    통과 (0.27ms, 3.96MB)
테스트 15 〉    통과 (0.36ms, 3.9MB)
테스트 16 〉    통과 (0.47ms, 3.99MB)
테스트 17 〉    통과 (0.50ms, 3.98MB)
테스트 18 〉    통과 (0.74ms, 3.95MB)
테스트 19 〉    통과 (0.85ms, 3.95MB)
테스트 20 〉    통과 (0.88ms, 3.97MB)
효율성  테스트
테스트 1 〉    통과 (3.76ms, 4.5MB)
테스트 2 〉    통과 (3.54ms, 4.43MB)
테스트 3 〉    통과 (79.05ms, 35.6MB)
테스트 4 〉    통과 (78.61ms, 31.6MB)
채점 결과
정확성: 83.3
효율성: 16.7
합계: 100.0 / 100.0

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool SortSecCol(const vector<string>& v1, const vector<string>& v2){
    return v1[1]<v2[1];
}

int solution(vector<vector<string>> clothes) {
    int answer = 1;
    int temp=0;
    sort(clothes.begin(),clothes.end(),SortSecCol);

    for(int j=0;j<clothes.size();j++){
        if(j==clothes.size()-1){
            if(clothes[1][j]==clothes[1][j-1]){
            answer=answer*(temp+1)-1;}
            else{
                answer=answer*2-1;
            }
        }
        else{
            if(clothes[1][j]==clothes[1][j+1]){
                temp++;
            }
            else{
                temp++;
                answer=answer*(temp+1);
                temp=0;

            }

        }

    }


    return answer;
}

다시풀기

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool seccol(const vector<string>& v1, const vector<string>& v2){
    return v1[1]<v2[1];
}


int solution(vector<vector<string>> clothes) {
    int answer = 1;
    sort(clothes.begin(),clothes.end(),seccol);
    int temp=2;
    for(int i=1;i< clothes.size();i++){
        if(clothes[i][1]!=clothes[i-1][1]){
            answer*=temp;
            temp=2;
            continue;
        }
        temp++;

    }
    answer*=temp;

    return answer-1;
}

채점을 시작합니다.
정확성  테스트
테스트 1 〉    통과 (0.02ms, 3.97MB)
테스트 2 〉    통과 (0.01ms, 3.95MB)
테스트 3 〉    통과 (0.01ms, 3.97MB)
테스트 4 〉    통과 (0.01ms, 3.95MB)
테스트 5 〉    통과 (0.03ms, 3.94MB)
테스트 6 〉    통과 (0.01ms, 3.95MB)
테스트 7 〉    통과 (0.02ms, 3.89MB)
테스트 8 〉    통과 (0.01ms, 3.94MB)
테스트 9 〉    통과 (0.01ms, 3.94MB)
테스트 10 〉    통과 (0.01ms, 3.96MB)
테스트 11 〉    통과 (0.01ms, 3.95MB)
테스트 12 〉    통과 (0.02ms, 3.9MB)
테스트 13 〉    통과 (0.01ms, 3.94MB)
테스트 14 〉    통과 (0.01ms, 3.77MB)
테스트 15 〉    통과 (0.01ms, 3.94MB)
테스트 16 〉    통과 (0.01ms, 3.95MB)
테스트 17 〉    통과 (0.01ms, 3.96MB)
테스트 18 〉    통과 (0.02ms, 3.95MB)
테스트 19 〉    통과 (0.01ms, 3.94MB)
테스트 20 〉    통과 (0.01ms, 3.78MB)
테스트 21 〉    통과 (0.01ms, 3.9MB)
테스트 22 〉    통과 (0.01ms, 3.95MB)
테스트 23 〉    통과 (0.01ms, 3.93MB)
테스트 24 〉    통과 (0.01ms, 3.89MB)
테스트 25 〉    통과 (0.02ms, 3.95MB)
테스트 26 〉    통과 (0.01ms, 3.97MB)
테스트 27 〉    통과 (0.01ms, 3.78MB)
테스트 28 〉    통과 (0.01ms, 3.94MB)
채점 결과
정확성: 100.0
합계: 100.0 / 100.0

``` 벡터의 두번째 열을 통해서 정렬을 해주면 간단하게 문제를 풀 수 있다고 판단하였다.

출처 : https://mind-devlog.tistory.com/2

``` 풀이 방법은 생각했으나 실제로 코드화 하는데 어려움을 겪어 출처를 남긴 곳에서 공부함.

dp문제들은 코드화가 감이 안잡힌다..