Good Program Good Programmer

문제

온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다.

출력

첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다.

해결 방법

이 문제의 경우도 앞선 문제와 크기 다르지 않다.

정렬하는 인자가 나이와 가입순으로 바뀌었을 뿐이지 지난 정렬문제에서 썼었던 다인자 정렬방식을 그대로 쓰면될 듯 하다.

문제는 이번엔 정렬 요소는 2개인데 나이값에 따라 따로 이름을 저장해야한다는 점이다.

필자는 이 문제를 풀 때 정렬 요소를 2개에서 1개로 줄였다.

무슨 말이냐면 나이 순으로 정렬하되 나이가 같으면 가입한 순으로 정렬을 하라고 되어있는데 이때 LinkedhashMap을 쓰면 가입한 순번을 따로 인자로 둘 필요없이 자연스레 가입한 순서대로 출력이 된다.

따라서 인자가 2개에서 1개로 줄었기 때문에 예전처럼 map을 써서 나이(key) - 이름(value)로 저장하면 시간도 빠르고 잘 정렬될 것이다.

그래서 프로그램의 동작과정은 다음과 같다.

1. 나이(key) - 이름(value) 형식의 map으로 값들을 입력받는다.

2. 나이(key)를 배열로 리턴한 뒤 정렬한다.

3. 정렬된 나이순대로 이름을 map에서 가져와서 문자열에 추가한다.

1. 

2. 

3.

테스트용 코드

위 코드는 저번 코드에서와 마찬가지로 words.txt에서 1개를 빼오고 1~200까지의 수 중 랜덤으로 1개를 골래서

"나이 단어" 순으로 n개의 문자열을 생성해주는 코드이다.

words.txt link : github.com/dwyl/english-words/blob/master/words.txt

위 코드를 이용해 10만개의 문자열을 생성하고 우리가 작성한 코드에 넣어서 실행해보았더니

위와 같은 실행시간이 도출되었다.

소스코드

느낀점

만약 지금까지의 문제들을 착실히 풀어왔다면 그리 어렵지 않은 문제였다.

특히나 LinkedHashMap을 이용한 것이 신의 한수였다.

문제

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

입력

첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

출력

조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.

문제풀이

이전 글 좌표 정렬하기 느낀점에서 내가 짠 코드보다 더 나은 코드가 있어서 소개한적이 있었다.

그 코드는 List.sort(); 메소드에 new comparator 클래스를 선언하여 그 안에 있는 compare메소드를 오버라이드해서 새로운 규칙의 비교 메소드를 생성하는 형식을 람다로 축소하여 2개 이상의 인자에 대하여 정렬하는 방법을 소개한적 있었다.

그래서 이번 문제에서 그 코드를 응용하여 적용해보았는데 위와 같은 13개의 입력값에 대해선 문제없이 작동하는 걸 확인하였다. 아래가 그 코드이다.

위 코드는 테스트용 코드로 20000개의 랜덤한 단어들을 문자열로 입력받아서 정렬을 수행하는 코드이다.

하지만 위 코드로 테스트를 진행했을 때 실행시간이 거의 2.5~3초 가까이 나왔다.

그래서 보기엔 더 심플하고 더 빠르게 될 것만 같았던 코드가 시간초과로 문제를 해결할 수 없자 살짝 뇌정지가 왔었다.

그래서 이전에 내가 썼던 방법대로 map을 이용하여 정렬하는 방식을 이용해야겠다는 생각이 들었다.

그래서 맵을 이용해서 2개의 인자를 정렬할 때는 다음과 같은 방식으로 진행한다.

1. 값을 입력받는다.

2. map에 해당 데이터를 입력한다. 이때 만약 같은 값이 있다면 넘어간다.

3. 입력받은 데이터의 key 배열을 정렬한다.

4. 각 key에 해당하는 value리스트를 정렬한다.

5. 각각의 key와 value들을 순서대로 출력한다.

1~2.

먼저 n을 입력받고 map을 만든 후 단어들을 입력받는다. 이때 해당key값이 없다면 새로운 list를 추가해준 뒤 값을 입력한다.

이때 해당 key값에 문자열 s가 있는지 확인하여 있다면 아무런 동작도 하지 않고 없다면 문자열을 추가한다.

이 코드가 내가 위에 썼었던 코드보다 빠르게 동작하는 이유는 위 코드는 값이 들어올 때마다 모든 리스트를 탐색하는 반면 이 코드는 입력된 값이 특정 key에 해당하는 리스트에서만 존재하는지 확인하기 때문에 실행시간이 현저하게 줄어들기 때문이다.

3.

4.

key값에 해당하는 리스트들을 정렬해준다. 여기서는 문자열만 비교하므로 특별히 new comparator클래스를 만들필요는 없다.

5.

그리고 모든 값들을 문자열에 추가한 뒤 해당 문자열을 리턴하면 끝난다.

테스트용 단어 생성기 코드

이 코드는 words.txt라는 텍스트 파일로부터 단어를 n개 만큼 랜덤으로 가져오는 메소드이다. 해당 텍스트 파일의 단어의 갯수가 466550개여서 466550크기의 배열을 생성하였다.

https://github.com/dwyl/english-words/blob/master/words.txt

위 경로에 가면 다운받을 수 있는 사전 파일이다.

wordSortUsingMap vs wordSortUsingList

wordSortUsingMap은 문제를 해결한 코드이고 wordSortUsingList는 시간 초과가 난 코드이다. 두 코드 간의 시간 차이를 비교해보겠다.

 테스트 코드는 위와 같고 그 결과는 다음과 같다.

거의 7배 가까이 차이가 나는 것을 볼 수 있다. 내가 잘못한 건지는 몰라도 sort메소드에 compare메소드를 오버라이드해서 정렬하는 방식은 조금 느리다는 것을 확인할 수 있었다.

물론 주요한 시간의 차이는 처음 값을 입력받을 때 중복값을 검사하는 과정에서 발생한다는 것을 감안해도 좀 심한 차이인 것 같다.

만약에 처음 중복값을 검사하지 않는다면 어떻게 될까해서 돌려보았더니 결과는 다음과 같았다.

여전히 7배 가까이 차이가 나는 것을 확인할 수 있었다.

소스코드

느낀점

일단 좋아보이는 코드가 진짜 다 좋은건 아니구나라는 것을 느꼈다.

문제

1. 2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

2. 2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 x_i와 y_i가 주어진다. (-100,000 ≤ x_i, y_i ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

출력

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

[ X좌표 순 ]                                                              [ Y좌표 순 ]

문제풀이

이 두 문제는 매우 유사하기 때문에 같이 묶어서 설명하겠다.

문제를 읽어보면 알겠지만 2개의 인자 중 주 인자와 보조 인자를 설정하여 주 인자 순으로 정렬하되 순서가 같은 주 인자들은 보조 인자를 사용하여 정렬을 하는 문제이다.

그래서 본인은 다음과 같은 과정을 통해 문제를 해결하였다.

1. 주 인자를 1차원 배열에 담는다.

2. 주 인자를 key로 가지고 보조 인자들을 가지는 리스트를 value로 하는 map을 사용하여 좌표들을 입력받는다.

3. 주 인자를 가진 1차원 배열을 정렬한다.

4. 보조 인자들이 들어있는 리스트들을 정렬한다.

5. 정렬된 1차원 배열의 값들에 해당하는 value들을 리스트에서 뽑아내면서 출력한다

이상이다.

그럼 위 동작들을 코드로 설명하겠다. 여기서 좌표 정렬하기 1의 주 인자와 보조 인자는 x, y이고 좌표 정렬하기 2의 주 인자와 보조 인자는 y, x이다.

1.

먼저 얼마만큼 입력받을 것인지 n을 입력받고 주 인자를 저장할 1차원 배열(coor)을 선언한다.

그리고 map을 선언하는데 key는 정수형으로 value는 정수형 리스트로 정하여 선언한다.

여기서 linkedhashmap을 쓴 이유는 순차적으로 저장되면 찾을 때도 더 빠를 것 같아서 썼다. 

그리고 임시로 문자열을 저장할 tmp변수를 선언한다.

2 ~ 3.

[ 1 ]

[ 2 ]

위 그림처럼 tmp에 저장할 값 문자열을 입력받고

coor배열에 x 또는 y를 입력받는다.

그리고 만약 해당 값이 map에 key로 존재하지 않는다면 map을 새로 생성한 후 그 안에 나머지 y 또는 x를 입력받는다.

그 후 주 인자가 들어있는 coor 배열을 정렬한다.

이렇게하면 주 인자들의 순서가 정렬된다.

4.

그렇가 저장된 map에서 value로 저장된 리스트들을 검사하면서 size가 1이라면 그 키에 해당하는 value가 1개 밖에 없다는 것이므로 아무 동작도 하지 않고 size가 2 이상이라면 해당 리스트를 정렬한다.

이렇게 함으로써 주 인자들에 해당하는 보조 인자들의 순서가 정렬된다.

5. 

[ 1 ]

[ 2 ]

이제 주 인자 배열을 돌면서 값들을 리스트의 맨 처음에서 하나씩 꺼내어 그에 해당하는 값을 출력하고 해당 값을 value의 리스트에서 제거하는 식으로 정렬된 좌표들을 문자열에 추가한다.

[1]과 [2]의 빨간색으로 밑줄 친 부분은 x,y의 출력순서가 다른 부분이다.

그리고 완성된 문자열을 리턴하여 출력하면 모든 값들이 정상적으로 정렬되어 출력되는 것을 볼 수 있다.

Junit 테스트

junit테스트는 따로하지 않았다 왜냐하면 문제에 주어진 예시만 제대로 정렬해도 다른 모든 값들에 대해서 정상적으로 동작하기 때문이다.

시간 테스트

문제에 주어진 시간테스트를 하기위해 다음과 같은 코드를 작성하였다.

위 코드는 -100000 < x < 100000 , -100000 < y < 100000에 해당하는 좌표들을 입력된 n들을 갯수와 함께 출력해주는 코드이다.

위 코드를 사용하여 100,000개의 값들을 돌린결과

0.4 ~ 0.5초 정도 나오는 것을 확인할 수 있었다.

소스코드

느낀점

이 문제는 값을 입력하는 과정에서 조금 시간이 오래 걸려서 당황했던 문제였다.

우리가 직접 입력한 값들을 처리하는 실제 코드에서는 상관이 없지만 junit을 테스트하기 위해서 여러 값들을 입력받는 코드에서 문자열로 인자를 전달받았을 때 해당 문자열을 실제 좌표들로 변환하고 Map에 매핑하는 과정에서 값들을 하나씩 입력받으면 굉장히 오랜 시간이 걸렸었다.

이런 문제를 해결하고자 아래 코드를 이용하였다.

값을 str 문자열로 입력받은 뒤 제일 첫 번째 값을 빼서 n에 저장하고 나머지 문자열의 개행 문자를 모조리 공백으로 바꾼다.

그 후 모든 문자열을 공백을 기준으로 나눠서 배열에 저장하고 실제 값들을 저장할 땐 해당 배열에서 직접적으로 입력받았다.

왜냐하면 배열 자료구조는 값의 탐색이 빠르기 때문에 조금 더 빠르게 동작할 거라 생각했기 때문이다.

그 결과 메소드를 실행하는데 필요한 시간이 19초에서 1초 미만으로 줄었다.

처음에는 방법이 잘못된 건줄 알았지만 입력값을 처리하는 과정이 이렇게나 오래 걸리는 문제는 처음이라 당황하였다.

그리고 이 문제의 여러가지 풀이법을 보다가 내 코드보다 조금 더 나은 코드가 있어서 소개하려고 한다.

www.acmicpc.net/board/view/62866

위 코드는 list형의 sort라는 메소드를 이용하여 정렬하는데 람다식을 사용하여 조금 더 간단히 문제를 풀었다. 위 코드는 2가지 인자 뿐만 2차원 좌표 뿐만 아니라 3차원 좌표, 4차원 좌표에 대해서도 응용하여 사용하면 굉장히 유용할 것 같아서 이곳에 기록해둔다.

문제

배열을 정렬하는 것은 쉽다. 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬해보자.

입력

첫째 줄에 정렬하고자하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 자리수를 내림차순으로 정렬한 수를 출력한다.

문제풀이

이 문제는 워낙에 쉽기때문에 별로 설명할 것이 없다.

그냥 각 자릿수대로 나눠서 배열에 저장 후 내림차순으로 정렬한다.

그리고 다시 그 값들을 순서대로 붙이면 끝난다.

소스코드

느낀점

쉽다!

문제

수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자.

1. 산술평균 : N개의 수들의 합을 N으로 나눈 값
2. 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
3. 최빈값 : N개의 수들 중 가장 많이 나타나는 값
4. 범위 : N개의 수들 중 최댓값과 최솟값의 차이

N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.

출력

첫째 줄에는 산술평균을 출력한다. 소수점 이하 첫째 자리에서 반올림한 값을 출력한다.

둘째 줄에는 중앙값을 출력한다.

셋째 줄에는 최빈값을 출력한다. 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다.

넷째 줄에는 범위를 출력한다.

문제풀이

이 문제는 다른 것들은 굉장히 쉬운 입문자용 문제인데 3번 최빈값이 조금 복잡하다.

이걸 어떻게 풀어야 하는지 좀 많이 헷갈렸었다.

1. 산술평균

먼저 산술평균부터 보도록 하겠다.

모든 주어진 모든 값들을 average라는 변수에 더한 후 그 갯수로 나누어준다.

이때 나누는 갯수를 (double) 형으로 변환해서 자연수를 소수로 만들어 준다음 반올림을 한 값을 다시 (int) 형으로 변환하여 평균값을 구해준다.

왜냐하면 문제에서 소수점 첫째 자리에서 반올림한 값을 출력한다고 했기 때문이다. 

2. 중앙값

나는 처음엔 이것도 헷갈렸었다.

왜냐하면 갯수가 홀수인 경우엔 중앙값이 있지만 짝수인 경우엔 중앙값이라는게 없지 않는가?

배열을 정렬한 후 갯수/2에 위치한 값을 담았는데 맞아서 굉장히 놀랐다.

언제나 느끼지만 백준 문제에는 설명이 부족한 것 같다.

4. 범위

범위도 뭐 별거 없다. 그냥 정렬된 배열에서 제일 마지막 값과 제일 처음값을 빼주면 된다.

3. 최빈값

드디어 대망의 최빈값이다. 이 문제의 하이라이트라고 봐도 무방한 문제이다.

문제에서는 최빈값을 가장 많이 나타난 수라고 정의하였고 만약 가장 많이 나타난 수가 여러 개일 경우 그 값들 중 두 번째로 작은 값을 구하라고 하였다.

그렇게 하기 위해서는 먼저 가장 많이 나타난 값을 찾아야 한다.

먼저 배열을 정렬한다.

그리고 위 코드를 사용하여 최빈값을 찾는다.

그런데 이렇게 하면 최빈값의 빈도수를 알 수는 있지만 최빈값이나 최빈값들 중 2번째로 작은 값을 알지는 못한다.

따라서 우리는 여러개의 값들을 빈도수대로 저장할 수 있는 자료구조가 필요하다.

그래서 선택한 것이 map 자료구조이다.

map 자료구조를 사용하여 key값엔 빈도수를 value들엔 해당 값을 넣는 것이다.

하지만 빈도수가 여러가지인 값들의 경우 map.put()을 실행할 때마다 value가 바뀌게 되어 여러가지 값들을 저장하지 못한다. 

이럴때를 대비하여 아래와 같은 자료구조를 사용할 것이다.

위 구조는 close addressing hash table이라는 아주 생소한 자료구조이다.

이름만 생소하지 구조는 위 그림과 같이 간단하다.

만약 같은 key값의 여러개의 value값들이 존재한다면 위 그림처럼 list로 엮어주는 것이다.

위 그림을 구현하기 위하여 위 코드를 작성한다. 이때 LinkedHashMap을 쓰는 이유는 값을 저장한 순서대로 저장하기 위해서이다.

하지만 그냥 HashMap으로 써도 무방하다. 처음엔 순서대로 저장해야 마지막 값을 빼서 최대 빈도수를 구할 수 있을 줄 알았는데 그런 메소드는 없어서 그냥 maxRep이라는 변수를 이용하여 최대 빈도수를 알아내서 그 값으로 value를 리턴받는 식으로 코딩을 하였다.

HashMap, LinkedHashMap, TreeHashMap을 언제 사용하는지 알고 싶다면 

m.blog.naver.com/PostView.nhn?blogId=tau300&logNo=130133380430&proxyReferer=https:%2F%2Fwww.google.com%2F

이곳으로 가서 확인하면 된다.

그렇게 선언을 한 후 빈도수 1을 키값으로 하는 arraylist를 value값으로 넣어준다.

그리고 초기에 설계했던 반복분에서 다음과 같은 코드들을 추가해준다.

위 코드와 같이 반복문 맨 처음엔 rep에 해당하는 빈도수의 키값에 있는 arrayList에 우리가 조사하는 값이 있는지 없는지를 조사하여 값의 중복 저장을 막는 코드를 넣는다.

그리고 똑같이 해당 값의 빈도수를 조사한 후 해당 빈도수의 키가 없다면 추가한 후 해당 빈도수에 값을 넣고 빈도수가 이미 존재한다면 해당 키값에 해당하는 ArrayList에 값을 넣는다.

이렇게 하면 {빈도수 : 해당 값들}에 해당하는 [1 : N] 관계의 HashTable이 만들어질 것이다.

그리고 위 코드를 이용하여 최다 빈도수인 maxRep을 키 값으로 가지는 ArrayList를 정수 배열로 반환받아서 정렬을 한다.

그리고 위 코드를 이용하여 만약 해당 배열의 값이 1개라면 제일 첫 번째 값을 리턴받고 배열이 여러개라면 여러 개의 값들 중 두 번째로 작은 값을 리턴받으면 문제에서 원하는 최빈값을 구할 수 있다.

Junit 테스트

위 값들을 가지고 실험을 하였고

문제없이 실행되었다.

실행시간

위 코드를 이용하여 문제에서 주어진 500,000개의 4000을 넘지 않는 정수값들을 문자열로 리턴받은 뒤 실험하였더니

평균적으로 0.3~0.4초 정도가 나와서 시간 안에 풀 수 있었다.

소스코드

느낀점

뭔가 쉬워보여서 도전했다가 최빈값에서 많이 당황하여 문제를 푸는데 좀 시간이 걸렸던 것 같다.

문제

666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다.

하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다.

종말의 숫자란 어떤 수에 6이 적어도 3개이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 숫자는 666이고, 그 다음으로 큰 수는 1666, 2666, 3666, .... 과 같다.

따라서, 숌은 첫 번째 영화의 제목은 세상의 종말 666, 두 번째 영화의 제목은 세상의 종말 1666 이렇게 이름을 지을 것이다. 일반화해서 생각하면, N번째 영화의 제목은 세상의 종말 (N번째로 작은 종말의 숫자) 와 같다.

숌이 만든 N번째 영화의 제목에 들어간 숫자를 출력하는 프로그램을 작성하시오. 숌은 이 시리즈를 항상 차례대로 만들고, 다른 영화는 만들지 않는다.

입력

첫째 줄에 숫자 N이 주어진다. N은 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 N번째 영화의 제목에 들어간 수를 출력한다.

문제풀이

이 문제는 너무 쉬워서 별로 설명할 것이 없는듯하다.

문제에 나와있는대로 666이 들어가는 숫자중 n번째 숫자를 찾으면 되므로

1. 숫자를 계속해서 증가시킨다.

2. 그 와중에 666이 들어가는 숫자가 있다면 카운팅을 증가시킨다.

3. 카운팅이 입력된 숫자와 같다면 그때의 숫자를 리턴한다.

소스코드

느낀점

처음에 666앞에 더하게 (n-1)을 하는 줄 알았는데 아니어서 당황했다;;;

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M*N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8*8 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8*8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

출력

첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

문제풀이

이번 문제 또한 설명이 굉장히 복잡하기 때문에 간단히 풀어서 설명해보도록 하겠다.

1. 체스판은 무조건 8x8의 형태이며 한 변을 공유하는 두 칸의 색깔은 서로 달라야 한다.(왼쪽이 흰이면 오른쪽은 검)

2. N(세로)xM(가로)의 칸으로 나뉘어진 판에서 8x8 칸만 따로 띄어 놓고 보았을 때 그 칸이 체스판이 되려면 몇몇 개의 칸의 색깔을 바꿔야 한다.

3. 이때 이 색깔을 바꾸는 횟수의 최솟값을 구하여라.

이것이 이 문제의 핵심이다.

그렇다면 이것을 코드로 구현해보겠다.

먼저 입력값을 적절하게 처리하여 받아준다.

그리고 여러가지 변수를 만드는데 모두 필요한 것들이다.

diffCnt는 주어진 판에서 8x8의 체스판이 나올 수 있는 갯수만큼의 크기를 가진 배열이다. 이 배열은 각각의 체스판과의 비교에서 몇 개의 칸을 바꿔야 하는지 저장할 변수이다.

문제에서는 최솟값만을 구하라고 하였으므로 이 배열은 필요가 없지만 나중에 어떠한 값들이 나왔는지 확인하기 위해 생성하였다.

그리고 diffdiffCnt변수는 이름이 좀 그렇긴 하지만 diffCnt의 카운팅 변수이다.

String변수 3개는 각각 위에서부터 왼쪽 제일 위가 흰색일 때의 체스판과 왼쪽 제일 위가 검은색일 때의 체스판, 그리고 입력된 판에서 추출한 체스판 문자열이 담길 변수이다.

incompleteChessBoard를 변수로 쓰는 이유는 체스판을 추출하여 원래의 체스판과 비교하기 때문이다.

그냥 원래 입력값에서 for문을 통하여 하나하나 비교하는 것도 되지만 이 방법이 배열을 이용하는 방법보다 빠르기 때문에 그냥 이렇게 하였다.

그리고 그 밑의 min은 최솟값이 담길 변수이고, tmp1과 tmp2는 각각 입력된 값이 얼마나 많이 바뀌었나를 저장할 임시변수이다. 이 임시변수가 2개인 이유는 밑에서 설명하도록 하겠다.

이번 코드의 핵심 코드이다.

언뜻보면 어려워보이는 코드이지만 실제로는 굉장히 간단한 코드이다.

1. 입력된 판에서 8x8판을 →(가로), ↓(세로) 순으로 추출한다.

2. 추출된 8x8판을 W로 시작하는 체스판, B로 시작하는 체스판과 비교하여 얼마나 다른가 측정한다.

3. 그리고 두 측정값 중 가장 작은 값을 추출하여 실제 min에 들어있는 값과 비교하여 어떤값이 더 작은가 확인한다.

4. 더 작은 값을 배열에 저장하고 배열의 카운팅 변수를 증가시킨다.

5. 1~4를 반복한다.

이 코드에서 보다시피 w로 시작하는 체스판과 b로 시작하는 체스판을 추출된 체스판과 비교하기 때문에 tmp1과 tmp2라는 임시변수가 2개가 쓰인다.

이렇게 2개를 비교하는 이유는 둘 중 하나만 비교했을 때 

8 9
BBBBBBBBB
BBBBBBBBB
BBBBBBBBB
BBBBBBBBB
BBBBBBBBB
BBBBBBBBB
BBBBBBBBB
BBBBBBBBW

이런 값이 들어올 경우 1가지로만 비교하면 최솟값이 31이 아닌 32가 나올 수 있기 때문이다. 

이런 오류를 제거하기 위해 번거롭지만 w로 시작하는, b로 시작하는 체스판과 추출된 체스판을 각각 비교하는 것이다.

테스트 해본 값들

입력 예시 2개

8 8
BBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

출력값: 1

8 9
BBBBBBBBB
BBBBBBBBB
BBBBBBBBB
BBBBBBBBB
BBBBBBBBB
BBBBBBBBB
BBBBBBBBB
BBBBBBBBW

출력값: 31

위 코드를 이용하여 최대 50x50판을 입력값으로 넣었을 때 연산시간

평균 0.05초 정도 걸렸었다.

소스코드

느낀점

이번 문제는 처음부터 설계를 잘못해서 여러가지 반례가 많이 발생한 결과 완벽하게 코드를 작성했다고 생각했지만 완벽하지 않아서 조금 헤맸던 것 같다.

질문 검색에서 여러가지 반례들이 있었기에 풀 수 있었던 문제인 것 같았다.

문제

우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x, y), (p, q)라고 할 때 x > p 그리고 y > q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다. 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56, 177), (45, 165) 라고 한다면 A의 덩치가 B보다 큰 셈이 된다. 그런데 서로 다른 덩치끼리 크기를 정할 수 없는 경우도 있다. 예를 들어 두 사람 C와 D의 덩치가 각각 (45, 181), (55, 173)이라면 몸무게는 D가 C보다 더 무겁고, 키는 C가 더 크므로, "덩치"로만 볼 때 C와 D는 누구도 상대방보다 더 크다고 말할 수 없다.

N명의 집단에서 각 사람의 덩치 등수는 자신보다 더 "큰 덩치"의 사람의 수로 정해진다. 만일 자신보다 더 큰 덩치의 사람이 k명이라면 그 사람의 덩치 등수는 k+1이 된다. 이렇게 등수를 결정하면 같은 덩치 등수를 가진 사람은 여러 명도 가능하다. 아래는 5명으로 이루어진 집단에서 각 사람의 덩치와 그 등수가 표시된 표이다.

이름(몸무게, 키)덩치 등수

위 표에서 C보다 더 큰 덩치의 사람이 없으므로 C는 1등이 된다. 그리고 A, B, D 각각의 덩치보다 큰 사람은 C뿐이므로 이들은 모두 2등이 된다. 그리고 E보다 큰 덩치는 A, B, C, D 이렇게 4명이므로 E의 덩치는 5등이 된다. 위 경우에 3등과 4등은 존재하지 않는다. 여러분은 학생 N명의 몸무게와 키가 담긴 입력을 읽어서 각 사람의 덩치 등수를 계산하여 출력해야 한다.

입력

첫 줄에는 전체 사람의 수 N이 주어진다. 그리고 이어지는 N개의 줄에는 각 사람의 몸무게와 키를 나타내는 양의 정수 x와 y가 하나의 공백을 두고 각각 나타난다.

출력

여러분은 입력에 나열된 사람의 덩치 등수를 구해서 그 순서대로 첫 줄에 출력해야 한다. 단, 각 덩치 등수는 공백문자로 분리되어야 한다.

제한

• 2 ≤ N ≤ 50
• 10 ≤ x, y ≤ 200

문제풀이

이 문제는 말이 좀 많이 헷갈리는 문제이다.

www.acmicpc.net/board/view/18431

위 웹사이트를 가면 쉽게 알 수 있는데 

a : (100, 100)

b : (100, 10)

c : (50, 50)

이 세 경우가 있다고 생각해보자

문제에 따르면 두 사람의 덩치를 비교할 때 x > p 그리고 y > q이면 (x,y)의 덩치가 더 크다고 한단다.

그렇다면 a와 c의 경우는 분명하게 a의 덩치가 c의 덩치보다 크다고 할 수 있는데 a와 b, b와 c는 각각 서로의 덩치가 크다고 말할 수 없는 관계가 아니다.

이렇게 되면 a와 c의 관계 또한 서로 크다고 할 수 없는데 분명 a는 c보다 덩치가 크다고 할 수 있으므로 모순이 발생한다.

이럴때는 어떻게 해야 하는지 궁금했었는데 위 웹사이트에 가면 이에 대한 답으로 그냥 문제에 있는 

"N명의 집단에서 각 사람의 덩치 등수는 자신보다 더 "큰 덩치"의 사람의 수로 정해진다. 만일 자신보다 더 큰 덩치의 사람이 k명이라면 그 사람의 덩치 등수는 k+1이 된다."

이 문장을 보면 된다고 한다.

즉 위와 같은 경우에서는 a보다 덩치가 큰 사람은 없으므로 a의 등수는 1이고, b 또한 b보다 덩치가 큰 사람이 없으므로 등수가 1이다. 그리고 c는 c보다 덩치가 큰 a라는 사람이 1명 있기 때문에 등수가 1+1=2가 된다.

즉 다른 사람들과의 관계는 생각을 하지 않고 오직 그 사람보다 덩치가 큰 사람들만을 세서 그 사람의 등수를 메기는 방식이라 우리가 생각하는 기존의 등수랑은 개념이 다르다.

이것 때문에 굉장히 생각을 많이 했었는데 위 답변을 보고 문제를 풀었더니 정답이어서 굉장히 당황스러웠다.

이럴거면 등수가 아닌 자기보다 덩치가 큰 사람의 수를 세라고 명확히 명시해주면 조금 더 잘 알아들을 수 있었을텐데 문제 자체가 조금 아쉽다.

아무튼 이러한 문제해결 방식으로 코딩을 하면 다음의 과정을 거치게 된다.

먼저 몇 개의 갯수를 입력받을지 결정하는 수를 입력받고

체중과 몸무게를 일정한 형식으로 입력받는다.

그리고 문자열로 입력받은 값들을 모두 정수로 바꿔서 배열에 저장한다.

그리고 Map이라는 collection을 사용하여 각각의 배열을 키 값으로 등수를 value값으로 설정하여 저장할 것이다. 그리고 순서대로 map의 value들을 뽑아내면 우리가 원하는 출력값을 얻을 수 있을 것이다.

이때 HashMap이 아닌 LinkedHashMap을 사용하는 이유는 값들을 뽑아낼 때 순서대로 뽑아내기 위해서이다. 일반적인

HashMap을 사용해도 get함수를 사용하면 순서대로 뽑아낼 수 있지만 메소드를 사용하는 것보다 순차적으로 뽑는게 더 빠를 것 같아서 LinkedHashMap을 사용하였다.

사실은 원래 

이런식으로 저장을 하려고 하였다. 몇 등에 해당하는 것들끼리 묶어서 쭉쭉쭉 연결될 수 있도록 하는 것이다.

하지만 그렇게 하다보니 등수는 1등인데 알고보니 2,3,4등보다 덩치가 작은 요소가 있는 모순이 발생하기 때문에 이런 방식은 채택하진 않았는데 지금와서 생각해보니 이런 방식 또한 가능할 것 같긴하다.

하지만 이를 알아채기 전에 이미 각각의 요소마다의 키에 해당하는 등수를 value값으로 주는 방식으로 문제를 풀었기 때문에 그 방식으로 코딩을 진행해보도록 하겠다.

위 코드가 이번 코드의 메인이자 핵심코드이다.

입력받은 값들의 갯수만큼 반복문을 도는데 바깥 반복문에서는 비교할 대상 1개를 선택하여 map에 넣고

안쪽 반복문에서는 비교할 대상 1개를 제외한 나머지의 대상들을 바깥 반복문에서 지정한 비교대상과 계속해서 비교를 해 나간다.

이때 만약 비교되는 대상이 비교하는 대상보다 크다면 비교하는 대상은 비교되는 대상보다 작은 것이므로 등수를 +1하여 다시 map에 저장한다.

이 과정이 끝나면 Map에는 각각의 덩치에 해당하는 등수가 적혀져 있을 것이다.

이를 위 코드를 이용하여 문자열로 뽑아낸다음 앞 뒤 공백을 제거한 문자열을 돌려주면 우리가 원하는 값을 얻을 수 있다.

Junit테스트는 위와 값들을 가지고 실행하였고 모두 정상적인 결과가 출력되는 것을 확인하였다.

또한 문제에서 제한한 50개의 덩치값들을 넣고 실행한 결과 위와 같이 0.002초만에 모든 분류 작업을 완료할 수 있었다.

소스코드

느낀점

문제에서 정의하는 등수와 내가 알고 있던 등수와 달라서 많이 고민을 했던 문제였다.

문제

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.

자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.

문제풀이

문제가 너무 기므로 간단히 하자면 다음과 같다.

생성자가 198이라 했을 때

198 + 1 + 9 + 8은 216이므로

216은 198의 분해합이다.

또한 198은 216의 생성자이다.

이때 분해합 N이 주어졌을 때 이 분해합 N을 생성하는 생성자 중 가장 작은 값을 찾는 것이 문제의 목표이다.

즉, 216이라는 분해합은 207과 198이라는 생성자가 있지만 이 중 더 작은 198만을 출력해야 하는 것이다.

그렇다면 분해합 N의 생성자를 찾으려면 어떻게 해야할까?

물론 수학적 공식을 이용하여 풀 수도 있지만 이 챕터의 주제가 무작위 대입이므로 1부터 1000000까지 값을 증가시키면서 216이라는 분해합을 갖는 생성자를 찾는 방법이 좀 더 쉬울 것 같다.

하지만 그렇다고 진짜 1부터 백만까지 반복문을 돌려서 찾게되면 시간이 너무 길어지기 때문에 문제를 풀지 못할 수 있다.

그래서 생각해낸 꼼수가 각 자릿수의 최댓값이 숫자 9이기 때문에 (자릿수의 갯수 * 9)를 분해합에서 뺀 숫자 중에 생성자가 있는지 찾는 방법이다.

먼저 int n을 매개변수로 입력받아서 n의 자릿수를 알아낸다.

그리고 위 그림과 같은 변수들을 선언해준다.

sum은 분해합을 저장할 변수이고

result는 생성자를 저장할 변수이다.

minNum과 maxNum은 어느 구간의 생성자들을 이용할 건지 결정해주는 변수이다.

그리고 tmp는 생성자의 각 자릿수를 구하기 위하여 연산을 할 때 임시로 값을 보관해둘 변수이다.

그리고 위 소스코드와 같이 sum 변수에다가 분해합을 구한 뒤 sum변수가 n과 같다면 해당 i값이 n의 생성자가 되므로 해당 값을 리턴해주면 된다.

분해합을 구할 때는 각 자릿수를 10의 자릿수로 나눈 몫을 분해합에 더하고 각 자릿수를 10의 자릿수로 나눈 나머지를 1작아진 10의 자릿수로 나눈 몫을 다시 분해합에 더하는 방식을 사용하였다.

소스코드

느낀점

위 코드에서 더 간소화된 코드를 사용할 수도 있었지만 가독성을 위하여 위 코드와 같이 코딩을 하였다.

문제

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.

한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.

김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.

이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.

N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

입력

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.

합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.

문제풀이

이 문제는 처음엔 굉장히 어려워 보이지만 정말 말그대로 브루트 포스(무작위 대입)으로 풀 수 있다.

나도 처음엔 어떻게 해야 조금 더 우아하게 더 나은 공식을 써서 풀 수 있을까 고민했는데 결국 답이 안나와서 걍 무작위 대입으로 풀었더니 시간내에 해결할 수 있었었다.

먼저 입력을 받아서 String배열에 저장해준다.

그 다음에 여러 변수를 선언해준다. M은 말그대로 M값이고

nearst_M은 M에 가장 가까운 값을 가질 변수이고

s_len은 문자열로 넘겨받은 숫자들 중에서 M보다 작은 값들의 갯수를 세는 변수이다. 이 변수는 별도의 필요없는 값들에 대한 계산을 최소화하기 위하여 새로운 배열을 생성할 때 배열의 크기를 결정해주기 위하여 사용한다.

i_cnt변수는 그냥 정수형 배열에 값을 저장해줄 때 원 배열의 증가값과 함께 증가하면 띄엄띄엄 저장이 되므로 연속적으로 값들을 배열에 저장해주기 위하여 쓰는 카운팅 변수이다.

tmp는 3값을 더한 값을 임시로 저장해두는 변수이다.

그 후 M값보다 작은 값들의 갯수를 세서 새로운 배열을 선언해준다.

그리고 또 다시 M보다 작은 값들을 찾아내어 이번엔 실제 배열에 저장해준다.

여기서 정렬은 디버깅하거나 실제로 배열에 어떤 값들이 들어왔나 한 눈에 보기 편하게 하기 위하여 사용할 수 있다.

지금은 시간 단축을 위하여 정렬은 하지 않겠다.

그리고 이번 코드의 핵심이라고 할 수 있는 무작위 대입 코드이다. 3개의 값들을 선택하는데 서로 겹치지 않도록 해야한다.

이때 가장 효과적인 것이 중첩 for문으로 시작점과 끝점이 겹치지 않도록 구성하는 것이다. 중첩문 안으로 들어갈 수록 시작값이 1씩 증가하고 끝값도 1씩 증가하는 것을 볼 수 있다. 이렇게 중복되는 값들이 없도록 구성을 하면 시간을 조금이라도 더 절약할 수 있다.

그리고 마지막에 M에 가장 가까운 값을 출력한다.

소스코드

느낀점

조금 더 우아한 방법으로 풀고 싶었는데 이렇게 해도 문제가 해결이 되니 좀 허무한 것 같다.