DCP: #1 [Solved]

Good morning! Here’s your coding interview problem for today.

This problem was recently asked by Google.

Given a list of numbers and a number k , return whether any two numbers from the list add up to k .

For example, given [10, 15, 3, 7] and k of 17 , return true since 10 + 7 is 17 .

Bonus: Can you do this in one pass? hell no

Status: Solved

// Solving, Solved, Abandoned, Pending
// 푸는 중, 해결됨, 버려짐, 보류 중

k와 숫자들이 주어지면, 배열의 두 수를 k 이하로 더하고, 그 결과가 k와 같다면 true를, 다르다면 false를 반환하는 문제로 해석했습니다.
제가 할 줄 아는 언어가 자바밖에 없어서 일단은 자바로 풀어보려고 합니다. 풀면 코드 올려드리겠읍니다.
매일마다 할 수 있을진 모르겠는데, 글쎄요. 어쨌든 구독했으니 이제 푸는 일만 남았네요. 매일은 아니더라도, 최대한 빨리, 자주 한 문제씩 올려보겠습니다.

조언 받습니다만, 의도적인 정답코드 공개는 삼가 주시면 감사하겠습니다.

1 Like

정렬을 항상 생각하십시오.
잊지마세요 정렬은 nlogn입니다.

1 Like

갑자기 든 궁금증인데
데이터가 정렬된 상태로 주어진다고 했을때 해시를 안 쓴다는 가정 하에 O(n)으로 풀 수 있나요?
(대충 투포인터로 풀 수 있냐는 질문)

가능할것 같아용 ㅎㅎㅎㅎ

1 Like

일주일에 하나씩이면 대단한거져

https://blog.naver.com/jinhan814/222214370640

제가 본받고 싶은 사람입니다… (하루 50문제씩 푸는 사람)

풀긴 했는데, 현재 프로그램에 배열의 길이가 정해져 있는 문제가 있습니다.

코드
package solution1;

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] arr = new int[5];
		int k = 0, sum = 0, i = 0;
		boolean bool = false;
		while(i < arr.length) {
			arr[i] = sc.nextInt();
			i++;
		}
		k = sc.nextInt();
		Arrays.sort(arr);
		System.out.println(Arrays.toString(arr));
		for(i = 0; i < arr.length - 1; i++) {
			for(int j = 0; j < i; j++) {
				if(j == i) {
					continue;
				}
				if(sum + arr[j] + arr[i] == k) {
					bool = true;
					break;
				}
			}
		}

		System.out.println(bool);
	}
}

입력:

10 15 3 7 0
17

출력:

[0, 3, 7, 10, 15]
true

정상적으로 작동은 되나 일단 보류하겠읍니다. 피드백 받습니다.

이걸 투썸문제라고 하거든요?
리트코드:


백준:
https://www.acmicpc.net/problem/3273
아웃풋 형식 아주 조금씩만 다르니까, 코드 조금 고쳐서 넣어보시고
리트코드, 백준 둘 다 풀리는지 확인해보세요

sum은 머져? 글고 저렇게 포문 두개 돌릴거면 sort 하실 필요 없어요

저 i 는 arr의 마지막 원소인 arr[4]에는 절대 도달 못하겠네요. 마지막 원소가 답의 일부라면 false 가 나오겟네요

과연 안쪽 for문에서 break 를 한다고 포문 두개를 정상 탈출 할까요? 결국 다음 포문을 또 시작하게 되겠네요

안쪽 포문을 보면
애초에 조건을 j < i 라고 했는데 j == i 를 왜 체크해줘야 하죠? 한번도 실행될 일이 없는데

Revision
package solution1;

import java.util.Arrays;

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] arr = new int[sc.nextInt()];
		int k = 0, sum = 0, i = 0;
		boolean bool = false;
		while(i < arr.length) {
			arr[i] = sc.nextInt();
			i++;
		}
		k = sc.nextInt();
		sc.close();
		
		System.out.println(Arrays.toString(arr));
		for(i = 0; i < arr.length; i++) {
			for(int j = 0; j < arr.length; j++) {
				if(sum + arr[i] + arr[j] == k) {
					sum += arr[i] + arr[j];
					System.out.printf("%d + %d\n", arr[i], arr[j]);
					break;
				}
			}
			if(sum == k) {
				bool = true;
				break;
			}
		}
		System.out.println(bool);
	}
}

피드백 감사합니다.

sum 은 전혀 필요없으니 없애보시고

그 후엔 이중 포문 돌면서 푸는 O(n^2) 솔루션 말고
정렬과 이분탐색을 이용한 O(nlogn) 이나 해쉬를 이용한 O(n) 솔루션을 한번 생각해보세요.

Haskell
solve :: [Int] -> Int -> Bool
solve xs k = elem k $ (+) <$> xs <*> xs
1 Like