IT 기록

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        
        Map<String, String> hm = new HashMap<String, String>();
        
        for(int i=0; i<phone_book.length-1; i++){
            for(int j=i+1; j<phone_book.length; j++){
                if(phone_book[i].startsWith(phone_book[j])) return false;
                if(phone_book[j].startsWith(phone_book[i])) return false;
            }
        }
        return true;
    }
}

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        
        for(String player : participant) map.put(player, map.getOrDefault(player, 0)+1);
        for(String winner : completion) map.put(winner, map.get(winner)-1);
            
        for( String key : map.keySet() ) {
            if(map.get(key) != 0){
                answer = key;
                break;
            }
        }
        
        return answer;
    }
}

두개의 문자열을 입력받은 후 , 각각의 문자열 속에 중복되는 문자가 존재하면 YES출력 아니면 NO를 출력하는 문제이다.

- 풀이방법

문자열을 char배열로 변환하여 map에 넣은 후, key값이 존재하면 YES를 출력 아니면 NO를 출력하도록 했다.

static String twoStrings(String s1, String s2) {
    int result = 0;
    HashMap<String, Integer> map = new HashMap<String, Integer>();
        
    for(char c : s1.toCharArray()){
        if(!map.containsKey(""+c)){
            map.put(""+c, 1);
        }
    }

    for(char c : s2.toCharArray()){
        if(map.containsKey(""+c)){
            result++;
        }
    }

    return (result == 0) ? "NO" : "YES";
}

유일하게 번역기 안돌리고 그냥 풀리다니.. 반갑구나 반가워요~~

두 개의 String 배열을 인자로 받는데, 

첫번째 String 배열 안에 두번째 String 배열 내의 모든 요소들이 존재하면 Yes를 출력, 아니면 No를 출력하는 문제이다.

풀이 방법은

hashMap을 이용해서 일단 첫번째 String 배열 내의 모든 요소들을 key로 해서 집어 넣는다.

value는 1로 넣으면서, 중복 문자가 있다면 value의 숫자를 1씩 증가시키면서 넣어주었다.

그리고, 두번째 String 배열 내의 모든 요소들을 루프로 돌면서 map안에 key가 존재하는지, 존재하면 value를 1씩 차감시켰고, 존재하지 않거나 value가 0보다 작아지는 경우 No를 출력하도록 했다.

static void checkMagazine(String[] magazine, String[] note) {
    // 1. 잡지에 나오는 문자열에 note의 문자열이  모두 포함되어있으면 YES else No 출력
        
    HashMap<String, Integer> map = new HashMap<String, Integer>();

    for(int i=0; i<magazine.length; i++){
       if(!map.containsKey(magazine[i])){
           map.put(magazine[i], 1);
       }else{
           map.put(magazine[i], map.get(magazine[i])+1);
       }
    }

        
    for(int i=0; i<note.length; i++){
        if(!map.containsKey(note[i])){
            System.out.println("No");
            return;
        }else{
            if(map.get(note[i]) > 0){
                map.put(note[i], map.get(note[i])-1);
            }else{
                System.out.println("No");
                return;
            }
        }
    }
    System.out.println("Yes");
    return;
}

정수형 배열이 주어지면, 중복되지 않는 쌍(pair)을 만들어

각 쌍에서 원소들 간의 차이 값에 대한 절대값이 가장 최소인 값이 얼마인지 반환하는 문제이다. 

간단한 문제라 아래와 같이 풀이 후 Submit을 눌렀는데...

static int minimumAbsoluteDifference(int[] arr) {
    int min = Integer.MAX_VALUE;

    for(int i=0; i<arr.length-1; i++){
        for(int j=i+1; j<arr.length; j++){
            min = Math.min(min, Math.abs(arr[i]-arr[j]));
        }
    }
    return min;
}

두 개의 Test Case에서 Fail이 났고, Fail 사유는 시간초과. 

이중 for문으로 시간복잡도가 O(n^2)이다.

그래서 한번의 for문을 이용해 풀어야한다.. 

정렬 후에 인접한 값을 빼주는 방법을 이용하면 한번의 for문으로 가능.

static int minimumAbsoluteDifference(int[] arr) {
    int min = Integer.MAX_VALUE;

    Arrays.sort(arr);

    for(int i=0; i<arr.length-1; i++){
        min = Math.min(min, Math.min(min, Math.abs(arr[i]-arr[i+1])));
    }
    return min;
}

문자열과 숫자를 순서대로 입력받아,

문자열의 길이가 두번째 인자로 받은 숫자만큼 길이가 될때 까지 문자열을 붙인후, 

'a'문자의 갯수를 파악하는 문제이다. 

단순히 생각하고 접근하면 테스트케이스에서 두번째 숫자가 커질경우, OutOfMemory 에러가 발생한다..

static long repeatedString(String s, long n) {
     long multipleNum =0;
     int aCnt = 0;
     long result = 0 ;

	 //먼저 문자열에서 a개수를 세고,
     //문자열을 붙인 수 만큼 곱해서 몫을 구한다.
     for(int i=0; i<s.length(); i++){
         if('a' == s.charAt(i))
             aCnt++;
     }

     multipleNum = n/s.length();
     result =  aCnt*multipleNum;

	 //나머지 문자열에서 a의 개수를 구해서 더한다.
     long remainder = n%s.length();

     for(int i=0; i<remainder; i++){
         if('a' ==s.charAt(i))
             result++;
     }
     return result;
}

배열이 주어지면 0 으로만 점프할 수 있으며, 최대 i+2인덱스 씩 점프가 가능하다. 

만약 i+2번째 인덱스의 숫자가 1이라면 i+1번째 인덱스로 점프해야 한다.

배열의 마지막 인덱스까지의 최소 점프 횟수를 구하는 문제.

static int jumpingOnClouds(int[] c) {
	int jumping = 0;
	int i = 0;

	try{
		while(true){
			if(i+1 >= c.length) break;

			if(c[i+2] == 0){
				jumping++;
				i+=2;
			}else{
				jumping++;
				i++;
			}
		}
	}catch(java.lang.ArrayIndexOutOfBoundsException e){
		jumping++;
	}

	return jumping;
}

편법이다.. 

ArrayIndexOutOfBoundsException이 발생하는 Case가 있기때문에 해당 Exception발생시, 점프횟수를 +1 해주었다.

검색좀 해보니 동적계획법을 이용해 푸는방법이 있는데, 다음번에 포스팅해야겠다..

John works at a clothing store. He has a large pile of socks that he must pair by color for sale. Given an array of integers representing the color of each sock, determine how many pairs of socks with matching colors there are.

For example, there are  socks with colors . There is one pair of color  and one of color . There are three odd socks left, one of each color. The number of pairs is .

Sample Input

9

10 20 20 10 10 30 50 10 20

Sample Output

3

배열안에 숫자들이 들어오는데 양말처럼 짝을 지어서 몇 짝이 나오는지 반환하는 문제이다.

static int sockMerchant(int n, int[] ar) {
	int result = 0;
	HashSet<Integer> colors = new HashSet<Integer>();

	for(int i = 0; i < ar.length ; i++){
		if(!colors.contains(ar[i])){
			colors.add(ar[i]);
		}else{
			result++;
			colors.remove(ar[i]);
		}
	}
	return result;
}

HashSet에 하나씩 담으면서 중복데이터가 있을경우 수량을 ++ 하고, 해당 요소를 제거하는 방법이다. 

시간복잡도 O(1)