[3273] 두수의 합

| Algorithms / 백준 문제 풀이 모음 # Python, Sliver 3

백준 문제 풀이

3273번: 두 수의 합

  • 해설

      N개의 원소 중 2개를 더했을 때 X 값이 되는 조합의 수를 구하는 문제이다.
    
  일일히 2개를 픽해서 더하는 방식도 가능하겠지만, N이 크기 때문에
  좀 더 효율적인 방식이 좋을 것이다.
    
  그래서 사용하는 것이 투 포인터이다.
    
  투 포인터
  포인터를 2개 둬서 조건에 따라 해당 포인터를 이동시키면서 조건에 맞는 지 체크하는 형식이다.
  우선, 투 포인터에서 중요한 점은 2개의 포인터 중 어떤 걸 옮길지 조건을 제시해주는 것이다.
  원소들을 정렬하고, 포인터를 양쪽 끝에 둔다면...
    
  첫번째 포인터는 가장 작은 값, 두번째 포인터는 가장 큰값을 가지게 된다.
  포인터에 해당하는 두 수의 합이 X보다 작다면, 앞의 포인터를 이동 시키고
  큰 경우는 뒤의 포인터를 이동시키는 방식으로 진행한다.
    
  같은 경우는 어떻게 할까...?
    
  같은 경우는 두 포인터를 모두 이동시킨다.
    
  물론 모든 경우의 수를 보지는 않기에 시간 복잡도가 낮고, X에 가까워지도록 코드를 작성했기 때문에
  X에 해당하는 경우의 수를 모두 찾을 수 있다.

[7568] 덩치

| Algorithms / 백준 문제 풀이 모음 # Python, Sliver 5

백준 문제 풀이

7568번: 덩치

  • 해설

      문제에서는 덩치가 큰 사람에 따라서 등수를 매긴다고 한다...
  '덩치가 크다'라는 의미는 몸무게 키 모두 자신보다 큰경우만 해당하는데...
    
  이러다 보니 몸무게는 나보다 적은데, 키는 나보다 큰 경우 등에는
  누가 덩치가 큰지 알기 어렵다는 문제가 있다.
    
  이를 방지하기 위해서 자신보다 덩치큰 사람의 수로 등수를 매기는 것인데..
    
  우선 몸무게와 키를 받자.!
    
  **입력**
  한사람당 몸무게와 키 2가지 입력을 받아야 하는 경우인데.. A라는 사람에 
  접근하면, 몸무게와 키를 반환해야하기 때문에 list에 ()튜플 형태로 받는다.
  N = int(input())
  nums = []
  for i in range(N):
      a, b = map(int, input().split())
      nums.append((a, b))
    
  이러면 nums[i][0] -> 몸무게, nums[i][1] -> 키 로 반환이 된다.
    
  다음으로 각각 사람마다 비교해서 자신보다 덩치큰 사람의 수를 계산한다.
  grade = []
  for i in range(N):
      grade.append(0)
      for j in range(N):
          if nums[i][0] < nums[j][0] and nums[i][1] < nums[j][1]:
              grade[i] += 1
    
  grade 라는 리스트를 정의해서 i번째 사람마다 자신보다 덩치큰 사람 수를 
  카운트한다.
    
  이제 등수를 산정하면 되는데...
  자신보다 덩치큰 사람의 수이기 때문에 1등은 자신보다 큰사람이 없을 것이고,
  2등은 1명, 3등은 2명, 4등은 3명...
  즉, n등은 자신보다 덩치큰 사람이 n-1명 있는 것이다.
    
  반대로 생각하면 자신보다 덩치큰 사람 수+1 = 등수이다!
  **출력**
    
  result = ''
  for i in grade:
      result += str(i+1) + ' '
  print(result)
  이러면 성공적으로 각각 등수를 출력하게 된다.

  • 답안

      if __name__ == '__main__':
      N = int(input())
      nums = []
      for i in range(N):
          a, b = map(int, input().split())
          nums.append((a, b))
    
      grade = []
      for i in range(N):
          grade.append(0)
          for j in range(N):
              if nums[i][0] < nums[j][0] and nums[i][1] < nums[j][1]:
                  grade[i] += 1
    
      result = ''
      for i in grade:
          result += str(i+1) + ' '
      print(result)

Pagination